Google Code Jam Japan Qual C: ビット数

GCJ

問題概要

a + b = N(<10^12)を満たすようにpopcount(A) + popcount(B)を最大化する問題。

考えたこと

  • とりあえずsmallは本当に書くだけなのでさっさと書く。
  • Dに64ビットのpopcntが無かったので真面目に書く。
  • largeを考えよう。こういうのは大抵桁でDPだ。
  • でももっと楽に行けそう。片方は111..11になるように仮定して良さそう。
  • もう少し真面目に考えると、基本的に立っている方のビットは片方に押し付けて良いし、途中に両方ビットが0になってるようなものがあれば上のビットから1を借りてきて今のビットで1,1に分けた方が良い。
  • やっぱり64ビットでのcountLeadingZero的なものはないので愚直に全通り試す。計算量は落ちるけど十分。

通ったコード

small

import std.stdio;
import std.algorithm;

int nextInt(){
	int x;
	scanf("%d",&x);
	return x;
}

int popCount(long x){
	int ret = 0;
	for( ; x > 0 ; x>>=1){
		ret += x&1;
	}
	return ret;
}

int solve(long x){
	int ret = 0;
	for(auto i = 0; i <= x; i++){
		ret = max(ret, popCount(i) + popCount(x-i));
	}
	return ret;
}

void main(){
	for(auto c = 1, T = nextInt; c <= T; c++){
		writef("Case #%d: %d\n", c, solve(nextInt));
	}
}

large

import std.stdio;
import std.stream;
import std.algorithm;

long nextLong(){
	long x;
	scanf("%lld", &x);
	return x;
}

int popCount(ulong x){
	int ret = 0;
	for( ; x > 0 ; x>>=1){
		ret += x&1;
	}
	return ret;
}

int solve(ulong x){
	int ret = 0;
	for(int i = 0; i<63; i++){
		auto y = (1L<<i)-1;
		if(x >= y){
			ret = max(ret, popCount(x - y) + popCount(y));
		}
	}

	return ret;
}

void main(){
	for(auto c = 1, T = nextLong; c <= T; c++){
		writef("Case #%s: %s\n", c, solve(nextLong));
	}
}