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

ということでA問題に続き，C問題をやってみました．これはlargeが解けるように書き直しました．というか，smallのときに書いたコードをそのまま書き換えてしまったので，当日のコードを自分で無くすというバカなことをしてしまいました．

#! c:/Python27/python.exe
# -*- coding: utf-8 -*-

input  = 'C-large-practice.in'#'C-small-attempt0.in'#'A-large.in'
output = 'gcjj2011_0C_output.txt'

def step(N):
    i = 0
    while N >= 2**i:
        i = i + 1
    #return i - 1
    num1 = 2**(i-1) - 1
    num2 = N - num1
    binaryNum1 = format(num1, "b")
    binaryNum2 = format(num2, "b")
    count1 = binaryNum1.count("1")
    count2 = binaryNum2.count("1")
    countSum = count1 + count2
    return countSum

if __name__ == '__main__':
    f = open(input)
    fout = open(output,'w')

    a = int( f.readline() )
    for i in range(a):
        #line = f.readline().split()
        N = int( f.readline() )
        result = step(N)
        print "Case #"+str(i+1)+": " + str(result)
        fout.write("Case #"+str(i+1)+": " + str(result) + '\n')
    fout.close()

考え方としては2つの数字のうち，一方はすべて1にしておくのが最適なので（たとえばN=12であれば12を超えない最大の(2進法で)1ばかりの数，つまり2^3 - 1 = 7 = 111と5 = 101に分ければよいので）結局，ある数Nに対してNを超えない2^x - 1のxを求めればよいとわかります．という方針でコードを書きました．

うーん，ちゃんと考えれば全然本戦に進めるということが今回やってみてわかりました．あまり勝手に難しすぎると考えすぎない方がよいようです．．．．