Codeforces #1068 : Div2. D. Taiga's Carry Chains

Dまでは順調だったんだけどね。
https://codeforces.com/contest/2173/problem/D

問題

整数N,Kが与えられる。
Nに２の累乗を１つ選んで加算する、という作業をK回繰り返す。
Nを２進数とみなしたとき、繰り上げの回数の総和の最大値を求めよ。

解法

Nを２進数表記したとき、少なくともどこか１か所はビットが立っているので、そのうちどこかに合わせた２の累乗を加算するとよい。
この作業を繰り返すと、Nはいずれ２の累乗になる。
その後は１回の作業で１回繰り上がり確定である。

よって、それまでの間、具体的にはNが2^30を超えるまでの間、どこで加算すると繰り上がり回数が最大になるかをDPで求めよう。

int T;
int N,K;

int dp[32][32][2];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>K;
		
		FOR(x,32) FOR(y,32) dp[x][y][0]=dp[x][y][1]=-1<<30;
		dp[0][0][0]=0;
		FOR(x,30) FOR(y,30) FOR(k,2) {
			if((N>>x)%2+k>=2) {
				dp[x+1][y][1]=max(dp[x+1][y][1],dp[x][y][k]+1);
			}
			if((N>>x)%2+k>=1) {
				dp[x+1][y+1][1]=max(dp[x+1][y+1][1],dp[x][y][k]+1);
			}
			dp[x+1][y][0]=max(dp[x+1][y][0],dp[x][y][k]);
		}
		int ret=0;
		FOR(i,31) if(i<=K) {
			ret=max(ret,dp[30][i][0]);
			ret=max(ret,dp[30][i][1]+K-i);
		}
		cout<<ret<<endl;
			
		
	}
}

まとめ

ここはすんなり。