Imagine Cup Round 2

NHC

ギリギリで Round 1 に通った私ですが、なんか結果出るのが遅いんですけど、通ってないのが明らかなんで忘れないうちに。


２週間くらい前（？）に pascal に Imagine Cup やってる？といわれて存在を思い出す。問題だけ読んでたので、適当に作ったら 30 くらいだった（小さい方がよいスコア）。ちなみにかなり naive な方法なので、いかにみんな適当か分かる。そのあと adhoc な修正を加えて 20 くらいまで減る。先週は NTCIR にいったりしてて時間がなくて放置。

終了２日前くらいにメールが来て存在を思い出すが、結局前日に adhoc に修正しまくって 18.2 くらいで FA。なんか、いい加減に終わってしまいました。でも、17 とかとても無理そうだったので時間あっても通過できなかったでしょう。というか、決勝６人とかやる気がなさすぎるといわざるを得ない。下位の人はどう考えてもあきらめるだろう。

さて、肝心の問題ですが、ノード数 N*N*N の無向グラフが与えられたとき、これを N*N*N の立法格子点上に配置して、そのエッジの長さの総和を最小化せよという問題（長さの総和とかかった時間の重み付き線形和がスコア）。ちなみにとった方法は、エッジの多いノードから順に現時点で長さの総和が最小になるように配置し、あと適当に総和が短くなるようにランダムに選んだ点を更新するだけ。適当な heuristics が含まれます。

解いた感想ですが、

  • heuristics をちょっといじると突然スコアが変わり出す
  • しかも法則性とか一般性が見えない
  • 初期値を工夫するとスコアが変わるが、初期値だけ良くて収束点の悪い初期値ができることも
  • 総合して結局スコアが修正前と変わらない・・・
  • ランダムに選ぶと速度だけではなく、収束速度にもなぜか効く
  • 人生は適当だということだ（ぉ

どうも、エッジ数の多いノードの位置が重要で、これを間違えると反復的な手法では修正しづらいようです。ビット演算を使った怪しいことを試しましたが、意外と速度向上しなくて萎えました。というかバグってて、途中でデバッグをあきらめた・・・。

※ 終了ギリギリでわざと時間切れする DLL を送りつけてる人がいるなぁというのは私も感じましたよ