Project Euler 253

プロジェクトオイラー
http://projecteuler.net/index.php?section=problems&id=253

最初、どういう問題なのかさっぱりわからなかった。何度も読んでいるうちに意味が分かってきた。
1〜10のカードがでたらめに手元に積んであって、例えば、3,5,9,2,1,4,8,6,7,10と並んでいたとすると、

  3         1 segments

  3 5       2 segments

  3 5   9   3 segments

 23 5   9   3 segments

123 5   9   3 segments

12345   9   2 segments

12345  89   2 segments

123456 89   2 segments

123456789   1 segments

12345678910 1 segments

だから、最大3というわけだ。
そのあと、ジョギングしながら考えた。10枚なら10!通りしかないのだから簡単。サクっと書ける。

from itertools import permutations, imap

from math import factorial
def num_segments(n):

    mode = 0

    while n:

        if n & 1:

            if mode <= 0:

                mode = -mode + 1

        else:

            if mode > 0:

                mode = -mode

        n >>= 1

    return abs(mode)
def gen_num_segments(a):

    n = 0

    for k in a:

        n |= 1 << k

        yield num_segments(n)
def max_segments(a):

    return reduce(max, gen_num_segments(a))
N = 10

n = sum(imap(max_segments, permutations(range(1, N + 1))))

print "%.6f" % (float(n) / factorial(N),)

しかし、40枚となるとそうはいかない。
ちょっと思いついたことがあるので、明日考えようと思う。明日もあまり時間は無いけれど。