スキップしてメイン コンテンツに移動

Project Euler - Problem 18

ラベル:

問題

  • 原文

    Find the maximum total from top to bottom of the triangle

  • 日本語訳

    三角形を頂点から下まで移動するとき、その最大の合計値を求めよ。

解答

動的計画法を使ってボトムアップで簡単に解くことができる問題です。

簡単のため、小さい三角形で考えることにします：

0:    j
1:   h i
2:  e f g
3: a b c d

2行目の各点を頂点として、2行の小さい三角形が作れることが分かります。 上の例で言えば、(e, a, b)と(f, b, c)、(g, c, d)の3つです。 (e, a, b)の頂点eから末端（a、b、c、dのいずれか）に移動したとき、その数値の合計は最大でe + max(a, b)となります（maxは最大値を選ぶ関数）。同様に他の2つもf + max(b, c)、g + max(c, d)と表せます。 これらをE、F、Gとおくことにして、例を次のように書き換えます：

0:   j
1:  h i
2: E F G

(h, E, F)からなる三角形の最大値はH = h + max(E, F)、(i, F, G)からなる三角形のそれはI = i + max(F, G)です。 Eは「頂点eから末端に至る経路の最大値」で、FやGも同様ですから、HとIは「頂点h（やi）から末端に至る経路の最大値」となります。

これを先ほどと同様に置き換えて：

0:  j
1: H I

頂点jから末端に至る経路の最大値はJ = j + max(H, I)となり、これが解です。

#!/usr/bin/perl

use strict;
use warnings;
use feature qw/say/;
use List::Util qw/max/;

my @rows = map { [ split /\s+/ ] } <DATA>;
until (@rows == 1) {
  my $curr_row = $rows[-2];
  my $bigger_branch;
  for (my $i = 0; $i < @$curr_row; $i++) {
    $bigger_branch = max $rows[-1][$i], $rows[-1][$i + 1];
    $curr_row->[$i] += $bigger_branch;
  }
  $#rows--;
}

say $rows[0][0];

__END__
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

コメント

  1. 平田敦2009年6月3日 9:02:00 JST

    エントリを拝読しました。
    大変参考になりました。
    感謝です。

    返信削除
  2. Koichi SATO2009年6月13日 19:46:00 JST

    見落としていました。コメント承認が遅くなりましてすいません。
    ありがとうございます。稚拙なエントリですが、何かの役に立ちましたなら幸いです。

    返信削除
  3. 平田敦2009年6月13日 21:04:00 JST

    とんでもない、とても役に立ちました。
    年をとって頭が固くなっていますから、
    Webでこうしていろんな方のコードを見せてもらうことがとてもいい刺激になっているんです。

    感謝です。

    返信削除

コメントを投稿

このブログの人気の投稿

Perl 5 to 6 - 列挙型

