Codeforces #389 Div2 E. Santa Claus and Tangerines

まんまと想定誤解法に引っかかった。
http://codeforces.com/contest/752/problem/E

問題

だいぶ意訳。

整数の多重集合Sがある。
2以上の要素e∈Sを選び、eを取り除いてfloor(e+1)/2とfloor(e/2)をSに入れる、という処理を任意回数行うことができる。
S中である要素以上の個数がK以上になるようにしたい。そのような要素の最大値はいくつか。

解法

解xを二分探索し、元の入力の整数から、x以上の要素を何個生成できるか…と考えると確かに解けるがTLEする。
そこで、解の候補xを10^7から1まで降順に求めていこう。
sum(P[x...])がK以上となる最大のxを求める。

ここで、今Sに要素eがP[e]個あったとする。
解xがfloor(e/2)以下であれば、eに対し処理を行うことでfloor(e+1)/2とfloor(e/2)をP[e]個ずつ増やすことができる。
なお、処理を行うと元のeが消えるので、解がfloor(e/2)以下である場合のみ、個数がP[e]個増えたと考えることができる。

…というように考えて、各要素の個数および増分をそれぞれ計算していくとよい。
以下のコードでは以下の２値を更新していっている。

• V[e] := 要素数の増分
• W[e] := 増分とみなされない個数

int N,K;
ll V[10000001];
ll W[10000001];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d%d",&N,&K);
	FOR(i,N) scanf("%d",&x), V[x]++;
	
	ll sum=0;
	for(i=10000000;i>=1;i--) {
		sum += V[i];
		if(sum>=K) return _P("%d\n",i);
		V[i]+=W[i];
		W[(i+1)/2]+=V[i];
		V[i/2]+=V[i];
	}
	_P("-1\n");
}

まとめ

難しく考えすぎたな。