マラソン参加記~AHC001~
はじめに
こんにちは、tardigradeです。本ブログでは主に競技プログラミングのマラソンコンテスト(ヒューリスティックコンテスト)についての記事を書いていく予定です。そんなに固い記事を書くつもりはないので、のんびり気楽に読んでいただければ幸いです。
自己紹介
名前は「tardigrade(たーでぃぐれいど)」です。「くまむし」の英訳から来ているので、「くまむし」とか「くま」と呼ばれることもあります。競技プログラミング歴はおよそ1年、2021/03/14時点でAtCoder緑です。
AHC001に参加しました
およそ一週間にわたるコンテストでしたが、あっという間に終わってしまったように感じます。
よかった点も反省点もいろいろあるので、本記事でそれを共有できればと思います。何か感想やアドバイス等あれば、気軽にコメントお願いします！
AHC001を振り返る
とりあえず思考の流れを最初から順に追ってみたいと思います。
問題把握
ざっくりまとめると
- 要求された座標を通るように長方形を配置出来れば正の点がもらえる
- 要求された面積に近いほど得られる点は高い
といった感じでしょうか。
最初に考えたことは、「やべぇ、方針が何も見えねぇ」です。ほんとに、冗談抜きで、なんも思い浮かばなくてめちゃくちゃ焦りました。
1回目のAC
なにも思い浮かばなかったのでとりあえず問題を眺めていると、
- 要求されている座標を通るように1マス分だけ確保する
という方法で最低点は取れることに気づきます。焦って一度しょうもないWAを吐きますが、無事正の点は確保します(確か80万点くらい)。
後々使うかもしれないと思い、スコア計算の関数もこの時書きました。
2回目のAC
1回目のACから考えて、
- 要求されている座標を通るように1マス分だけ確保する
- 辺を拡張していく
という方針をまず思いつきました。
重複判定
しかし、辺を拡張すると「他の長方形と重なる」可能性が出てくるので、「長方形が他の長方形と重なっているか」を判定する関数が必要になります。実装が重くてめちゃくちゃバグらせましたが、何とか実装します。
拡張の仕方
将来的には乱択が見えますが、とりあえず初期解がほしいです。
山登り等への発展を考えると、あんまり偏った解になっても困る気がします。
そこで、まずは正方形の形を保ったまま拡張することを考えました。「正方形」と決め打ちしてしまえば、大体どれくらいまで辺を伸ばすべきかを考えるのも簡単ですし、重複判定も若干楽になります(これがとても嬉しい)。
拡張する順番
スコアは「長方形の面積の大きさ」ではなく、「どれだけ要求された面積に近いか」に対して与えられます。要求された面積の小さい物から拡張していくのが効率がよさそうだと考えました。
これで確か2.7*10^10点くらい。
3,4回目のAC
2回目のACの時点で「初期解は正方形で…」ということを決めたのに、なぜか長方形を許すことで初期解を改善できないか考え始めます。この辺の思考の過程はあまり覚えていません…。長方形の重複判定などはどのみち必要になるので、無駄足ではないのですが。
要求されている面積との差が小さくなるように正方形の辺を拡張(伸縮は面倒だったので考えない)するような処理を書き加え、提出しました。それなりに改善されたのでこちらを初期解にすることに決めます(3.1*10^10点くらい)。
ちなみにこの時の拡張処理は、「重複しないようにできる限り拡張する」といった器用なことはできておらず、「決まった値だけ拡張」or「拡張しない」のどちらかが選択されるようになっていました。結構雑な作りです。
5,6,7回目のAC
拡張処理の精度をあげるか、乱択を実装するか悩み、乱択を選択します。いろいろなパラメーターを試して、よさげなものを投げました(大体4.1*10^10点)。
もう少し具体的に言うと、四隅の座標を0~10000の間でランダムにいじって、スコアが改善されれば採用、みたいな感じです。
8~20(?)回目のAC
拡張処理の精度を上げたり、パラメーターを調整したりしていると、実装ミスに気づきます。エラーがでる類のものではなく、やりたかったことができていなかった感じ。
これを修正すると、4.5*10^5点に乗ります。
以降のAC
完全な乱択だと効率が悪いことに気づき、近傍の値で乱択できるようにしました。時間が経つごとに座標の変化量が少なくなるようにすると、4.7*10^10点に乗ります。
あとはパラメーター調整で時間を溶かしました。
反省
良かった点
- 最初何も思いつかなかったけど、しっかり考察を続けられた
- 山登り法までは実装できた
悪かった点
- 実装の本質的な改善ができなかった
- 見やすい実装にしようと思って逆に冗長に書いてしまう部分が多かった
疑問点
- 焼き鈍しでスコアが良くならない…パラメーターの設定の仕方がよくわからん
- inlineってとりあえずつけておけば速くなるのか？
- 手元で、複数のテストケースをいっぺんに回せる方法があれば便利だな～と思った
めっちゃ楽しかったです！！！
