当ＨＰがいつもお世話になっているＨＮ「ＹＩ」さんからの出題です。
（平成２６年４月１２日付け）
画像を見て答えてください。
１．左の「１」からスタートする。分かれ道にさしかかったら好きな方向に向かう。ただし、左に
戻らず、右に右にと進んでいく。いちばん右に到着したときに、通った数字の合計が最も大
きくなるような進み方を答えよ。
２．このような問題について、どのようなネットワークでも答えを導ける一般的な方法を考えよ。
この問題は中学二年生のときに作りました。同級生は誰も相手にしてくれなかったのを覚え
ています。
（答） らすかるさんが考察されました。（平成２６年４月１２日付け）
1→12→13→14→27→21→20 だと思います。
DD++さんが考察されました。（平成２６年４月１３日付け）
１．の解は、らすかるさんの解と同様に、「1、12、13、14、27、21、20」で、合計108 が最大。
２．について、右から順に以下の作業をする
・一番右の列の各マスはそのままにしておく。（今回は、20をそのままに）
・右から二番目の列の各マスについて、その右に繋がっている数のうち最大のものを
加えて書き換える（今回は上からそれぞれ41、39、37に書き換える）
・右から三番目の列の各マスについて、その右に繋がっている数のうち最大のものを
加えて書き変える（今回は上からそれぞれ61、67、50、68、52に書き換える）
・左端まで繰り返す（今回は108になり、これが合計の最大値）
・左端からスタートし、右に繋がっているうち最大の数が書いてあるところを選んで進む
・数字を全部戻してその経路を通るのが答え
（コメント） なるほど、DD++さんの逆算の方法が自然な計算ですね。
私の備忘録の「スケジュール問題」による解法と同じ考え方です。
ＹＩ さんからのコメントです。（平成２６年４月１３日付け）
DD++さんの解法はわかりやすいですね。私が考えていたのは、もっと分かりにくい考え方
でした。
・任意の点Aから点Bへ向かう道筋をルートと呼ぶ。
・ある２つのルートについて一方を通るともう一方を通ることができない場合、二つのルート
は独立であるとする。
１．適切な２点A、Bを考え、AからBへ向かう最も点数の高いルートを探す。それが判定でき
なければ、別の２点を選びなおす。
２．AからBに向かうルートに接しているルート、つまりルートA、Bから「開いている」ルートを
すべて探す。
３．２で選んだすべてのルートに対して独立、かつ、１．で見つけたルートに含まれていない、
ルートA、Bの部分をすべて消去する。
４．これを繰り返すと、答えのルートだけが残る。
（具体例）で説明すると、
１．画像の左側の１と８を選択。１から８に向かうルートは上側のほうが点数が高い。
２．A,Bから開いているルートは、１５-１２と１０-１５
３．１-１０は１のルートに含まれていないが、１０-１５と独立でないので、残しておく。１０-８
は、条件に合うので、消去する。