結果発表 > 優勝作品と解説

優勝されたsumoruさんの作品と、ご本人による作品解説です。

優勝者作品

sumoruさんの作品(ソースコード)

作品解説

コンテスト中に考えたことやプログラムの遷移

スコアが大きく変わったところなどを抜粋しています。

35,252 turns 0.05sec
最初に作ったテストコード。小さいUFOが貪欲に、近い順に家を周る。
25,798 turns 0.1sec
大きいUFOを農場として利用するようにした。大きいUFOは小さいUFOが多くいるところに向かう。
目的の家がUFO間で重複しないようにした。終了直前は重複することもある。
21,412 turns 0.1sec
小さいUFOが、最も近い家とその付近を周るようにした。
19,238 turns 5sec
大きいUFOの目的地を、家が密集しているところを探して設定するようにした。その点に向かう途中で、近くに家があったら寄っていく。
17,851 turns 1sec
大きいUFOも家を周るようにした。農場としての利用も継続している。
小さいUFOは、高々5つの家を周ったのちに農場に戻るので、巡回セールスマン問題を(ただの総当たりで)解いて経路を最適化した。
16,196 turns 4sec
実現可能な最小ターン数を二分探索で探すようにした。そのために、initの段階でどのUFOがどの家を周るのかを全て決定し、ターン数を予測できるようにした。

大きいUFOが周る家を最初に決定し、何ターン目にどこにいるかを全て記録する。それをもとに、小さいUFOが周る家・農場の順番を決定する。順番は基本的に貪欲法で求めた。

これ以降は細かい工夫をしたりバグを見つけたりして、数百ターンずつ縮まっていきました。
UFOの目的地を家の中心ではなく、その次に行く家の方向に少しずらした。go2() 参照。少し手抜きをしており、もう少し改善できそう。

大きいUFOの周る家とその順番が変わるとターン数が結構変わるので、密集した家の中心をどこに据えるかを変えて何度も試すようにした。計算時間のほとんどはこれに使っていて、これをなくすと総ターン数13,630、5secくらいになる。


小さいUFOが周る家の順番は、まだ目的地になっていない家の中で、中心から最も離れた家に最終ターンに到達すると仮定して、そこから時間を遡るように決定した。

ターン数予測の精度向上・高速化のために色々と試した。

基本的に、何か思いついたら実装してみて、うまくいけば採用、ダメならコメントアウトして後でまた試す、の繰り返し。

貪欲法ではない、もっといい方法は思いつかなかった。


13,600ターンを切ったあたりからほとんどターン数が縮まらなくなり、乱数を使って貪欲法がたまに次善手を選ぶようにしたところ、ターン数が数百小さくなり、そのとき初めて暫定一位のスコアとなりました。

感想

(研究そっちのけで)時間をかけて色々と試せたのでとても楽しめました。優勝できてとてもよかったです。

視覚的にも楽しい問題をありがとうございました。