Project Euler 301

http://projecteuler.net/index.php?section=problems&id=301

6時前に目が覚めて問題文を見る。長い。読もうとするが、眠くてなかなか進まない。問題文を読み終えて、特になにも思いつかないので、もっとも原始的にコーディングしてみる。

def X(stones):
    if stones == (0, 0, 0):
        return False
    
    def gen(ss):
        for k in range(3):
            for p in xrange(ss[k]):
                yield ss[:k] + (p,) + ss[k+1:]
    
    return any(not X(ss) for ss in gen(stones))

N = 5
print sum(X((n, n * 2, n * 3)) for n in xrange(1, N + 1))

これで11秒。

やっぱり、このパターンだったか。最後は範囲がヒントになる。
フォーラムを見たが、みんな元々知っている問題だったんだね。自分と同じやり方の人はいなさそう。答えは一瞬で出る。
星になりました。いまのところ26人らしい。今まではLegendだったけど、Veteransに。語感としては格下げのような気が。もう順番はつかないらしい。一丁上がりってことか。
フォーラムに驚愕の解法が書かれていた。しかし、数学的に簡単に確かめられた。よく考えたら、ほかの部分も数学的にクリアになった。