*[[Problem 149:http://projecteuler.net/problem=149]] 「和が最大となる部分列の探索」 [#q0ee6343]

下の表において, 任意の方向(縦横斜め)に隣り合うものの和の最大値は16 (= 8 + 7 + 1)となることは簡単に確かめられる.
|-2|5|3|2|
|9|-6|5|1|
|3|2|7|3|
|-1|8|-4|8|

いま, 同じ探索をより大きなものについてもしてみることにする.

まず, 400万個の擬似乱数を"Lagged Fibonacci Generator"によって生成する.

1 ≤ k ≤ 55 について, &tex{s_{k} = [100003 - 200003k + 300007k^{3}] (modulo 1000000) - 500000}; ~
56 ≤ k ≤ 4000000 について, &tex{s_{k} = [s_{k-24} + s_{k-55} + 1000000] (modulo 1000000) - 500000};

つまり, &tex{s_{10} = -393027 , s_{100} = 86613}; となる.

s の項は, 最初の2000個を最初の行に(順番に), 次の2000個を2番目の行に, というように, 2000x2000の表に並べ替えられる.

任意の方向(縦横斜め)に隣り合うものの和の最大値を求めよ.
(連続して足す領域は3マス以上でもよい, 斜め4マス等も認める)



トップ   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS