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

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. エントリを拝読しました。
    大変参考になりました。
    感謝です。

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

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

    感謝です。

    返信削除

コメントを投稿

このブログの人気の投稿

京大テキストコーパスのパーサを書いた

要旨 CaboCha やなんかの出力形式であるところの京大テキストコーパス形式のパーサモジュールを Perl で書いたので紹介します。 Github Tarball on Github Ppages これを使うと例えば CaboCha の出力した係り受け関係を Perl のオブジェクトグラフとして取得できます。 使用例 単なる文節区切りの例。 #!/usr/bin/env perl use v5.18; use utf8; use IPC::Open3; use Parse::KyotoUniversityTextCorpus; use Parse::KyotoUniversityTextCorpus::MorphemeParser::MeCab; use Symbol qw//; my ($in, $out, $err); my $pid; BEGIN { ($in, $out, $err) = (Symbol::gensym, Symbol::gensym, Symbol::gensym); $pid = open3($in, $out, $err, cabocha => '-f1'); } END { close $out; close $err; waitpid $pid => 0 if defined $pid; } binmode STDOUT, ':encoding(utf8)'; binmode $in, ':encoding(utf8)'; binmode $out, ':encoding(utf8)'; my $parser = Parse::KyotoUniversityTextCorpus->new( morpheme_parser => Parse::KyotoUniversityTextCorpus::MorphemeParser::MeCab->new, ); say $in '星から出るのに、その子は渡り鳥を使ったんだと思う。'; say $in '出る日の朝、自分の星の片付けをした。'; close $in; my $sentence

C の時間操作関数は tm 構造体の BSD 拡張を無視するという話

