Problem 14

大抵過去のソースより短く，（すっきり）するか速くなるんだけど（あるいは両方）今回のだけは力を入れてたこともあって，全然改良できなかった…．lambdaいれてみたんだけど結果遅くなったし．（短くなって良いかなぁとは思ったんだけど）関数呼び出しと同じような扱い？全部インライン展開したら速くなるのかな？まさかｗｗｗいやそんなのはもうだめだ．ヤメよう．

def count_terms(N,lis):
    i = 0
    while N != 1:
        if N < len(lis) and lis[N]:
            i += lis[N]
            break
        if N & 1:
            N += (N<<1) + 1
        else:
            N >>= 1
        i += 1
    return i

limit = 10 ** 6
chk = [0 for i in xrange(limit)]
i = 1
while 2<<i <limit:
    chk[2<<i] = i
    i += 1

for i in xrange(2,limit/2):
    if not chk[i]:
        t = 1
        chk[i] = count_terms(i,chk)
        while i<<t < limit:
            chk[i<<t]=chk[i] + t
            t += 1

for i in xrange(limit/2 + 1,limit,2):
    if not chk[i]:
        chk[i] = count_terms(i,chk)
print chk.index(max(chk))

小賢しく少しでも速くなるようにシフト演算とか入れてみたけど，うん．0.1秒ほどの効果．自分の環境だと3.5秒前後です．
codepadでtimeoutにならないから一応合格．（あれを目安にしています一応）
やっていること．2の指数は指数部がそのまま入る．あとは必要な値の半分を先に埋めて，埋まった奴は2,4,8倍みたいな感じで値を指数部分足す．カウントを数えて既に数えた数を見つけたらその時の値を入れるとかそういうことやっている？と信じている！でここまで頑張っても，スレッドの最初にあったCの愚直ソースが0.6秒…．自分の環境でも1-2秒(体感)．Pythonに移植すると30秒超えるｗｗｗ見た目はこんな感じ．

term = 0
for i in range(1,10**6):
    j = i
    this_term = 1
    while j != 1:
        this_term += 1
        if this_term > term:
            term = this_term
            longest = i
        if j % 2:
            j = 3 * j + 1
        else:
            j >>= 1
print longest,term

こんなので1秒いけるのかと…．コンパイラってSUGEEEEE.