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

GCJ

ビット数

動的計画法。下位の桁をNに一致させて、繰り上がりが無い場合とある場合の、f(a)+f(b)の最大値を覚えてく。もっと綺麗な方法がありそうな気がするが、この解法でもO(桁数)。

# coding: utf-8

def solve(N):
    M = 100
    # [i][j] 下位i-1桁がNと一致し、
    # 繰り上がりが無い場合(j=0)とある場合(j=1)のf(a)+f(b)の最大値
    T = [[-9999]*2 for i in range(M)]
    T[0][0] = 0
    
    for i in range(0,M-1):
        if (N&1<<i)==0:
            T[i+1][0] = T[i][0]                     # 00
            T[i+1][1] = max(T[i][0]+2,T[i][1]+1)    # 10
        else:
            T[i+1][0] = max(T[i][0]+1,T[i][1])      # 01
            T[i+1][1] = T[i][1]+2                   # 11

    return T[M-1][0]

for t in range(input()):
    print "Case #%s: %s" % (t+1,solve(input()))