■ [MM][TCO]TCO09 Marathon Round3 
100人→10人。Top50（たしか）はTシャツがもらえますよ。
問題
http://www.topcoder.com/longcontest/?module=ViewProblemStatement&rd=13768&pm=10372
垂直な平面内にターゲットとなる円が数十個配置されている。この中に質点を1つ落とすので、板を何個か置いてうまく質点を跳ね返らせ、ターゲットに全部当てよ、という課題。
方針
Round2はギリギリ通過だったので戦える気がしません。Tシャツもらえるところまでいければ御の字。
てなわけでのんびり楽しんでやる。
履歴
| 日付 | 使った時間 | やったこと |
|---|---|---|
| 3/26（木）- 3/29（日） | 7hくらい | 自明解（いろんな方向に1回だけ跳ね返らせて一番良かったやつを採用）で提出。20点弱くらい |
| 3/30（月）- 4/3（金） | 10hくらい | シミュレーション部分のコードをビジュアライザから移植してきて手元で使えるようにした。 高速化の余地がかなりあったのでいろいろといじる 板を使ってターゲットをつなぐ細い通路を造ってその中を通す、という方針を試すが、 激しく跳ね返りまくって全然ハンドリングできない。無理ゲー感漂う |
| 4/4（土）- 4/5（日） | 24h | 眠れなかったので24時間耐久マラソン開催。 板は整数座標にしか置けないので、飛ぶ方向を正確に計算して配置することは不可能そう。 何かしら総当たり的、ランダム的手法が必要そうだとやっと把握する 時間間隔を決めて、その時間内で最もたくさんターゲットに当たる板の置き方を数種類の中から選択する、 それを繰り返して全部のターゲットに当たるまでやる。という方針でやってみた。 つまり、一定ステップで時間を進めながらgreedyに飛ばしていく、といった感じ。 これを時間間隔を変えながら試して一番いいやつを採用。 なんとかまともに飛んでいくようになった。一気に60点台後半へ到達 |
| 4/6（月） | 3h | ふと思いついた高速化を入れてみたら、なんかシミュレーションが3倍くらい速くなった。70点台 |
| 4/7（火） | 2h | パラメタ調整でチューニング。2点くらい上がった |
| 4/8（水） | 4h | パラメタ調整でチューニング。しかしカオティックな振る舞いでよくわからなくなったのでほとんど影響なし |
シミュレーションを高速化するにあたって、ボトルネックは、質点の軌跡がターゲットにぶつかるかどうかをNewton法を使って4次方程式を解いて求めているところのようでした。
ここで、大部分はNewton法を使うまでもなく簡単な計算でぶつからないことが自明にわかるケースなので、それをカットすることで高速化できました。
結果
暫定順位 19/91
感想
僕は参加者のレーティング順で70番目くらいだったので、この結果はできすぎです。たまたまとしか言えぬ。
問題に関しては、アルゴリズムというよりもチューニング勝負になってしまってる感があって、ちょっと微妙だったかも…。
画像
こんな感じ。
短い板しか使っておらず、画面上で板はほとんど見えません。長いのを置くと、以前に通った経路とぶつかってそれまでの計算がおかしくなりそうだったので。
しかし最初の一枚だけは「以前の経路」が存在しないので、長いのを使っても良かったんですね。ここは気づきたかった。