これはMoritz Lenz氏のWebサイト Perlgeek.de で公開されているブログ記事 "Perl 5 to 6" Lesson 16 - Enums の日本語訳です。 原文は Creative Commons Attribution 3.0 Germany に基づいて公開されています。 本エントリには Creative Commons Attribution 3.0 Unported を適用します。 Original text: Copyright© 2008-2010 Moritz Lenz Japanese translation: Copyright© 2011 SATOH Koichi NAME "Perl 5 to 6" Lesson 16 - 列挙型 SYNOPSIS enum bit Bool <False True>; my $value = $arbitrary_value but True; if $value { say "Yes, it's true"; # 表示される } enum Day ('Mon', 'Tue', 'Wed', 'Thu', 'Fri', 'Sat', 'Sun'); if custom_get_date().Day == Day::Sat | Day::Sun { say "Weekend"; } DESCRIPTION 列挙型は用途の広い獣です。定数の列挙からなる低レベルのクラスであり、定数は典型的には整数や文字列です(が任意のものが使えます)。 これらの定数は派生型やメソッド、あるいは通常の値のようにふるまいます。 but 演算子でオブジェクトに結びつけることができ、これによって列挙型を値に「ミックスイン」できます: my $x = $today but Day::Tue; 列挙型の型名を関数のように使うこともでき、引数として値を指定できます: $x = $today but Day($weekday); ...
コメントを投稿
続きを読む

Project Euler - Problem 25

問題 原文 What is the first term in the Fibonacci sequence to contain 1000 digits? 日本語訳 1000桁になる最初の項の番号を答えよ. 解答 Gaucheのストリームライブラリを使ってみました。 (use util.stream) (define fibonacci-sequence (iterator->stream (lambda (yield end) (let loop ((a 1) (b 1)) (yield a) (loop b (+ a b)))))) (define (digits n) (define (digits-1 m acc) (if (< n m) acc (digits-1 (* m 10) (+ acc 1)))) (digits-1 1 0)) (define (solve) (+ 1 (stream-index (lambda (n) (= 1000 (digits n))) fibonacci-sequence))) (define (main argv) (display (solve)) (newline))
コメントを投稿
続きを読む

Project Euler - Problem 31

問題 原文 How many different ways can £2 be made using any number of coins? 日本語訳 いくらかの硬貨を使って2ポンドを作る方法はいくつあるでしょうか? 解答 ポンドとペンスを別々に扱うのは面倒と無駄以外の何者でもないので、単位をペンスに統一します。よって問題は合計が200ペンスとなるコインの組み合わせは何通りあるかです。 コインを昇順にC i (i = 0, 1, 2, ..., 7)と番号づけることにします。 合計nペンスとなるC k 以下のコインを使った組み合わせをcc(n, k)と表すと、次のようになります： cc(0, k) = 1 cc(n, 1) = 1 cc(n, k) = Σ(cc(n - iC k , k - 1))、ただしi ∈ { 0 , 1, 2, ..., floor(n / C k ) } 副問題は同じものが何度も出てくるのでメモ化しています。 #!/usr/bin/env perl use strict; use warnings; use feature qw/say state/; use List::Util qw/sum/; sub coin_comb($;$); { my @coins = (1, 2, 5, 10, 20, 50, 100, 200); sub coin_comb($;$) { state %memos; my ($currency, $coin_idx) = @_; $coin_idx //= $#coins; return $memos{$currency, $coin_idx} if exists $memos{$currency, $coin_idx}; return 1 if $currency == 0; return 1 if $coin_idx == 0; use integer; $memos{$currency, $coin_idx} = sum map { coin_comb($currency - $coins[$coin_idx] * $_, $coin_idx...
コメントを投稿
続きを読む

Project Euler - Problem 42

問題 原文 By converting each letter in a word to a number corresponding to its alphabetical position and adding these values we form a word value. For example, the word value for SKY is 19 + 11 + 25 = 55 = t 10 . If the word value is a triangle number then we shall call the word a triangle word. Using words.txt (right click and 'Save Link/Target As...'), a 16K text file containing nearly two-thousand common English words, how many are triangle words? 日本語訳 単語中のアルファベットを数値に変換した後に和をとる. この和を「単語の値」と呼ぶことにする. 例えば SKY は 19 + 11 + 25 = 55 = t 10 である. 単語の値が三角数であるとき, その単語を三角語と呼ぶ. 16Kのテキストファイル word.txt 中に約2000語の英単語が記されている. 三角語はいくつあるか? 解答 42問目! ちょっと拍子抜けするほど簡単です。三角数を片っ端から計算して連想配列に入れておき、文字列の値を計算して照合するだけです。 #!/usr/bin/env perl use strict; use warnings; use feature qw/say/; use List::Util qw/sum/; sub word_value($) { my $offset = ord('A') - 1; sum map { ord($_) - $offset } split //, uc shift; } sub tri_num($) { my $n = shift; $n * ($n + 1) / 2...
コメントを投稿
続きを読む

Project Euler - Problem 38

問題 原文 What is the largest 1 to 9 pandigital 9-digit number that can be formed as the concatenated product of an integer with (1,2, ... , n) where n > 1? 日本語訳 整数と(1,2,...,n) (n > 1) との連結積として得られる9桁のPandigital数の中で最大のものを答えよ. 解答 乗数が1, 2, ..., n (n > 1)で桁数は9なので、被乗数mは1から9999の範囲です。 範囲が分かれば後は簡単で、m×1から順に積を連結していって、丁度9桁となったときにPandigital数であればいいわけです。 Pandigital数 を定義通り考えれば「1から9のすべての数字が1回以上現れる数」ですが、この問題では桁数の制約からいずれの数字も1回ずつしか現れないため、「同じ数字が重複して出現せず、0が現れない数」に読み替えることができます。Perlだとこちらの方が正規表現マッチングが高速でした。 #!/usr/bin/env perl use strict; use warnings; use feature qw/say/; use List::Util qw/max/; say max map { my $cat = ''; for (my $mul = 1; length $cat < 9; $cat .= $_ * $mul++) {} (length $cat == 9 and $cat !~ /0/ and $cat !~ /(\d).*\1/) ? $cat : () } 1 .. 9999;
コメントを投稿
続きを読む