150 : 三角形配列から和が最小となる部分三角形の探索

三角形配列において, 含まれる要素の和が最小となるような部分三角形を求めたい.

下図では, マークされた三角形が, 和が -42 となり, この条件を満たすことは簡単に確かめられる.

1000行の三角形配列を作りたいので, 500500個の値の範囲が±219の擬似乱数$s_k$を以下のような線形合同法によって生成する.

$t := 0$ for k = 1 up to k = 500500:{ $t := (615949 \times t + 797807) \mod 2^{20}$ $s_k := t−2^{19}$ }

よって, $s_1 = 273519, s_2 = −153582, s_3 = 450905, \dots$となる.

三角配列は, 以下のように配置される.

$\begin{array}{c} s_1 \\ s_2 \; s_3 \\s_4 \; s_5 \; s_6 \\s_7 \; s_8 \; s_9 \; s_{10} \\ \vdots \end{array}$

部分三角形は, ある要素から始めて下にいくにつれ広くなっていくようなものを考える. (最初の要素の次の行は2つの要素を含む, その次の行は3つの要素を含む, といったように) "部分三角形の和"はそれが含む全ての要素の和とする. 最小の部分三角形の和を求めよ.