Project Euler 150

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


Pythonってこういう書き方ができたんですね。知らなかった。

    for (i, j), s in izip(gen_index(N), gen_pseudo_random()):

これとの連想で、ラムダでもこういう書き方ができます。

    lambda (i, j): i + j, ...

さて、この問題は単純に考えればO(n3)です。そこで、O(n2)にならないか考えたのですが、ダメでした。素直に組んで、5分弱でした。C++なら恐らく5秒もかからないでしょう。

from itertools import *

def gen_pseudo_random():
    D = 2 ** 20
    S = 2 ** 19
    t = 0
    while True:
        t = int((615949 * t + 797807) % D)
        yield t - S

def gen_index(N):
    return ((i, j) for i in xrange(N) for j in xrange(i + 1))

def make_triangle(N):
    a = [ [ 0 ] * k for k in xrange(1, N + 1) ]
    for (i, j), s in izip(gen_index(N), gen_pseudo_random()):
        a[i][j] = s
    return a

def make_sum_edge(a):
    N = len(a)
    b = [ [ 0 ] * (k + 1) for k in xrange(1, N + 1) ]
    for i in xrange(N):
        s = 0
        for j in xrange(i + 1):
            s += a[i][j]
            b[i][j+1] = s
    return b

def calc_min_triangle(i, j):
    s = 0
    m = 0
    for k in xrange(i, N):
        s += b[k][k-i+j+1] - b[k][j]
        m = min(m, s)
    return m

N = 1000
a = make_triangle(N)
b = make_sum_edge(a)
print reduce(min, starmap(calc_min_triangle, gen_index(N)))