Codeforces #314 Div2 D. One-Dimensional Battle Ships

Div2 Dの割に実装は簡単。
http://codeforces.com/contest/567/problem/D

問題

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");
	
}

まとめ

戦艦は隣接配置できないって制限、必要だったのかなぁ。