前提・実現したいこと
AtcoderのABC98のD問題について,作成したプログラムがシステムテストを通らない(誤りを含む)理由がわかりません.
使用言語はC++です.
方針
満たすべき条件は,与えられた数を二進数表記したときAlからArの各2^kの位について,1であるようなAiが1つ以下であることと同値である.(証明略)
たとえば,
10001
00100
01010
は条件を満たすが,
10001
00100
01011
は条件を満たさない.
ここで,n個の数を2bitで2次元配列で管理する.
ある区間[l,r]で条件をみたすとき,l+1,l+2, ... , r-1も条件を満たすので,
rを固定しそれぞれのrに対して条件を満たす最小のlを求めることでO(n)で実装をする.
発生している問題・エラーメッセージ
基本的な挙動は正しいが,テストセットの一部でWA(誤った解が出力された状態)になる.
該当のソースコード
#include<iostream> #include <stdio.h> #include<string> #include <cmath> #include <algorithm> #include <vector> #include <cstdint> #include <queue> #include <map> #include <set> #define MOD 1000000007 #define FOR(i,a,b) for(int i=(a);i<(b);i++) #define REP(i,n) FOR(i,0,n) #define dump(x) cout << #x << " = " << (x) << endl; #define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl; typedef long long ll; using namespace std; int main(){ int n; cin >> n; // n個の2bit表記 int a[n][20] = {}; REP(i,n){ int num; cin >> num; int bit = 0; while(num != 0){ a[i][bit] = (num % 2); num /= 2; bit++; } } /* REP(i,n){ REP(j,20){ cout << a[i][19-j]; } cout << endl; } */ int ans = 0; int s[20] = {}; // Aは最大20桁までである int count = 1; // 固定したrに対して条件を満たすlの個数 int index = 0; // 現在の条件を満たす区間を最長とするlのインデックス REP(i,n){ int flag = 1; // 条件をみたす? REP(j,20){ s[j] += a[i][j]; if(s[j] > 1) flag = 0; } if(flag == 1) { ans += count; count++; } else{ int Flag = 0; //条件をみたすようになるまでlを進める while(Flag == 0){ Flag = 1; REP(j,20){ s[j] -= a[index][j]; if(s[j] > 1) Flag = 0; } index++; count--; } ans += count; count++; } } cout << ans << endl; return 0; }
回答1件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。