Codeforces #880 : Div1 B. Lottery

非常に出来の悪かった回。
https://codeforces.com/contest/1835/problem/B

問題

0～Mのいずれかの値を出すくじを考える。
すでにN人の参加者がおり、それぞれ0～Mのいずれかの値を選択済みである。

くじを引くと0～Mの範囲のいずれかの整数Xが等確率で出る。
その時、Xから近い値を選択したK人があたりとなる。
(タイの場合は、参加者番号が小さい人が勝ち)

今N+1人目が、できるだけ当たりとなる確率を増やしたいとき、どの値を選択すべきか。
ベストとなる選択値と、その時のXの値の数を求めよ。

解法

今位置Cを選んだ時、左右それぞれ最寄りのK人目の選んだ値をA,Bとする。
この時、((A+C)/2,(B+C)/2)の範囲の値が出たらCはあたりとなる。

ここから逆に、誰と誰の間にCを取るかを決めると、A,Bが決まり、あたりとなるXが決まる。
よってそのようなCの位置を総当たりしていこう。

ll N,M,K;
ll X[1010101];

ll hoge(ll v) {
	int a=lower_bound(X,X+N,v)-X;
	int b=lower_bound(X,X+N,v+1)-X;
	
	ll L=(b<K)?0:(v+X[b-K])/2+1;
	ll R=(a+K-1>=N)?M:(v+X[a+K-1]-1)/2;
	return R-L+1;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>K;
	FOR(i,N) cin>>X[i];
	sort(X,X+N);
	
	pair<ll,ll> ret={hoge(0),0};
	
	FOR(i,N) {
		ll L=(i==0)?max(0LL,X[i]-2):max(X[i]-2,X[i-1]+3);
		ll R=min(M,X[i]+2);
		for(ll a=L;a<=R;a++) {
			ll v=hoge(a);
			if(v>ret.first) {
				ret.first=v;
				ret.second=a;
			}
		}
	}
	cout<<ret.first<<" "<<ret.second<<endl;
}

まとめ

コードはともかく考察がちょっとめんどい。