幾何での手抜き手法

※この記事はCompetitive Programming Advent Calendar Div2012 の19日目の記事です。

競技プログラミングにおいて、時間内に正しい答えを出せる限り手を抜く(簡単なプログラムを書くの意)のが定石。
ということでとある問題を題材に探索っぽくして幾何で手を抜く方法でも紹介してみます。

問題

AOJ1093を題材にします。

詳しくは本家で読んでもらうとして概要はこんな感じ↓

N (≦ 100)個の点 p[i] = (x[i], y[i]) と速度 v[i] (0 ≦ i ≦ N - 1)が与えられます。
適当な座標を選び、(x[i], y[i]) に速度 v[i] で移動する時間の0 ≦ i ≦ N - 1での最大値を最小化する。
その時の最小値を出力しなさい。

解法

数学的な解法は私には思い浮かばないので、探索していくことにしましょう*1

探索方法

点を移動させていって、解っぽいところを探す探索を考える。

今(x, y)にいるとして、よりよい点を探すにはどうすれば良いか。
自然に、一番移動に時間がかかる点の方に少しすすめば良い気がする。

実はこの問題はこの解法で良く、擬似コードにすると以下のようになる。
実際のコード見たい方はこちら

r := (0.5 〜 (1.0 - ε) の間の適当な数)

(x, y) <- 適当な点
d <- ある程度大きい数

while 収束するまで
  (x, y) <- ((x, y) を 一番移動に時間がかかる点 p[i] の方向に d だけ近づけた点)
  d <- d * r

print ((x, y) から一番移動に時間がかかる点 p[i] に移動するのにかかる時間)

これで通ってしまう。
幾何系の問題の解法には見えないすっきりさで素晴らしい(当社比)。

考察

これで終わりだと面白く無いのでほんの少しだけ考察。

おそらくこの手法は山登り法の一種だと思われる。
一般には局所解に陥る場合があり、厳密な解を出すような問題には不向きだが、今回のような局所解となるような点が他にない問題では使える*2

サンプルケースだと以下のような評価関数(= (x, y) から一番移動に時間がかかる点 p[i] に移動するのにかかる時間)になっていて、局所解が他に無いことや、山登り(図だと谷下り??)法で綺麗に解けそうな様子が見える(見難くてごめんなさい)。

今回は、評価関数として問題に書かれているものをそのまま利用したが、本当の解と評価関数の極大/極小の位置さえ一致していれば良いので評価関数を工夫することで色々な問題に応用できるはず。

デメリット
  • r や d や (x, y)の初期値がパラメータとして残ってしまう
    • d や (x, y)はあまりにも外れた値を書かない限りは大丈夫だが r が難しい
      • 小さすぎると上手く解にたどり着かない場合があり、大きすぎると時間がかかりすぎる。
      • 今回のケースだとr = 0.97付近にWAとACボーダーがあるらしく予想外に大きい*3
    • パラメータのせいでWAになった場合にパラメータのせいなのかアルゴリズム的な間違いなのかが分かりにくい

まとめ

探索っぽくして幾何で手を抜く方法を紹介しました。そんなに汎用的に使える手法でもないですが、何度かこの種の解法を書いた記憶はあるので、たまには使える手法のはずです。(最近だとUTPC2012 D-地図が2枚)

一見難しそうな幾何問題に出会っても、このような簡単な探索で解けないか考えてみると良いかも知れません。

明日はDarseinさんとnatrium11321さんの番です。皆様楽しみに待ちましょう!

*1:真面目に考えたけど本当に浮かばない。周りのコード見ても3分探索とか使っているので、綺麗には解けない?

*2:局所解に陥ってしまう場合でも初期値を複数試すことで十分高い確率で通るみたいな問題があったら面白いのでは

*3:直感的には、間違えて移動した場合に r = 1/2 だと挽回できるはずなので 1/2より少し大きいあたりと予想していた