京都大学プログラミングコンテスト2015

Submission #534852

Source codeソースコード

#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <utility>
#include <sys/time.h>

using namespace std;
typedef long long ll;

ll dp[64][64][64][2];
const ll INF = 1ll << 62;

ll solve() {
	ll N;
	cin >> N;
	int S = 1;
	for (int i = 0; ; ++i) {
		if ((1ll << i) > N) {
			S = i;
			break;
		}
	}
	for (int i = 0; i < 64; ++i) {
		for (int j = 0; j < 64; ++j) {
			for (int k = 0; k < 64; ++k) {
				dp[i][j][k][0] = INF;
				dp[i][j][k][1] = INF;
			}
		}
	}

	dp[0][0][0][0] = 0;
	for (int i = 0; i <= S; ++i) {
		for (int j = 0; j <= S; ++j) {
			for (int k = 0; k <= S; ++k) {
				if (dp[i][j][k][0] == INF && dp[i][j][k][1] == INF) continue;
				if ((N & (1L << i)) == 0) {
					dp[i + 1][j + 0][k + 0][0] = min(dp[i + 1][j + 0][k + 0][0], dp[i][j][k][0]);
					dp[i + 1][j + 0][k + 1][0] = min(dp[i + 1][j + 0][k + 1][0], dp[i][j][k][1]);
					dp[i + 1][j + 1][k + 1][0] = min(dp[i + 1][j + 1][k + 1][0], dp[i][j][k][0] + (1L << i));
					dp[i + 1][j + 1][k + 0][1] = min(dp[i + 1][j + 1][k + 0][1], dp[i][j][k][1] + (1L << i));
				} else {
					dp[i + 1][j + 0][k + 1][0] = min(dp[i + 1][j + 0][k + 1][0], dp[i][j][k][0]);
					dp[i + 1][j + 0][k + 0][1] = min(dp[i + 1][j + 0][k + 0][1], dp[i][j][k][1]);
					dp[i + 1][j + 1][k + 0][1] = min(dp[i + 1][j + 1][k + 0][1], dp[i][j][k][0] + (1L << i));
					dp[i + 1][j + 1][k + 1][1] = min(dp[i + 1][j + 1][k + 1][1], dp[i][j][k][1] + (1L << i));
				}
			}
		}
	}
	ll ans = INF;
	for (int i = 1; i <= S; ++i) {
		ans = min(ans, dp[S + 1][i][i][0]);
	}
	return ans;
}


int main() {
	int T;
	cin >> T;
	for (int i = 0; i < T; ++i) {
		cout << solve() << endl;
	}
}


Submission

Task問題 H - Bit Count
User nameユーザ名 tomerun
Created time投稿日時
Language言語 C++11 (Clang++ 3.4)
Status状態 AC
Score得点 300
Source lengthソースコード長 1781 Byte
File nameファイル名
Exec time実行時間 169 ms
Memory usageメモリ使用量 5016 KB

Test case

Set

Set name Score得点 / Max score Cases
All 300 / 300 00_sample.txt,10_small_00.txt,20_medium_01.txt,20_medium_02.txt,20_medium_03.txt,30_large_04.txt,30_large_05.txt,30_large_06.txt,80_power_of_2.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
00_sample.txt AC 35 ms 4896 KB
10_small_00.txt AC 86 ms 4772 KB
20_medium_01.txt AC 77 ms 4892 KB
20_medium_02.txt AC 81 ms 5016 KB
20_medium_03.txt AC 77 ms 4892 KB
30_large_04.txt AC 169 ms 4848 KB
30_large_05.txt AC 166 ms 4900 KB
30_large_06.txt AC 153 ms 4900 KB
80_power_of_2.txt AC 34 ms 4768 KB