CROC 2016 Elimination Round : C. Enduring Exodus

Eに時間かけすぎて、一応A-Eは解けたけどレート微増にとどまった。
http://codeforces.com/contest/655/problem/C

問題

N個のマスが並んでいる。
一部のマスは埋まっており、一部は空いている。
空いているマスのうち(K+1)箇所を選択し、1マスには人を、残りKマスには牛を配置したい。
最適な配置をしたとき、人から最も遠い牛までの距離を最小化せよ。

解法

(最初から埋まったマスは除き)連続した空きマスを(K+1)個使うのが良いのは自明だろう。
あとはどの連続(K+1)マスを使うか、また(K+1)マスのうち人をどこに配置するのかを求めればよい。

よくみられる解法は以下の何れか。

• 尺取法の要領で、(K+1)マス分の(埋まったマスを無視した)連続空きマスについて順次処理する。
  • (K+1)マス分の空きマスのうち、lower_bound等を使ってもっとも両端の真ん中に近いマスを求め、そこに人を背理する。
• 各空きマスに人を配置した場合、二分探索で半径d以内の空きマスが(K+1)個以上になるようなdを求める。

以下のコードは後者。

int L,K;
string S;
int sum[101010];

int ok(int cur,int d) {
	int l=max(0,cur-d);
	int r=min(cur+d,L-1);
	return (sum[r+1]-sum[l])>=K+1;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>L>>K>>S;
	FOR(i,L) sum[i+1]=sum[i]+(S[i]=='0');
	
	int mi=1<<30;
	FOR(i,L) if(S[i]=='0') {
		int ret=1<<20;
		for(j=19;j>=0;j--) if(ok(i,ret-(1<<j))) ret-=1<<j;
		mi=min(mi,ret);
	}
	cout<<mi<<endl;
}

まとめ

これはすんなり。