CSAcademy Round #71 : D. Russian Dolls

少し手間取ったけどまぁ何とか。
https://csacademy.com/contest/round-71/task/russian-dolls/

問題

N個のマトリョーシカがあり、それぞれのサイズはA[i]である。
あるサイズのマトリョーシカの中には、それより小さいマトリョーシカを１つ入れることができる。
（中に入れるマトリョーシカの中に、さらに小さいマトリョーシカが入っていてもよい）

ここで、サイズKのマトリョーシカが１個あったとき、(K-1)のマトリョーシカを2個と交換できる。
これらのマトリョーシカをできるだけ入れ子にし、総数を最小化したい。
最小値はいくつか。

解法

最大サイズのマトリョーシカが十分あれば、他のマトリョーシカはすべて入る。
初期状態でマトリョーシカの最大サイズがSのとき、交換を繰り返して全て(S-k)のマトリョーシカにするとそのようなマトリョーシカは初期の最大サイズのものの2^k倍個程度になる。
よって、最大サイズが(S-20)～S程度のケースを総当たりし、それらの中に他のマトリョーシカをすべて押し込めることができるか考えよう。

今最大サイズがSでその個数がC(S)とする。
(S-1)以下のサイズのマトリョーシカが、いずれもC(S)個以下になるようにしたい。
溢れそうなら１つ小さいサイズのものに交換する。
問題はSが非常に大きいことで、O(S)をまともに処理するとTLEする。
そのため飛ばし飛ばし処理しよう。
今C(k)=2*C(S)個ある場合、半分はそのサイズを維持してもよいが残り半分は交換しなければならず、その場合C(k-1)が2*C(S)個増える。
またC(k)が2*C(S)個より多い場合、C(k-1)が2*C(S)個以上増え最終的に条件を満たせない。
これらを踏まえて条件を満たせるかどうか判定しよう。

int N;
int A[101010];
map<int,int> M;

ll hoge() {
	int pre;
	int first=1;
	ll w,left=0;
	ll ret=0;
	int i;
	FORR(m,M) {
		if(first==1) {
			w=m.second;
			first=0;
		}
		else {
			int dif=abs(pre+m.first);
			if(left>w) {
				if(left==w*2) {
					ret+=w*dif;
				}
				else {
					FOR(i,dif) {
						if(left<=w) {
							left=0;
							break;
						}
						ret+=left-w;
						left=(left-w)*2;
						if(left>w*2) return -1;
					}
				}
			}
			else {
				left=0;
			}
			left+=m.second;
		}
		pre=-m.first;
	}
	if(left>w) {
		if(left>=w*2) return -1;
		FOR(i,pre) {
			if(left<=w) {
				left=0;
				break;
			}
			ret+=left-w;
			left=(left-w)*2;
			if(left>w*2) return -1;
		}
		if(left) return -1;
	}
	
	return ret;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>x, M[-x]++;
	
	ll ret=1LL<<60,step=0;
	while(M.size()>1) {
		if(step>ret) break;
		ll tmp=hoge();
		if(tmp>=0) {
			ret=min(ret,step+tmp);
		}
		auto it=M.begin();
		step+=it->second;
		M[it->first+1]+=it->second*2;
		M.erase(M.begin());
	}
	ret=min(ret,step);
	
	cout<<ret<<endl;
	
}

まとめ

問題設定は単純だけど結構実装が面倒くさい。