UVa First Bangladeshi Contest of 2012-2013 Season Problem (D) Draw and Score

問題

二分木を根のノードから書いていく。
二分木がバランスしているとは、
根が2つの子を持ち、それぞれの子を根とする部分木の大きさが等しいことを言う。

ノードを書いた後で、どれかを根とする部分木がバランスしたとき、
スコアに1点を加算する。
（複数の部分木がバランスした場合はその個数だけ点数を加算する）

N個のノードを書くとき、得られる最大の点数はいくつか、求めよ。

制約条件

N≦10^15

方針

根の左の子の個数をl, 右の子の個数をrとすると、
木が（根で）バランスする回数は最大でmin(l, r)回。

lを0からN-1まで試すと、左右の子のバランスする回数は
同じ問題で部分問題になるので、再帰により最大のスコアが求められる。

この再帰はメモ化して計算量がO(N^2).
OEISで回数の数列を調べたら、
0からNまでを二進法で書いたときに出現する1の数 - Nというのがこの数列の一般項らしい。
なのでそれをDPで求める。

このDPは典型的な桁DP.
（今までの合計と、場合の数を覚えておいて、今までの合計に加えて、場合の数x新たに加わる数を足していくようなDP)

ソースコード

int n, d[70];
ll dp[71][2], way[71][2];

int main()
{
	int CS;
	scanf("%d", &CS);
	
	rep(cs, CS){
		ll n, N;
		scanf("%lld", &n);
		memset(way, 0, sizeof(way));
		memset(dp, 0, sizeof(dp));
		
		N = n;
		rep(i, 70) d[69 - i] = n % 2, n /= 2;
		
		way[0][0] = 1;
		rep(i, 70) rep(s, 2) if(way[i][s]){
			rep(j, 2){
				int ns = s || j < d[i];
				if(!ns && j > d[i]) continue;
				way[i + 1][ns] += way[i][s];
				dp[i + 1][ns] += dp[i][s] + j * way[i][s];
			}
		}
		ll ans = dp[70][0] + dp[70][1] - N;
		
		printf("Case %d: %lld\n", cs + 1, ans);
	}
	
	return 0;
}