Dragon Fantasy 解説

アルゴリズムの概略

この問題は枝刈り探索で解けます。 枝刈り探索の問題というのは，枝刈り探索で解けると聞けば案外すんなり解けますが， 「枝刈り探索で解けるのかどうかがそもそも分からない」場合が多い，つまり計算量が算定できないので手を付けにくい問題です。 ACM/ICPCでは「はまらないこと」が重要なので，たいていのチームが最初はスルーすることになります。 手を付けるか付けないか，それが問題です。 時間があればとりあえず書いてトライしてみるというのも一つの手ではあります。

この問題を最初に読むと，グラフ問題かと思います。 例えば全てのクリスタルを回収する経路の中で最短のものを見つければ（巡回セールスマン問題を解けば）それが解になるかと思いきや， 瘴気とクリスタルの位置関係に依存するので解とは言えません。 色々考えさせられることになりますが，結局は枝刈り探索に落ち着かざるを得ないのです。

さて，この問題はクリスタルの回収で，進めない領域が (dx, dy) を中心に単位時間あたり 1 ずつ同心円状に広がっていきます。 ですから，クリスタルを回収したときにそこが既に進めない領域であれば，その探索は打ち切ることができます （木構造状に探索しているとイメージして，これを枝刈りと呼びます）。 逆に，回収時にそこが進める領域であれば，瘴気と主人公の速度が等しいために移動途中で一度も瘴気の円の中に入っていないことが分かるので，その探索は続ける必要があります。

ですが，n = 20 もあり，その程度の枝刈りでは探索は終了しません。 そこで，「そこから回収できるクリスタルのうち一つでも取れなければ探索を打ち切る」という条件を追加します。 というのも，aを現在位置として，a -> b といって取れない（間に合わない）クリスタルは a -> c -> b といっても必ず取れないからです。 つまり，現在地点から到達不可能なクリスタルが一つでもあれば，その探索は無意味であるといえます。 そして，この条件を入れればプログラムは現実時間内に終了します。

アルゴリズムの計算量

見積もることはできません。 ただ，この問題は経路が見つからない場合が計算時間が最もかかるので，そのような場合の計算量を減らすアルゴリズムを考えることが重要です （クリスタルを全て回収する経路を早く見つけることにはあまり意味がない）。

感覚的に言えることは，上記の枝刈り条件を入れることによって，遠く離れているクリスタルを先に回収しようとするようなパスは早めに（探索が浅いうちに）打ち切られやすくなります。

アルゴリズムの実装

瘴気（同心円状）内にいるかどうかは，魔王の位置が (dx, dy)，現在位置が (x, y) で時間 t 経っているとすると，

sqrt((dx-x)^2 + (dy-y)^2) <= t

で判定できます（右辺は瘴気の広がる速度が 1 のため 1×t = t）。 これはいわゆる「円の内外判定」で，円の中心との距離が半径以下であれば円の内側（もしくは円上）にあることが分かります。

ただし，実数（浮動小数点）を扱うので注意が必要です。 今回の問題では勇者が瘴気の円上であればダメになっているので，上記の等式で「左辺＝右辺」が成り立つ場合を扱わなければなりませんが， 計算誤差があるので実数の計算では == 演算子を使うことはできません。 なので，非常に小さい数，例えば ε = 10-10 のような値を使って，

#define EPS (1e-10)

if ( dist(dx-x, dy-y) < t + EPS ) {
  ...
}

としてやる必要があります（これで t よりやや大きいけれどもほぼ等しい場合もif文が成り立つようになります）。 これは実数を扱う計算では非常によく使う手法なので覚えておきましょう。

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