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)))