Google Code Jam 2021 Round 1C : A. Closest Pick

まだCは解いてないけど。
https://codingcompetitions.withgoogle.com/codejam/round/00000000004362d7/00000000007c0f00

問題

1～Kのマスが並んでおり、先手がうちいくつかのマスを選んでいる。
ここで、後手は2つのマスを選ぶことを考える。

その後、1～Kのいずれかの値cがランダムに選択される。
もし、後手が選んだマスが、先手が選んだマスよりc番目のマスに最寄りなら後手が勝つ。
後手の選び方を最適化したとき、勝率はどうなるか。

解法

先手の選んだマスで区切られた、各区間について考える。

• 最初の先手の選択マスの手前と、最後の先手の選択マスの後は、後手が1マス選択すれば区間内のどこが選ばれても後手が勝つ。
• それ以外は、後手が区間内で２マス選択すれば区間全体、1マス選択すれば区間の半分の確率で後手が勝つ。

ということで、1つの区間を2マス選択で全体を確保するケースと、1マス選択で得られる区間長のうち上位2つを選ぶケースのうち最大値を答えよう。

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	int N,K;
	vector<int> P;
	cin>>N>>K;
	FOR(i,N) {
		cin>>x;
		P.push_back(x);
	}
	sort(ALL(P));
	vector<int> cand;
	cand.push_back(P[0]-1);
	cand.push_back(K-P.back());
	int ma=0;
	FOR(i,P.size()-1) {
		int d=P[i+1]-P[i];
		ma=max(ma,d-1);
		if(d>1) cand.push_back(d/2);
	}
	sort(ALL(cand));
	reverse(ALL(cand));
	ma=max(ma,cand[0]+cand[1]);
	
	_P("Case #%d: %.12lf\n",_loop,1.0*ma/K);
}

まとめ

なんで今回1Bと1Cの間隔妙に短いんだろう。