Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2011-10-01Google Code Jam Japan 2011 予選

Google Code Jam Japan 2011 予選 C ビット数

| 20:14 | Google Code Jam Japan 2011 予選 C ビット数 - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam Japan 2011 予選 C ビット数 - SRM diary(Sigmar) Google Code Jam Japan 2011 予選 C ビット数 - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

DP

下の桁から順番に、aとbの1,0を決めていく

状態はdp[2][70]で、添字はそれぞれキャリーの有無、桁数を表す

初期状態でdp[0][0]以外は無効な値であることに注意

Nは2進数で最大59桁であるはずだが、念のため61桁まで計算し、最終的にdp[0][61]を解としている

64桁とか計算するとオーバーフローに注意しないといけないので、適度に打ち切る必要がある


ソースコード

int solve(ll N) {
	int res=0;
	
	int dp[2][70];
	memset(dp, -1, sizeof(dp));
	dp[0][0]=0;
	for(int i=0; i<61; i++) {
		if(N&(1LL<<i)) {
			if(dp[0][i]>=0) dp[0][i+1]=max(dp[0][i+1], dp[0][i]+1);
			if(dp[1][i]>=0) dp[0][i+1]=max(dp[0][i+1], dp[1][i]);
			if(dp[1][i]>=0) dp[1][i+1]=max(dp[1][i+1], dp[1][i]+2);
		} else {
			if(dp[0][i]>=0) dp[0][i+1]=max(dp[0][i+1], dp[0][i]);
			if(dp[0][i]>=0) dp[1][i+1]=max(dp[1][i+1], dp[0][i]+2);
			if(dp[1][i]>=0) dp[1][i+1]=max(dp[1][i+1], dp[1][i]+1);
		}
	}

	res=dp[0][61];
	return res;
}

int main() {
	ifstream ifs("input.txt");
	ofstream ofs("output.txt");

	int testcase;
	ifs >> testcase; ifs.ignore();
	for(int testnum=1; testnum<=testcase; testnum++) {
		ll N;
		ifs >> N;
		int res=solve(N);
		ofs << "Case #" << testnum << ": ";
		ofs << res << endl;
	}
}
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20111001