Div2 Dの割に実装は簡単。
http://codeforces.com/contest/567/problem/D
問題
1次元の戦艦ゲームを考える。
1列にNマスのマスが並んでおり、そこにサイズAマス分の戦艦を配置していく。
各戦艦は同じマスを共有することもできないし、間に空きマスなしで隣接させることもできない。
先手がNマスに戦艦をK個配置した後、後手がそれを撃沈させるゲームを行った。
後手はM箇所のマスを指定して攻撃したところ、先手はすべて攻撃は失敗(指定したマスに戦艦はない)と答えた。
そんなことがあるだろうか。
先手が嘘をついている可能性がある攻撃回次があれば、それを答えよ。
解法
攻撃の結果、戦艦をK個置けなくなるなら、先手は嘘をついていると考えてよい。
B個の空きマスが連続している場合、そこにおける戦艦は(B+1)/(A+1)個である。
後は連続した空きマスの集合をsetなどで管理し、攻撃の際に戦艦数を再計算してK個以上おけるか置けないか判定すればよい。
int N,K,A,M; int X[202020]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>K>>A>>M; set<int> S; S.insert(0); S.insert(N+1); int num=(N+1)/(A+1); FOR(i,M) { cin>>X[i]; auto it=S.lower_bound(X[i]); auto it2=it; it--; num -= (*it2-*it-1+1)/(A+1); num += (X[i]-*it-1+1)/(A+1); num += (*it2-X[i]-1+1)/(A+1); S.insert(X[i]); if(num<K) return _P("%d\n",i+1); } _P("-1\n"); }
まとめ
戦艦は隣接配置できないって制限、必要だったのかなぁ。