久しぶりに C++ (as better C) で真面目なプログラムを書いていて引っかかったので備忘録。 「拡張なんだから標準関数の挙動に影響するわけねえだろ」という常識人は読む必要はない。 要旨 time_t の表現は環境依存 サポートしている時刻は UTC とプロセスグローバルなシステム時刻 (local time) のみで、任意のタイムゾーン間の時刻変換を行う標準的な方法はない BSD / GNU libc は tm 構造体にタイムゾーン情報を含むが、tm -> time_t の変換 ( timegm / mktime ) においてその情報は無視される 事前知識 C 標準ライブラリにおいて時刻の操作に関係するものは time.h (C++ では ctime) ヘッダに定義されている。ここで時刻を表現するデータ型は2つある: time_t と tm である。time_t が第一義的な型であり、それを人間が扱い易いように分解した副次的な構造体が tm という関係になっている。なので標準ライブラリには現在時刻を time_t として取得する関数 ( time_t time(time_t *) ) が先ずあり、そこから time_t と tm を相互に変換する関数が定義されている。 ここで time_t の定義は処理系依存である。C / C++ 標準はそれが算術型であることを求めているのみで (C11 からは実数型に厳格化された)、その実体は任意である。POSIX においては UNIX epoch (1970-01-01T00:00:00Z) からのうるう秒を除いた経過秒数であることが保証されており Linux や BSD の子孫も同様だが、この事実に依存するのは移植性のある方法ではない。 一方で tm は構造体であり、最低限必要なデータメンバが規定されている: int tm_year : 1900 年からの年数 int tm_mon : 月 (0-based; 即ち [0, 11]) int tm_mday : 月初からの日数 (1-based) int tm_hour : 時 (Military clock; 即ち [0, 23]) int tm_min : 分 int tm_sec : 秒 (うるう秒を含み得るので [0

救急外来にかかったときの記録

子どもの頃にかかった記憶はあるが自分で行ったことはなかったのでメモしておく。 先日怪我をした。より具体的に云うとランニング中に転倒し顎を地面に叩きつけた。深夜の12時ごろの話である。 その時点ては両手の擦傷が痛いとか下顎の間接が痛いとか奥歯のセラミックが割れなくて幸いだったといった程度だが、マスクを外して見るとなにやら下部に血がついている。 顎にも擦傷があるのかとうんざりしながら歩いて帰り、血の滲んだマスクを捨てて傷口を洗おうとしたところで皮膚が割けて肉が見えているのに気付いた。 一瞬顔が青くなったが単身なので倒れるわけにはいかない。幸い血は固まっていてそれほど出血していないし、先程まで運動していたからかあまり痛みもない。 この時点で明白な選択肢は3つあった。即ち: 救急車を呼ぶ 自力で病院へ行き救急外来を受診する 応急処置して朝になったら近場の医院を受診する である。まず 3 は精神的に無理だと悟った。血も完全には止まっていないし、痛みだしたら冷静に行動できなくなるだろう。 1 はいつでも可能だったが、意識明瞭で移動にも支障がない状態では憚られた。救急車が受け入れ先病院を探すのにも時間がかかると聞く。 結局とりあえず 1 をバックアップ案とし、2 の自分で連絡して病院へ向かうことにした。まずは病院探しである。このときだいたい 00:30 AM。 最初に連絡したのは最寄りの都立病院の ER だった。ここならタクシーで10分もかからない、のだが、なんと ER が現在休止しているとの回答だった。そんなことがあるのかと驚愕したがどうしようもない。 近場に形成外科の救急外来の開いている病院はないか尋ねたところ 消防庁の相談センター の電話番号を案内された。 ここで4つの病院を紹介された。余談だが相談の対応は人間だが番号の案内は自動音声に切り替わるので録音の用意をした方が良い (一応2回くり返してくれる。) いずれも若干遠くタクシーで2、30分かかるが仕方がない。最初に連絡した最寄りの病院はその日形成外科の当直医師がいなかった。二件目でトリアージの質問をされ、受け入れ可能とのことだったので受診先が決定。このとき 00:45 AM。 診察時に脱ぎ易い服に着替え (このときまでランニングウェアだった)、健康保険証を持って病院へ向かう。ガーゼがないのでマス

js_of_ocaml の使い方

js_of_ocaml (jsoo) は Ocsigen が提供しているコンパイラである。その名の通り OCaml バイトコードから JavaScript コードを生成する。 これを使うことで OCaml で書いたプログラムを Web ブラウザや node.js で実行することができる。 インストール 単に OPAM を使えば良い: $ opam install js_of_ocaml js_of_ocaml-ocamlbuild js_of_ocaml-ppx バージョン 3.0 から OPAM パッケージが分割されたので、必要なライブラリやプリプロセッサは個別にインストールする必要がある。 とりあえず使うだけなら js_of_ocaml と js_of_ocaml-ppx の二つで十分。後述するように OCamlBuild でアプリケーションをビルドするなら js_of_ocaml-ocamlbuild も入れると良い。 これで js_of_ocaml コマンドがインストールされ、OCamlFind に js_of_ocaml 及びサブパッケージが登録される。 コンパイルの仕方 以下ソースファイル名は app.ml とし、ワーキングディレクトリにあるものとする。 手動でやる場合 一番安直な方法は、直接 js_of_ocaml コマンドを実行することである: $ # バイトコードにコンパイルする。js_of_ocaml.ppx は JavaScript オブジェクトの作成や操作の構文糖衣を使う場合に必要 $ ocamlfind ocamlc -package js_of_ocaml,js_of_ocaml.ppx -linkpkg -o app.byte app.ml $ # 得られたバイトコードを JavaScript にコンパイルする $ js_of_ocaml -o app.js app.byte OCamlBuild を使う場合 OCamlBuild を使う場合、.js 用のビルドルールを定義したディスパッチャが付属しているので myocamlbuild.ml でこれを使う: let () = Ocamlbuild_plugin . dispatch Ocamlbuild_js_of_ocaml . dispatcher $ # app.ml ->

開発環境の構築に asdf が便利なので anyenv から移行した

プロジェクト毎に異なるバージョンの言語処理系やツールを管理するために、pyenv や nodenv など *env の利用はほとんど必須となっている。 これらはほとんど一貫したコマンド体系を提供しており、同じ要領で様々な環境構築ができる非常に便利なソフトウェアだが、それを使うことで別の問題が出てくる: *env 自身の管理である。 無数の *env をインストールし、シェルを設定し、場合によりプラグインを導入し、アップデートに追従するのは非常に面倒な作業だ。 幸いなことにこれをワンストップで解決してくれるソリューションとして anyenv がある。これは各種 *env のパッケージマネージャというべきもので、一度 anyenv をインストールすれば複数の *env を簡単にインストールして利用できる。さらに anyenv-update プラグインを導入すればアップデートまでコマンド一発で完了する。素晴らしい。 そういうわけでもう長いこと anyenv を使ってきた。それで十分だった。 ——のだが、 ここにもう一つ、対抗馬となるツールがある。 asdf である。anyenv に対する asdf の優位性は大きく2つある: 一貫性と多様性だ。 一貫性 “Manage multiple runtime versions with a single CLI tool” という触れ込み通り、asdf は様々な言語やツールの管理について一貫したインタフェースを提供している。対して anyenv は *env をインストールするのみで、各 *env はそれぞれ個別のインタフェースを持っている。 基本的なコマンド体系は元祖である rbenv から大きく外れないにしても、例えば jenv のように単体で処理系を導入する機能を持たないものもある。それらの差異はユーザが把握し対応する必要がある。 多様性 asdf はプラグインシステムを持っている。というより asdf 本体はインタフェースを規定するだけで、環境構築の実務はすべてプラグイン任せである。 そのプラグインの数は本稿を書いている時点でおよそ 300 を数える。これは言語処理系ばかりでなく jq などのユーティリティや MySQL のようなミドルウェアも含むが、いずれにしても膨大なツールが asdf を使えば