AtCoder Heuristic Contest 001 (AHC001) の参加記を書くはずだったのですが、記念すべき第1回ということで「マラソンに初めて参加したけど、感想戦TLで周りが何を言っているか分からない……。」という方が多そうな気がして、気付いたら初心者向け解説記事*1を書き始めてしまっていました。
ふぁぼ圧、強すぎませんか https://t.co/DuGViXzI80
— TERRY (@terry_u16) 2021年3月15日
参加記はまた後日書きます。→書きました。
- 問題概要
- はじめに
- 正の得点を得る（823,090点）
- 山登り法を導入してみる（452億点）
- ちょっと改善してみる（469億点）
- 焼きなまし法を導入してみる（477億点）
- さらなる改善
- Tips
- おわりに
問題概要
社のスポンサー企業が広告を出そうとしています。企業
は、点
を含む面積
の広告スペースを希望しています。できるだけ満足度の合計が高くなるように広告を配置してください。
はじめに
ABCのようなアルゴリズム系コンテストと、AHCのようなヒューリスティック系コンテストとでは、アプローチの仕方を変えた方が上手く行くことが多いです。具体的には、乱択（ランダムに選択する）を使った「山登り法」や、その発展である「焼きなまし法」などが強力な武器になります（もちろんこれらが使い辛い問題もありますが、結構汎用的に使えてなおかつ強力な手法だと思っています）。あんまり型にはめすぎるのもよくない*2ですが、最初のうちは既存の手法に当てはめてみて、そこから自分なりのアレンジを加えていくと良いのかなと思います。*3
この記事では、コンテスト中の私の思考過程にある程度沿った形で、ヒューリスティック系コンテストの典型的な取り組み方について紹介したいと思います。私自身、Introduction to Heuristics Contestで初めてヒューリスティック系コンテストに参加してから半年ちょっとしか経験がないので、間違っている点などあれば優しくマサカリを投げてくださいね。
正の得点を得る（823,090点）
問題文を読むと、以下のことが分かります。
- 全ての広告は正の面積を持たなければならない
- 広告同士が重なってはいけない
- 広告がスペースからはみ出してはいけない
- 以上を満たしてさえいれば、どんな出力でもよい
最初から完璧な解答を目指そうとすると、取っかかりがなくかなり難しそうです。しかし、正当な解（WAでない解）を出すだけならそこまで難しくありません。の米粒みたいな広告を各
を含むように置いてみましょう。
の広告なので、他の広告と重なることはありませんし、スペースからはみ出すこともありません。私がスポンサーだったらブチ切れますが、これは正当な解です。これを提出すると、823,090点（暫定50ケース分）が得られるはずです。
山登り法を導入してみる（452億点）
先ほどの解をベースにちょっとずつ改善していくことを考えましょう。さすがに米粒だと怒られそうなので、広告をもっと大きくしたいです。色々やり方があると思いますが、ここでは以下のシンプルなアルゴリズムを試してみます。*4
- ランダムな長方形を選ぶ。
- 選んだ長方形を上下左右のいずれか（ランダムに選択）に1マスだけ拡大してみる。
- スコアを計算してみて、他の広告に重なったり*5、スペースからはみ出したり、スコアが下がったら元に戻す。そうでなければ採用。
- 1.～3.を時間いっぱい繰り返す。
このように、「解をちょっとだけ変化させてみて、良くなったら採用」する手法を山登り法と言います。かなり単純で力任せな解法ですが、こんな解法でも452億点（満点500億点に対し9割）が得られました。1505人の提出者中だいたい610位相当です。コンピュータのパワーは凄いですね。
ちょっと改善してみる（469億点）
先ほどのコードで得られた解をビジュアライザで表示してみましょう。想像だけで判断せず、実際にどうなっているか見てみるのは大事です。
なお、ビジュアライザの出力はいずれも問題文下段にある入力例1に対する解です。またビジュアライザは公式のものに若干改造を加えていて、各長方形のIDの横に長方形ごとのスコア（0～1）を表示するようにしています。
左上や右下あたり、他の長方形が邪魔でこれ以上大きくできない青い長方形が存在するようです。邪魔な長方形を適当にどかせばよさそうなので、先ほどのアルゴリズムに太字部分を追加してみます。
- ランダムな長方形を選ぶ。
- 選んだ長方形を上下左右のいずれか（ランダムに選択）に1マスだけ拡大してみる。あるいは、上下左右のいずれかに1マス平行移動させてみる。
- スコアを計算してみて、他の広告に重なったり、スペースからはみ出したり、要求された点
を含まなくなったり、スコアが下がったら元に戻す。そうでなければ採用。*6
- 1.～3.を時間いっぱい繰り返す。
試してみましょう。
だいぶ良くなりましたね。このように、今のコードの何が良くないのか調べて、ちょっとずつ改善していくのがマラソン系コンテストの醍醐味です。このコードを提出すると、469億点が得られました。本番429位相当です。
焼きなまし法を導入してみる（477億点）
もう一度ビジュアライザを見てみましょう。やっぱり周りが邪魔でこれ以上大きく出来ない長方形がいくつかあります。また重要な考察として、今回の問題のスコア計算式では、面積1.0の長方形と面積0.6の長方形を作る（1.84点）より面積0.8の長方形を2つ作る（1.92点）方がスコアが高くなります。一人をいじめるのではなく、みんな平等に我慢させましょうということですね。
ではどうすればいいか考えてみると、拡大するだけではなく適当に縮める操作を入れればよさそうです。しかしここで問題があります。長方形を縮めると基本的にスコアが下がるので、上記のアルゴリズム（スコアが下がったときは不採用）では絶対に縮むことはありません。だからといってどんな変化も採用してしまっては、伸びたり縮んだりするだけで一向にスコアが改善しません。そこで、スコアが下がった場合はある確率で採用することにしましょう。こうすることで、
- 毎回ではないが、たまに長方形を縮めることができる。
- スコアが上がる方が採用確率が高い*7ため、一時的にスコアが下がっても長い目で見ればだんだんスコアが上がっていく。
の2つを達成することができます。このように、山登り方の考え方に加え、スコアが下がったときもたまに採用するような手法を焼きなまし法といいます。焼きなまし法の丁寧な解説はIntroduction to Heuristics Contestやツカモさんの解説記事にお任せして、ここではふんわりとしたお気持ち解説だけに留めておきます。
まとめると、以下のようなアルゴリズムになります。
- ランダムな長方形を選ぶ。
- 選んだ長方形を上下左右のいずれか（ランダムに選択）に1マスだけ拡大してみる。あるいは、上下左右のいずれかに1マス平行移動させてみる。もしくは、上下左右のいずれかに1マスだけ縮小してみる。
- スコアを計算してみて、他の広告に重なったり、スペースからはみ出したり、要求された点
- 1.～3.を時間いっぱい繰り返す。
試してみましょう。
中央や右側にあった青い長方形がかなり紫に近付きました。これを提出すると、477億点が得られました。得点率95.5%、本番344位相当の得点です。
山登り法から焼きなまし法への移行は慣れればある程度機械的にできるので、まず実装の軽い山登り法から試してみて、必要に応じて焼きなまし法にスイッチするのがオススメです。
さらなる改善
山登り法・焼きなまし法の基本的な考え方の説明はこれで終わりです。しかし、ここからの工夫の仕方は無数にあります。1位のhakomoさんは山登り法ベースとのことですが、なんと497億点を叩き出しています。皆さんも是非とも色々アイデアを試して、自分のコードを成長させていってください。
Tips
ヒューリスティックコンテストに取り組むにあたってのTipsを適当に書いていきます。
手元でテストケースを回す
順位表の得点は気にしてはいけません。入力が50ケースしかない上、乱択アルゴリズムだと毎回結果がばらつくので全然信用できるものではありません。AHC001のようなシステス方式の場合は特にです。
テストケースジェネレータが用意されていることが多いので、それを使って手元でたくさんテストケースを生成しましょう。できれば1000ケースくらいあると安心です。*8その上で、自動で全ケースのテストを回すスクリプトを作っておくと便利です。結果は毎回記録しておいて、過去の結果と見比べることで改善／悪化を判断しましょう。
手元環境とジャッジとで実行速度が違う問題ですが、個人的にはあまり気にしなくて良いかなと思っています。焼きなまし系の場合実行速度が速いほど得点が高くなるのは確かですが、スコアを最大化するパラメータ
はそこまで大きく変わらないと（私が）思っているためです。実行時間の差がクリティカルに効いてくる場合、手元環境とコードテストでループ回数を調べて、その比を手元環境での実行時間に掛けてあげると良いかと思います。
ちなみに、思い切って16コア32スレッドCPUを買うと1024ケースのテストが3分弱で終わってかなり幸せになれます。（唐突なアフィリエイト）
AMD Ryzen 9 3950X, without cooler 3.5GHz 16コア / 32スレッド 70MB 105W【国内正規代理店品】100-100000051WOF
- 発売日: 2019/11/30
- メディア: Personal Computers
AMD Ryzen 9 5950X without cooler 3.4GHz 16コア / 32スレッド 72MB 105W【国内正規代理店品】 100-100000059WOF
- 発売日: 2020/11/06
- メディア: Personal Computers
私はRyzen 5950X（現行モデル）ではなくRyzen 3950X（一世代前）を使用しています。5950Xは品薄なので高い反面、3950Xは在庫整理でかなり安くなっているので……。上記のように実行時間をあまり気にしていないのも理由の一つです。
コンテスト序盤は特に丁寧にコードを書く
ABCのようなアルゴ系のコンテストではスピード重視で雑にコードを書きがちですが、AHC001のような長期コンテストの場合、あなたが書くコードは今後1週間付き合い続けるものになります。早くアイデアを試してみたい気持ちはあるかと思いますが、1週間後の自分に殴られないよう丁寧に書きましょう。
処理ごとに関数に分けたり、適宜構造体やクラスで情報をまとめたり（今回の場合、長方形クラスを作るなど）するのがおすすめです。
愚直判定を必要以上に怖がりすぎない
ABCなどのアルゴリズム系コンテストに慣れていると、計算量オーダーを気にしがちです。例えば今回の問題で、「ある長方形を移動させた際に、他の長方形と重なっていないか？」を判定したいとき、愚直に1個1個判定するとかかります。なんとなく嫌な気分になりますが、ヒューリスティック系コンテストでは入力の
が小さく、あまり問題にならないことも多いです。
また、最悪計算量ではなく平均計算量を意識した方が良いことが多いです。ヒューリスティック系コンテストでは入力が乱数で生成されることが多く、「最悪計算量のオーダーは悪いが、実際に走らせてみると高速」ということが往々にしてあります（もちろん問題によりますが）。現実世界でも文字列検索などでありがちですね。この辺り、アルゴリズム系コンテストとはちょっと意識を変えた方が良いかもしれません。
適宜assertなどを入れてバグをあぶり出す
ヒューリスティック系コンテストの恐ろしい点として、バグっていてもWAが返ってくるとは限らないということがあります。表示上はACなので、一見正しく動いているように見えてしまうんですよね。かく言う私もコンテスト終盤でそのようなバグを2つ見付けましたし、もしかしたらまだ見つかっていないバグがあるかもしれません。怖いですね。
これを避けるため、「ここでは○○という条件が満たされていないとおかしい」という場所に対して（C++でいう）assertなどを適宜入れて、条件が満たされていないときはエラーを吐かせるようにしましょう。提出時には実行速度に影響がないよう、必要に応じてassertを無効にするのを忘れずに。*9
可能なら関数ごとにテストコードを書くのも良いですね。愚直解と比較するのもアリです。私はサボっていますが……。
パラメータ調整に凝りすぎない
これは私もやりがちなのですが、新しい改善方法が思い浮かばないとき、コンテスト序盤～中盤にも関わらずついついパラメータの微調整に走りがちです。確かにパラメータを変えると大きく改善することもあるので粗いパラメータ調整は適宜やった方が良いのですが、終盤でもないのに0.01%の改善のために微調整を繰り返すのは完全に時間の無駄です。やめましょう。*10
練習用コンテストにチャレンジする
マラソンの練習をしたい場合、以下の問題が比較的素直でオススメです。お時間のあるときに是非†マラソンバチャ†を走ってみてください。
現実世界を疎かにしない
自戒です。
おわりに
いかがでしたか？（テンプレ）
マラソンは自由度が高いとはいえ、やっぱり高得点が取れた方が嬉しいです。この記事が、良きマラソンライフを送るための最初の一歩になれば幸いです。
*1:解説と書きましたが、このやり方が全てではありません。マラソンに「正解」はありません。アプローチの仕方が無数にあるのがマラソンの面白いところです。
*2:脳死焼きなましでスコアが伸び悩んだ経験があるため、自戒も込めて。
*3:なんだかイラストの模写練習みたいですね。
*4:しつこいようですが、マラソンに「正解」はありません。もっといいやり方もあると思うので、是非考えてみてください。
*5:判定の仕方がよく分からなかったので、私は「長方形 重なり 判定」で検索しました。
*6:スコアに変化がなかった場合も採用とします。
*7:こうなるように適切に確率を設定する必要はあります。パラメータは色々実験してみましょう。
*8:真面目にやるなら統計学的にどの程度結果がばらつくか検討した方が良いかもしれませんが、私はいつも適当に決めています。
*9:できれば手元環境／debugビルドでだけ有効になるように設定できると良いです。他言語のことは申し訳ないですがよく分からないので各自調べてください。
*10:自戒
