Nothing New

edvakfさんのTwittrでちらと見かけた Problem 18
http://projecteuler.net/index.php?section=problems&id=18

こんな感じで、手で解けそう。

　a1　　　→　a'1 ＝ a1＋max(b1,b2)
b1 b2　　→　消す

これで下のほうから縮退していけばいいような。


ということで、手でやってみる。

　　　　　　　　　　　　　　75*
                           1074

　　　　　　　　　　　　　95  64*
                         995 999

　　　　　　　　　　　　17  47  82*
                       818 900 935

　　　　　　　　　　　18  35  87* 10
                     704 801 853 782

　　　　　 　　　　　20  04  82* 47  65
                    686 640 766 731 772

　　　　　　　 　　19  01  23  75* 03  34
                  666 614 636 684 660 707

　　　　　　　　 88  02  77  73* 07  63  67
                647 501 613 609 533 657 673

　　　　　　　 99  65  04  28* 06  16  70  92
              559 499 479 536 514 526 594 606

　　　　　　 41  41  26  56  83* 40  80  70  33
            460 434 419 475 508 479 510 524 487

　　　　　 41  48  72  33  47  32* 37 16 94 29
　　　　　419 385 393 387 419 425 430 376 454 322

　　　　 53  71  44  65  25  43  91* 52  97  51  14
　　　　378 337 231 321 354 372 393 354 360 293 247

　　　 70  11  33  28  77  73  17  78* 39  68  17  57
　　　325 246 187 177 256 329 273 302 263 242 193 233

 　　91  71  52  38  17  14  91  43  58* 50  27  29  48
　　255 235 154 149 140 179 256 209 224 172 174 176 148　

 　63  66  04  68  89  53  67  30  73* 16  69  87  40  31
　125 164 102  91 111 123 165 128 166 109 122 147 100  54

 04  62  98  27  23  09  70  98  73  93* 38  53  60  04  23

よって、合計は 1074 だと思う。


追記：
最大ルートに * つけました。
というのは、CODEタグでくくって「スペースで位置決め」をしているため。