GoogleCodeJamJapan予選

参加しました.
13時開始で,14時頃に外出しなければなかったという事件（参加登録してから気づいた）

問題はABCの3種類,それぞれにSmallとLargeという2つの制約があり,愚直に書くとSmallは解けるがLargeは一捻りいる感じ.
ただし,Largeはコンテストが終わるまで正解か分からない.
3問中1問でもLargeが解ければ決勝に出場出来るらしい.

気づくと13時15分になってたので慌てて参加.
Aを見て問題を理解するも,Largeが解ける解法を思いつかなかったのでパス.
Cを開く,問題理解
数字Nが与えられ,a+b=Nを満たすa,bの1のビット数が最大となるとき1のビット数を答える問題.
紙の上で1から6まで解答してみる.
全てのビットが１の数(2^n-1)のうち,N以下で最大の物と,残り.で解けそうな気がする.
サンプルのケースで実験も出来るだろうという甘い考えの元,ダラダラと書く.

#include <iostream>
using namespace std;
typedef unsigned long long uint;

int bitCount(uint x){
    int count = 0;
    for(uint mask = 1; mask != 0; mask <<= 1) {
        if( (x & mask) != 0 ) count += 1;
    }
    return count;
}

int main(){
	uint n,t;
	cin >> t;
	for(int i=0;i<t;++i){
		cin >> n ;
		uint k=0,j;
		while( ( n > (((uint)1<<(++k))-1) ) );
		k-=1;
		n -= (((uint)1<<k)-1);
		k += bitCount(n);
		cout << "Case #" << i+1 << ": " << k << endl;
	}
}

1のビット数を数えるのにstd::bitsetが使えそうなのは知ってたけど,使った事なかったのでヤメ.
「ビット数　数える　C言語」とかいうナメたワードでググッて見つけたソースをコピペしてちょいちょいと書き換えた.
サンプル合った.
Small正解.
Large提出.

この時点で14時前だったので，Aを愚直に書いてみたりしたがサンプル合うのにSmall通らなくて涙目．
時間過ぎてたのでしぶしぶと外出．

後々確認してみるとC-Large通ってたようで良かった．
542位という素晴らしい成績で決勝進出のようです．

Tシャツ欲しいよ！