yatabis' Archives

後世のために書き記しておく

AHC012 振り返り記録

こんにちは、yatabis です。
今回 AHC012 に参加したので、やったことなどを書き残しておきます。

AHC012 は 4時間の短期コンテストでした。
4時間というのは Heuristic の問題を解くには短く、スピード感がとても大事になると思っています。
ABC などより時間が長くて大変なのですが、それでも時間いっぱい使わないと間に合わないことがほとんどです。
また、多くの人が時間いっぱい使っているため、長期のコンテストに比べて費やす時間に差が出にくく、より経験や実力がダイレクトに反映される気がします。

さて、結果ですが、90.0M のスコアで 105位で終了しました。
今回で Heuristic のレーティングが 1500 になりました。
(これは Algorithm のレーティングより上です!)

問題の概要

今回の問題はこちらです。

atcoder.jp

いくつかのイチゴが乗った円形のケーキを、何本かの直線で切り分けます。
特定の数のイチゴが乗ったケーキのピースが欲しい人に対して、なるべくの多くの人の希望を叶えられるよう、ケーキの切り分け方を最適化します。
希望通りのピースを受け取れた人の割合がスコアになります。

やったこと

本番中にやったことや考えていたことを時系列順に書いていきます。

最初の解答

ぼくはいつも、最初の解答はとにかく正の得点が取れるものを爆速で出す戦いをしているのですが、今回の問題では自明解が簡単には作れなそうな感じでした。
諦めてちゃんと考察をしようと思ったのですが、とりあえず縦に細く切っていく方法をまず思いついたのでそれを実装しました。
左端からカット線を徐々に右に動かしていき、その数が欲しい人がいるイチゴの数になった時点でカットします。
100回しかカットできないので、どうしようもなく左端の方で極細のピースが 100個だけできて終わるのですが、とりあえず最初の解なのでこれを提出します。
人は平均 500 人、最大 1000 人いるのでもちろん点数は低いです。 20M ぐらい。
これを提出した時点で開始から 23分ぐらい経っていました。

最初の解答のビジュアライズ

atcoder.jp

縦横に切る

縦にしか切らないとすると、明らかに 101個のピースしかできません。
なので、どうしても縦にも横にも切る必要があります。
もちろん斜めに切る方法もあるのですが、そうすると各ピースに含まれるイチゴの数を数えるのがとても大変になるので考えないことにします。
とりあえずランダムで縦横に合計 100回切ってみたらなんとなく良さそうなスコアが出たので、一旦提出してみました。
60M ぐらいになりました。ここまでで 41分です。
ちなみにスコア計算はまだ作っていません。

ランダムに縦横に切った図

atcoder.jp

ランダムサーチ

ランダム性をもたせたら、それを繰り返し生成してもっとも良かったものを提出することで、安定化できます。
ぼくはこれをランダムサーチと呼んでいますが、サーチというにはあまり頭は良くないですね。 せいぜい事故を防ぐ、ラッキーを狙うぐらいの効果しかありません。
それでもぼくがこれをやるのは、スコア計算があれば時間いっぱい回すだけで良いのでラクなのと、スコア計算を作ったらなんか一旦提出したくなるからです。
というわけでスコア計算を作ります。

今回の問題はスコア計算自体がものすごく難しい問題だったと思います。
結局、縦横にしか切らないことにして、各イチゴに対してどのピースに含まれるか、すなわちどの線とどの線の間にあるかを二分探索して求めました。
計算量としては、 O(N \log(K)) になりますかね。
制約から N \lt 10^{4}, K = 100 なので、まあ全然計算できるけど何回もやるのは厳しいといった感じですね。

なんとかスコア計算ができたので、提出します。
今まで Python で提出していましたが、こういう系は試行回数が大事なので PyPy で提出します。
それでも 1000 回ぐらいしか回っていませんでした。スコア計算がやはり重いので。
スコアは 68M ぐらいでした。あまり変わらないかと思ったけど、思ったより伸びましたね。
ここまでで 55分です。意外とすんなりスコア計算できました。

ランダムサーチの結果 seed=0 は苦手らしい

atcoder.jp

山登り法

ここまで来たら、次は山登り法を試します。
近傍への遷移は、とりあえずカット線を一本適当に動かす感じにしましょう。
細かいことは後で考えます。
その前に、スコアの差分計算をしないといけないですね。
さすがに試行回数 1000 回程度だと解の改善が全然間に合わない気がします。

今のスコア計算の方法だと差分更新にするのが難しいです。
近傍を考えると、線を 1本外して別のところに付け替えるので、その周辺のみ更新できれば... とか色々考えたのですが、結局差分計算は諦めました。
諦めた理由は、近傍を作った時点で、スコア計算なしでも 2000回ぐらいしか回らなかったからです。
近傍を作るのに 100 \times 100 ぐらいの配列を deepcopy しており、さすがにもっと上手くやれば速くなるんだとは思うのですが、心が折れてしまいました。

このままだと何ともならないので、封印を解いて Rust で書き直してみました。
そうすると差分計算なしで 10000回以上回ったので、 Rust でやることにしました。卍Rust 最強卍

普段は長期コンテストでは Rust で書くこともあるものの、短期コンテストで時間的な制約で Python で走り抜けることが多いのですが、今回は久しぶりに短期コンテストで Rust を使うことになりました。

山登り法、書きました。
近傍への遷移は、上述の通りカット線を 1本ランダムに選んでランダムに動かします。
移動先は左右の線の間からランダムに選びました。
結果は 83M。かなりいい感じですね。(やや白いラインが目立ちますが。)
休憩も挟みつつですがすでに3時間が経過しています。
残りあと 1時間で、ここから焼きなましていきます。

山登り法の結果 見た目ではもう良し悪しがわからん

atcoder.jp

焼きなまし法

最後に焼きなまし法を試していきます。
時間的にも、方針としてはこれが最後の方針となるでしょう。

山登り法から焼きなまし法への変換はある程度機械的にできて、温度の調節と遷移確率を決めるだけです。
基本的にはこちらの記事を参考にしました。

gasin.hatenadiary.jp

なんだかんだ焼きなましはあまりやったことがないので、結局ほぼ 1時間丸々温度調節(& バグ取り)に使い、最終提出をしました。
これで 90.0M 最終 105位の結果です。

最終提出のビジュアライズ やはりseed=0は鬼門ケースなのでは?

atcoder.jp

さいごに

以上が今回の AHC012 で自分がやったことのすべてになります。

ランダムサーチから山登り法、焼きなまし法という流れでスムーズに進められたので、とても満足です。
結構今まで山登り法まで辿り着けなかったり、焼きなまし法ができなくてビームサーチや乱択DFS みたいな方向に行くことが多くて、何気に今回初めて満足に焼きなまし法が使えたかなという気がしています。

一つ心残りがあるとすれば、スコアの差分計算を諦めてしまったことです。
終わってからも少し頑張ってみたのですが、結局できずじまいです。

あとは、今回自分は縦横だけで切ったのですが、やはりほとんどの人が縦横だけで戦っている印象でしたね。
縦横だけでも十分に条件を満たす切り方があるというのは興味深いです。
最終スコア 99.7M とかの解答や、あるケースで満点が出る解答などもあってとても驚きました。 みなさんすごいですね。

個人的には、今回よく戦えたかなと思っています。
特に、短期マラソンには実は苦手意識があったのですが、今回は満足のいくスコアが出せてよかったです。
今夜は気持ちよく眠れそうです。

久しぶりに文章を書いたので、長々と駄文を垂れ流してしまいました。
今回はここまでにしておきたいと思います。
最後まで読んでいただきありがとうございました!