CODE FESTIVAL 2017 Qual A : F - Squeezing Slimes

コードは割と単純。
http://code-festival-2017-quala.contest.atcoder.jp/tasks/code_festival_2017_quala_f

問題

N要素の数列Aが与えられる。
またBをAの総和とする。

最初、1がB個からなる数列があったとする。
このうち、偶数個からなる部分列を選ぶと、その部分列は以下のように変化する。

• 先頭から２個ずつ要素をペアにし、それらの和からなる要素に置き換える。

すなわち部分列の大きさは半分になる。

上記処理を繰り返し、Aを構築するには最小で何回部分列を変化させる処理が必要か。

解法

各A[i]について、A[i]個の葉を持つ2分木を考えよう。
葉に1、親頂点に子頂点の数字の和を書くようにすると、この二分木は元数列からA[i]を構築していく様子を表すものと言える。

問題の部分列を選ぶ処理は、連続した偶数個の葉を選び、それらを削除する処理に相当する。
これを繰り返し、最終的にA[i]が1個残ればよい。

二分木におけるA[i]個の各葉の高さをD[i][j]とする。
上記考え方をすると、できるだけ葉の高さを均しておいた方がよさそうということが推測できる。
よってD[i][j]はfloor(log(A[i]))かceil(log(A[i]))となるのが良く、floorとceilの値はそれぞれ前後半どちらかに固まるのが良い。

よってあとは単純なDPで、floorな値を手前に持ってきた場合と、ceilな値を手前に持ってきた場合でそれぞれA[0]～A[i]までに対し置き換えを実施する回数の最小値を求めて行くとよい。

int N;
int A[101010];
int L[101010],R[101010];
int dp[101010][2];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	N+=2;
	FOR(i,N) {
		if(i==0 || i==N-1) A[i]=1;
		else cin>>A[i];
		while(1<<(L[i]+1)<=A[i]) L[i]++;
		R[i]=L[i];
		if(A[i]&(A[i]-1)) R[i]++;
		
		if(i) {
			dp[i][0]=(R[i]-L[i])+min(dp[i-1][0]+abs(L[i]-R[i-1]),dp[i-1][1]+abs(L[i]-L[i-1]));
			dp[i][1]=(R[i]-L[i])+min(dp[i-1][0]+abs(R[i]-R[i-1]),dp[i-1][1]+abs(R[i]-L[i-1]));
		}
	}
	
	cout<<(min(dp[N-1][0],dp[N-1][1])+1)/2<<endl;
	
	
}

まとめ

こんな簡単な式になるのか…。