HTTF2019予選 ばらばらロボット

HTTF2019予選に参加しました。マラソンは初挑戦だったのでメモがわりに。

ランダムに1マス変えてみてスコアがよくなれば採用する山登りをしました。

問題→A - ばらばらロボット

コンテスト中

0:00 問題を読む。とりあえず#は使わないと決意(邪魔だし実装も面倒になりそうなので)

0:07 とりあえず白紙を出してみる(80940点)

0:36 .TDをrandom出力したものを提出(66336点)

TとDだけにしたのはこの時点でシミュレーションがDとTしか書いてなかったからだけどどうもTとDは微妙っぽいことがわかったので結果としては収穫だった。

0:45 なんか提出してみたくなったので白紙からTとDだけで山登りしたやつを提出(76065点)。山登りで白紙からスコア下がるのなんでやねん。

1:05 バイトに行かなきゃいけない時間になったのでとりあえずもう1回出してみる(80162点)。山登りとは。

4:18 バイトから帰ったので再開。バグの原因はxとyを逆にしてたからだった。競技プログラミング初心者か？(実際始めてから1年経ってないので初心者なんですね。)そこだけ直して提出(107803点)。やっとまともな点数が出たので安堵。

4:30 やっとLRも実装して提出(91196点)。何でやねん。

4:37 if文でelseをつけるのを忘れていたからだった。はぁ。DTよりLRのほうが効果的だらしいのでDTよりLRに変化させる確率を高く設定してみる。これで提出すると118343点。暫定42位だったので本選いけるのでは？となる(20卒なので20卒内25位で本選に進めるため)。

6:06 上の提出の時点ではループ回数が3000回だったので高速化を考える。変更するマスを通るものだけ再計算するようにする。最初は通るものも変更箇所以降だけを再計算することにしようとしたけど頭がバグったのでやめた。この改善でループ回数が20000回まで増やせたので提出(124795点)。26位に浮上して本選ありがとうという気持ちになる。

7:05 適当にパラメータとかいじって遊ぶけど目立った収穫なし。焼きなましを書いて提出したら点数が下がる。終わってから気づいたけど温度管理でバグってた(1文字変数を競合させるのをやめなさい。)

7:33 4個以上が集まるマスも減点してみると微増(125040)。結局これが最終結果になった。あとは適当に評価関数をいじって終わり。7分前に提出したコードが80682点で爆笑した。

コンテスト後

DTは完全に不要でLRだけでいいらしい。あとなぜか初期値は.よりLのほうが強いらしい。

→DTをなくすと場合わけが減った分とかでループ回数を3万近くまで増やせて125689点

ちなみに全部Lのtextを提出すると82374点で確かに白紙より強いので気づくとしたらそういうところからなのかなぁ。

焼きなましのバグに気づいて直す

→129733点。これコンテスト中に気づいてればと思ってコンテスト中のを直してみたけどいまいち変わらなかった。

TLのプロたち「LRしか使わないなら変更の影響を受けるのはそのマスの上で回転するやつだけ(Sは関係ない)」

→ループ回数が54000回になる。131097点。

プロたち「同じコマンドは圧縮できる」

→ループ回数が12万回まで増える。132825点。

(焼きなまし何もわかってないので適切な温度管理をすればもう少し伸びそうな気もする) 

感想

結果は37位。マラソンデビュー戦にしてはなかなかでは？

バイトで3時間抜けたのはやっぱりちょっと痛かったけど本選には進めそうでよかった。ありがとう20卒。

アルゴに比べて実装重めだけどそれを加味してもバグらせすぎなので反省しましょう。

今後はマラソンも積極的に参加してみようかな。