ICFPC 2009
6/27の27時から三日間あったのに二人組で参加してました。で、簡単なメモだけ。眠いので適当にしか書かないけれど、多分書き直したりもしなさそう。
問題
物理シミュレータのバイナリコードが与えられるので、その上で衛星を操作してお題をこなしましょう。バイナリのフォーマットが与えられるので、ちゃんとVM作ってからやりましょうね、という感じ。
取り敢えず面倒な部分は全部チームメートに丸投げして、ひたすらお題と戯れていました。
1001-1004
人工衛星を円軌道に乗せましょう。
軌道に乗せて900s間静止させないとダメ。効率のいい式を計算してやるとうまくいくわけですが...。実はこの問題だけ燃料を使い切った方が高得点という仕様なので、円軌道に接触した瞬間全エネルギーを放出して円軌道に乗れば良くて、それまでに使っていいエネルギー量を適当にサーチしてやる。エネルギーはまとめて使った方が早く円軌道に接触できるので、高得点を目指すには大体一意に定まるっぽい。
ベストは97点らしいんだけれど、1001と1004では達成できなかった。他も燃料の処理が悪くてちょっと減点されている。
2001-2004
円軌道に乗っている人工衛星に横付け(900s)しましょう。
円軌道の大きさによって周期が変わるので、タイミング良く円軌道に乗る問題。下手な小細工すると燃費が悪いので何もしない方が良さそうな感じ。若干ずれる分の補正は燃料でやった方がいい気がしたけれど、一周余分にしても時間のスコアが変化しなかったりもするので、ケースバイケースだった。
3001-3004
楕円軌道に乗っている人工衛星に横付け(900s)しましょう。
今度は楕円軌道なので、その分だけ面倒。解法は二つあって、まず遠日点か近日点で接する円軌道に乗って、遠日点か近日点で横付けした上で適当に加速して楕円に乗せる。(これはタイミングが比較的取りやすい。)あるいはどこかで適当に横付けして、相手の動きを真似する。横付けの位置が正確なら、大体うまくいくはず。
4001-4004
12個の衛星をそれぞれ訪問(1s)しましょう。ただし月があって、重力が働きます。
自分も他の衛星も月に引きずられるらしい...けれど良く分からなかった。12個の衛星のうち、一つはエネルギータンクで、訪問するたびに自分タンクを満タンにできるけれど、エネルギータンクの残量には上限がある。衛星の一つは月の回りをクルクル回るという厄介仕様。(月は非常に遠い。)
基本的にはエネルギータンクはいつ訪問してもいいけれど、一回は行かないといけないので、エネルギー効率を考えて真ん中ら辺、とお思いかも知れませんが、エネルギータンクは凄く近くにあるので、どの問題も序盤に訪問する方が良さそう。4003は別の衛星との兼ね合いで2番目になったけれど、他は最初に訪問しておいた。(4004はやってないけれど。)
で、実はこの問題、1sだけでいいので今までの問題よりもかなり楽。しかも燃料は全然使わない。取り敢えず重要なのは、自分は大抵地球を焦点とする楕円軌道(月の影響は遠くて余りない)に乗るので、加速は近日点で行うに越したことはない。近日点加速は最初は10％くらい使うけれど、最後の方は2％とかで十分なので、非常に燃費がいい。
あと、1s接触なので近日点での加速をバイナリサーチしてやると、大抵どれかの衛星に当たる。(もちろん面倒なので、ある程度近付くようなら、そこらで微調整する。微調整は月以外100も使わないケースがほとんど。)大抵の問題はこんな感じで自分タンクの燃料40％くらいで月以外は回収できる。で、月には30％くらい無駄打ちしても時間が1Msくらいなら必ず身入りがあるので向かって問題ない。(タイミングさえあえば月には10％もかからずに行けるけれど、時間がもったいないので無駄打ちしてでも行くべき。)悪く見積もっても自分タンクに10％くらい残る状態で終われるので、補充は本当に最初に一回するだけで良かった。
ステートセーブができたので、非常に効率良くバイナリサーチできたので、ストレスフリーだった。ただ気力が続かないので、8個くらい回収するまででいっぱいいっぱい。後半は結構ひどい。特に月とかは無駄打ちし過ぎ...。
