前回は、Project Euler で紹介されている問題18を解いてみました。視点を変えて、うまく解答を求めることができたので、その方法を紹介します。
再掲載 Project Euler 問題18（最大の経路和Ⅰ）
下の三角形の頂点から始めて、下の行の隣り合う数字に移動することで、上から下への合計の最大が23になる。
3
7 4
2 4 6
8 5 9 3
赤字の経路の 3 + 7 + 4 + 9 = 23 となる。
下の三角形の上から下への合計の最大を求めよ。
75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
注：経路は、16384通り（214）しかないため、すべてのルートを試せば、この問題を解くことができます。しかし、問題67は、三角形が100行になるため、すべての経路を計算することができないので、別の賢い方法が必要となります。;o)
考察（視点を変える）
前回は、bit全検索を使って、214通りのすべての合計を計算して、最大値を求めました。問題の注にも記載がありますが、問題67は、これと同じ趣旨で三角形が100行になっています。299通りの計算はできそうにありません。
視点を変えてみましょう。bit全検索では、上から経路を決めて合計値を求めていました。一方、下から考えていけば、一つ上の段の数字から選べる2つの数字で大きい数字を選んだほうが結果は大きくなります。
例になっている三角形で説明しましょう。
3
7 4
2 4 6
8 5 9 3
一番左下の8とその右にある5に注目します（赤字）。仮にその上の2（青字）まで来たときには、8の方が大きいため、8を選ぶしかありません。
3
7 4
2 4 6
8 5 9 3
次は、5とその右にある9に注目します（赤字）。仮にその上の4（青字）まで来たときには、9の方が大きいため、9を選ぶしかありません。
3
7 4
2 4 6
8 5 9 3
しつこいですが、9とその右にある3に注目します（赤字）。仮にその上の6（青字）まで来たときには、9の方が大きいため、9を選ぶしかありません。
ここまで来たら、一番下の段は考える必要がなくなります。3段目は、選ぶしかない方の数字を足しておけばよいわけです。
3
7 4
10 13 15
2段目にも同じことが言えます、10と13では、13の方が大きいため、13を選ぶしかありません。また13と15では、15の方が大きいため、15を選ぶしかありません。その結果、次の三角形を考えるのと同じになります。
3
20 19
この三角形をみると、1段目の3からは2段目は大きい20を選ぶしかなく、最大値の23を得ることができました。
解答例
考察で考えた手順をプログラムに落としてみましょう。
最初の for 文は下から回していきます。次の for 文は、2つを比較するために使います。配列の添え字で1を引いたり、1を足したりしていまので、配列の領域外アクセスに気を付けてください。鍵となる条件の文（背景色を変えています）を先にコーディングして、それから、for 文を書くほうが分かりやすいかもしれません。以下は、C言語の実装例です。
#include <stdio.h>
int problem[15][15] = {
{75, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{95, 64, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{17, 47, 82, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{18, 35, 87, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{20, 4, 82, 47, 65, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{19, 1, 23, 75, 3, 34, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{88, 2, 77, 73, 7, 63, 67, 0, 0, 0, 0, 0, 0, 0, 0},
{99, 65, 4, 28, 6, 16, 70, 92, 0, 0, 0, 0, 0, 0, 0},
{41, 41, 26, 56, 83, 40, 80, 70, 33, 0, 0, 0, 0, 0, 0},
{41, 48, 72, 33, 47, 32, 37, 16, 94, 29, 0, 0, 0, 0, 0},
{53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14, 0, 0, 0, 0},
{70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57, 0, 0, 0},
{91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48, 0, 0},
{63, 66, 4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31, 0},
{ 4, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53, 60, 4, 23}
};
int main(void)
{
int i, j;
for (i = 14; i >= 1; --i) {
for (j = 0; j < i; ++j) {
if (problem[i][j] >= problem[i][j + 1]) {
problem[i - 1][j] += problem[i][j];
} else {
problem[i - 1][j] += problem[i][j + 1];
}
}
}
printf("Problem018: %d\n", problem[0][0]);
return 0;
}効果が高いプログラムですが、あっさり表現できていると感じます。
最後に
視点を変えて、下から考えるとうまくいきました。このような解き方を自分で思いついて、効果も確認できると、プログラミングも楽しくなります。
ランダウの$O$-記法を使うと、前回、紹介した解き方の計算量は、$O(2^n)$ で、今回、紹介した解き方の計算量は、$O(n^2)$ になります。気になったかたは、$O$-記法 などで検索して内容を確認してみてはどうでしょうか。
引き続き、Project Euler の問題を紹介していきます。
