Codeforces #380 Div1 B. Sea Battle

なんか簡単だと思ったら750ptだった。
http://codeforces.com/contest/737/problem/B

問題

１次元の戦艦ゲームを考える。
1*NのグリッドがありそこにA個の戦艦がいる、それぞれは連続するBマス分の大きさである。
いくつかのマスを狙い撃ち、戦艦のいるマスを当てたい。
すでにいくつかマスを狙い撃っており、それらはすべて外れたことがわかっている。

最善手を打った場合、最悪ケースで残り何マス撃てば戦艦のいるマスを最低１つ当てられるか。

解法

連続マスがB個あるごとに撃っていけばよい。
そのようなマスがC個ある場合、残りA-1個になるタイミング、すなわち(C-(A-1))発目で戦艦に当てることができる。

int N,A,B,K;
string S;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>A>>B>>K>>S;
	x = 0;
	vector<int> V;
	FOR(i,N) {
		if(S[i]=='0') {
			x++;
			if(x==B) {
				V.push_back(i+1);
				x=0;
			}
		}
		else {
			x=0;
		}
	}
	
	_P("%d\n",V.size()-A+1);
	FOR(i,V.size()-A+1) _P("%d%c",V[i],(i==V.size()-A)?'\n':' ');
	
}

まとめ

なんかこういう戦艦ゲーはCodeforcesに多いイメージ。AtCoderでも出たっけ？