Posted at

Project Euler Q67 【最大経路の和 その2】

More than 1 year has passed since last update.

Project Eulerをワンライナーで解いてみる。

間違っていたらコメントください。


問題

以下の三角形の頂点から下まで移動するとき, その数値の合計の最大値は$23$になる.

   3

  7 4

 2 4 6

8 5 9 3

この例では $3 + 7 + 4 + 9 = 23$

$100$列の三角形を含んでいる$15K$のテキストファイル triangle.txt (右クリックして, 『名前をつけてリンク先を保存』)の上から下まで最大合計を見つけよ.

注:これは, Problem 18のずっと難しいバージョンです.

全部で$2^{99}$ 通りの組み合わせがあるので, この問題を解決するためにすべてのルートをためすことは可能でありません!

あなたが毎秒$1$兆本の$(10^{12})$ルートをチェックすることができたとしても, 全てをチェックするために$200$億年以上かかるでしょう.

解決するための効率的なアルゴリズムがあります. ;o)


解答

time cat triangle.txt |

awk '{for(i=1;i<=NF;i++){if(a[NR-1][i]<a[NR-1][i-1]){a[NR][i]=$i+a[NR-1][i-1]}else{a[NR][i]=$i+a[NR-1][i]}}} END{for(i=1;i<=NF;i++){print a[NR][i]}}' |
sort -n |
tail -1
7273

real 0m0.033s
user 0m0.030s
sys 0m0.007s

Problem 18と全く同じ方法で解けた。

しかも処理速度も問題ない。


答え合わせ

こちらのサイト様と一致していればOKとした。

http://kingyojima.net/pje/067.html