Amida, the City of Miracle 解説

アルゴリズムの概略

あみだくじを辿るだけという問題。 高いところ (h = 1000) から順に下っていって横線があればそれを辿ればOK。 h = 0 のときの状態が解になります。

STLに慣れていない方はこういう簡単な問題でSTLを駆使して慣れておきましょう。 この問題は multimap と set を使うと効率的に解けるのですから！

アルゴリズムの計算量

単純なシミュレーション問題なので計算量を求めることは不要。

アルゴリズムの実装

単純な配列を使う場合は素直に実装すればいいでしょう。

STLを駆使する場合は，横線のデータを保持するために multimap< int, pair<int, int> > を， 出現した高さをソートするために set<int> を使います（通常setは二分木で実装されるので勝手にソートされます）。 typedef しておくと後でデータ構造やアルゴリズムの変更があっても比較的楽に修正できます （本当は完全にデータ構造を決めてからプログラムを書くべきですが）。

$Id: index.shtml 1335 2007-03-01 09:06:39Z SYSTEM $