なにをしたか、とその反省 - 本戦
寝て…寝れなかったので、とりあえず反省を元に C++ でキチンと書きなおす。まずは VM は速いにこしたことないだろう…と JIT …は面倒だったので、その場で C コードを生成して実行するように。 validation の際は問題のバイナリが変わるだろうから、あらかじめ作っておくってのはイカンわけだね。この VM はほとんどバグも無いし速いしで文句の無い感じだった。5秒以内に 3M step は実行するようだ。
この最中にしんどいと思ったら熱出てることに気付いて悲しかった。加えて1日分の作業の書き直しとか相当ダルいので、めげかけた。しかし頑張った。 400x はとりあえず放置で2日目は全て使う覚悟で。
このへんで寝たか、そして起きた。 100x を解く C++ コードを書く。 Ruby と同じことしてるつもりなんだけど 1004 が通らん。どうしたもんかなぁと思ったけど、後々そのノウハウは必要になるかもしれないし…と適当に到着してから adjust するコードを書いた。そこでわかったのはここでやった種類の補正はうまくいかんし、確実性が低いということだった。最終的には後で捨てた。
1004 の補正の最中に書いたコードで有用だったものは、物理系の完全なシミュレータだった。この手のシミュレータは慎重に書かないと結構間違えるんだよなぁ…とビクビクしつつ書いたけど、まぁ割とあっさりうまく動いた。
200x 。スクリプトでやっていたことを移植する。めんどくさい。マジでめげる。そしてよくバグる。数値計算が微妙にずれまくる。シミュレータや問題のバイナリが微妙に仕様と違う計算をしていることを疑ってばかりだったのだけど、たいていのケースでずれる理由は与えてる初期時間がおかしいことだった。まぁ妙なコードを適当に書いたらそれなりに動いたので OK とした。 validation で増えるテストケースをさばける自信が無い感じだった。
300x 。手作業でやっていた微調整を自分でやるのは大変だった。バイナリサーチ書けば良かったんだろうけど、ローカルミニマムとかあるんじゃないかなぁというのと、実装がラクな方が良いということで、もちょいヘチョいのを書いた。最初に 10 値をずつずらして 10 分割した中で一番良いものを選んで、次に 5 ずつずらして…というのを繰り返すヤツ。これは遅かったのが問題だった。最後まで問題だった。よく考えると収束したら終了するくらいのことはしておけば良かった。この作業を 200x に移植して 200x も安定感が増えた。ただ 3003 が微妙にあやしい感じだったので、汎用的にするならもうちょっと良い補正方法を考えないとなぁと思いつつ、そろそろ人生に疲れてきたので 400x へ。
400x 。基本は複数ターゲットがいるだけで 300x と同じでいいだろう。むしろ軌道に 900sec 乗るのが苦手だったので、こっちの方が簡単だ。月には到達できないが、とりあえず近傍のいくつかを回収できるようにしたい。問題は月だなぁと思いつつ、まぁそんなに大きくズレないようなので、補正フェーズで正確なシミュレーションができてりゃいいだろう、と月入りシミュレータを実装。微妙にズレる。色々調べてみると、まずそもそも月の位置の計算がおかしい。これはアホみたいな話だけどテストプログラムで input として自機との相対位置を喰わせていたのであった :)
しかしまだバグっていた。まず自機とその他で誤差の量が違う。その他から直そう。とりあえず VM の吐いた C コードをゴルフしていけばリバースエンジニアリングできるだろう…とガリガリやっていた最中に、ふとこの VM の仕様で月の前回位置ってちゃんと覚えてるのかな? と思った。厳密に計算するなら、月の2回分の位置が重力として必要なのだけど、ナイーブに実装するなら前回の位置を2回使うとか、今回の位置を2回使うとかいうバグがバイナリにあっても不思議はない。適当にやってみたところ、今回の位置を前回の重力計算にも使ってそうなことが判明した。
これで誤差は相当減ったが、自機だけ相変わらずおかしい。これひょっとして自機って月無視してなくね…と思って自機のシミュレーションだけ 300x 以下用のに変えてみたところ、動く。アホかー。そしてそのすぐ後に 400x バイナリのアップデートが行なわれていた。アホかー。
で 300x ベースの 400x のコードを適当に走らせて、4位に復帰。そして寝る。
起きても8位だった。これは結構頑張れるなーと思う。
400x をいじっていく。 300x ベースだったので対象に近付いてから対象の軌道に入るコードだったのだけど、よく考えると自機は円軌道を描いてる前提なので、対象の軌道に近い円に補正する方が賢い。そう変更すると対象が楕円軌道描いてるヤツのスコアがかなり良くなった。 300x の名残りで対象は常に最初に発見した一番近い子、ていう感じだったんだけど、現在一番近いもの、に変えたら楕円の 4002 が良くなった。これで5位に。
このへんで 4004 は月以外パーフェクト、 4002 もかなり良くて、 4001 と 4003 がイマイチな感じだった。 4001 とかをビジュアライザで眺めていると、最初の方は調子が良いのだけど、後の方になると対象との周期差が少なくて、いいタイミングを待ってる間にタイムオーバーになってしまうとわかった。だから対象が反対方向に動いてる 4004 や、楕円を描いてる 4002 は成績が良い。
どうしたもんかなぁと思ったけど、とりあえず 100x のコードを持ってきて、対象が近い時は一旦対象から離れるようなコードを書いてみた。全然ダメ。時間の無駄だった。このへんでどうしたもんかちょっと思いつかなくなる。
そこで、後顧の憂いがあるのがうざいので、不安定そうな 300x を見直そうと思った。 400x の経験を生かしてみたりしてから、やっぱ 900sec ちゃんとついていくかどうか simulation してから挙動を決定すべきだよなぁと思って、確実に 900sec ついていけると判断した時だけ飛ぶようにした。まぁ当たり前なんだけどね。後 900sec ついていけるように、近傍についてから 900sec の間 adjust するコードを入れた。終わってから気付いたのだけど、燃料使ってる間は 900sec にカウントされないらしいので、このコード微妙に失敗するのに飛んじゃう可能性があるなぁ…ああバッファ考えて 1500sec 大丈夫だったら大丈夫、ってことにしてたんだけど、これが 1800 なら良かったのに…ギギギ。逆にうまくいく自信がある時は無駄に時間と燃料を浪費してるしな…
200x も同じロジックでいこうと思った。 200x のコードに同じ変更を backport するのめんどいなぁ…と思ったのだけど、 300x のコードそのまんまでいけるんじゃね? と思ってやってみた。うまくいった。まぁ対象が円であることを仮定する必要が無いわけだね。
400x に戻る。もうやれることは限られてるが 4001 と 4003 をなんとかしたい。色々考えた結果、常に一番近いのを常に対象としてるのが良くないだろうから、そこを直すのが最も効果的なんじゃないかと推測した。簡単なはずの変更なんだけど、完全にコードが対象1体を前提にしてたので、結構大変だった。最初はこの変更は全然うまくいかなくてがっかりしたけど、 magic number を色々調整したらかなり良くなった。これが良くなってる感触を得たのだけど、なにぶんアドホックな遅い作業を対象の数だけ回してるので、遅くなった。最悪10分、速いやつでも3分程度かかってしまう。
これを生成してる間に leaderboard が閉じられつつあるという情報を irori さんからゲット。それなら世界7位より6位の方が良いだろう、と計算が終わった 4001 をサブミット。よし6位だ。きねん写真をとってちょっとすると leaderboard 消えたという話。消えるんなら急ぐ必要なかったなーと思いつつ、他のヤツも submit …したたタイミングでスクリーンショットとりやがりましたよヤツラ! 騙し討ちです。ゆるせません。私が最後に見たのはこんなものでした。
Position Score Team Problems Solved 1 5171.5322 pepsiso 16 2 5025.1531 THIRTEEN 16 3 4685.6003 wiiphonies 16 4 4406.2437 Side Effects May Include... 16 5 4246.8523 Intercaml 16 6 3948.0274 shinh 16 7 3861.0396 jabber.ru 15 8 3718.6164 7-15 16 9 3618.2471 Purely Functional Infrastructure 16 10 3532.0610 irori 16 11 3531.0112 Pluk 15 12 3431.6513 cashto 16 13 3341.2227 BSM 16 14 3170.9021 Krakow Dragons 16 15 3111.3151 OneDayPastDue 14 16 3102.3321 Pokryshkin 16 17 3075.7607 NCSU ARC Alums 16 18 3066.0340 Cult of the Bound Variable 13 19 3033.8702 The Blind Hen 14 20 3026.4666 The Usual Suspects 16
やまぁそれはいいです。対象を増やす変更は、楕円を描いてる 4002 をかなり悪くしていた。調べてみると、燃料使いすぎということだった。 4002 とか全員近付いてくるから全員が対象になっちゃって、さらにそれらが離れてくもんだから、やばいんだよねーと思って、まぁ普通に燃料制限を適当にかけてみた。これはうまくいった。予定よりうまくいって、 4002 も全部回収できるように。ただ必ず燃料3500以上必要なシーンで飛び立てなくなってしまった。これは地球にムチャクチャ近いところからスタートとかさせられるとヤバいけど、大丈夫なのかなぁ。あんまり時間も無いわけだし、今回も前回同様、テストケースはそこまで難しくないと推測してるんだけどな。値のスケールを変えることに本質的な意味はないしね。
なんかもう思いつかなくなったし、そもそもテストが遅すぎてつらい。残りの時間はパラメータ調整だけやりつつ他の部分見直そうと思う。
まぁすぐに思いつくのは 100x の燃料使えば使う程点数が増えるというルール。やれば100点以上増えるしね。ただ validation でコケないように気をつけてコーディングしないといけない。まぁ色々注意しつつ 100x の安定度も上げた。この際 100x のアドホックな修正コードは捨てた。
4001 8体、 4002 9体、 4003 9体 (あれ YouTube に上げたバージョンは月以外全部落としてるね…でも点数落ちた記憶はないので、燃料なり時間なりの理由で点数増えたのかなぁ)、 4004 は割と余裕で10体、という感じだった。 4004 は時間も燃料もかなりあまってたので、 kinaba さんとこの後で見るに月行くのってスイングバイとかせんでもあまり燃料いらないので、案外頑張れば行けたんじゃないかなぁとか思って少し残念だった。
2日目以降は、 Top10 に入る前提で、 validation に耐えることを主眼に置いてアドホックな修正はなるべくしないようにしていたので、 Top10 に入れてるといいなぁ…手動入ってる人が上位に多いと割と上にいけるかもだし。
そういや終わった後にちょっと思ったんだけど、 4001, 4003 に対して、回りのヤツ落としたら一旦地球からかなり離れてしまって、速度が減ったところで逆進して、残りのヤツを狩るとかすれば面白かったんじゃないかなぁとか思った。スコアのルール的に燃料減らしちゃうのはマズいですかね。
反省としては、ビジュアライザもっとよくしておくべきだったなぁと。少なくとも燃料やスコアを表示をしておくべきだった。後アルゴリズムが現在考えてることの表示と。それにビジュアライザ遅かったんだよな。 VM もビジュアライザもそれ自体は良かったんだけど、たぶん通信のために printf と scanf してるのが遅い。ちゃんと本体に組み込むのをやるべきだったかな。ただ 1,2&3,4 それぞれにビジュアライザ組み込むのがめんどかったんだよな。 4 だけでもやればよかった。
後シミュレータが完全になってからは、実際に VM 走らせずに最初から最後までのプランを計算してやる方が良かったと思う。その方が速いし。ビジュアライズもシミュレータだけでできるはずだしな。それをやらなかったのは途中までシミュレータが色々バグってて信用できなかったからだったのだけど。
そういう意味で、一般的に、信用のおけるパーツを一つずつきちんと組んでくのは大事だなぁと思った。あまり中途半端な段階で飽きて次に進むのはあまり良くない。ただまぁ 300x 中途半端で 400x やって、その成果を 300x にかえすとかもできるし、今回は問題のバグもあって完璧なものを作ることができなかったあたり微妙な感じではあったけど。
逆に今回は VM ちゃんと作ったのは良かった。速いしバグが無いと信用できる部品があるのは良いことだった。
