Codeforces #419 Div1 E. Karen and Neighborhood

簡単そうに見えて意外と手こずった。
http://codeforces.com/contest/815/problem/E

問題

1～Nの家が順に並んでいる。
ここにN人の人が順次やってきて、家に入っていく。
最初に来た人は、1番の家に入る。
以降に来た人は、最寄の人がいる家までの距離が最大となる家に入る。距離が同着の家が複数ある場合、番号が最も小さい家に入る。

K番目に来た人はどの家に入るか答えよ。

解法

K=1,2の時は自明。
以降、[2,N-1]の範囲に人が入っていくことを考える。

まず、二分探索でK番目の人が入る家は最寄の家までの距離がどうなるかを求めよう。
以下の情報をメモ化再帰で求めることでこれは容易に求められる。
f(A,B) := 連続してA個の空き家があるとき、最寄の家までの距離がB以上であるようにするため何人まで人が入れるか

得られた距離の下限がDとする。
今[L,R]の区間が空いているとき、その中でx番目に来る人がどこに入るかを考える。
M=(L+R)/2とすると、x=1の時その人はMに入る。
x＞1の時、[L,M-1]と[M+1,R]のどちらに入るかを考えよう。

二分探索の結果より、xの人が家に入るとき、最寄りの家までの距離はDである。
逆に(D+1)以上の距離が出る間は絶対にx番の人は入らない。
仮に[L,M-1]側に入る場合、右側にf(R-M,D+1)分の人が入るので、あとは[L,M-1]の間で(x-f(R-L,D+1))番目の人がどこに入るか考えればよい。
逆に[M+1,R]側に入る場合、左側にf(M-L,D)分の人が入るので、あとは[M+1,R]の間で(x-f(M-L,D))番目の人がどこに入るか考えればよい。
どっちに入るかは、xが1+f(M-L,D)+f(R-M,D+1)より大きいか小さいかでわかる。

ll N,K;
map<pair<ll,ll>,ll> memo;

ll hoge(ll S,ll m) {
	if(S==0) return 0;
	if(memo.count({S,m})) return memo[{S,m}];
	
	ll ret=0;
	ll sm=(S-1)/2;
	ll la=S-1-sm;
	if(sm<m) return 0;
	ret = 1+hoge(sm,m)+hoge(la,m);
	return memo[{S,m}]=ret;
}

ll pos(ll L,ll R,ll low,ll K) {
	ll M=(L+R)/2;
	if(K==1) return M;
	K--;
	
	ll ns=hoge(M-L,low);
	ll nl=hoge(R-M,low+1);
	if(ns+nl>=K) {
		return pos(L,M-1,low,K-nl);
	}
	else {
		return pos(M+1,R,low,K-ns);
	}
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	if(K==1) {
		cout<<1<<endl;
	}
	else if(K==2) {
		cout<<N<<endl;
	}
	else {
		K-=2;
		ll L=0,R=N+1;
		while(L+1<R) {
			ll M=(L+R)/2;
			if(hoge(N-2,M)>=K) L=M;
			else R=M;
		}
		cout<<pos(2,N-1,L,K)<<endl;
	}
	
}

まとめ

シンプルな問題設定ながら面白い解法でいいね。