AtCoder Heuristic Contest 001 参加記録
これはAtCoder Heuristic Contest 001に参加した記録です。 最終段階で48,919,878,271点、暫定順位は120位でした。
— ぬるぬし (@00nuushi) 2021年3月14日
コンテストのトップページ atcoder.jp
やってみるまでは学会前だしそんなにやらないだろうなと思っていたのですが、あまりに楽しいので空き時間はAHCのことを考えない時間がないくらいには取り組みました。あまりマラソン型コンテストは参加したことありませんでしたが、AHCは今後もやっていきたいなと今は思っています。
問題
最初に問題を読んで、長方形の枠がN個あって枠の中に1つピンがあり、ピンが枠の境界を越えないようにしながら枠同士を押し合いへし合いして動かして広げて最適な面積に広げる感じのことをしたいのだなと思いました。枠というのは問題文で言うところの広告のことで、以下では広告として言及します。
この最初の理解の気持ちのまま割と最後まで解きました。
詳しくは問題ページを見てください。
1日目
自明な解
全部の広告の面積が1のものは自明にACとなります。これを提出すると823,090点でした。
1．とりあえず何かにぶつかるまで押し広げる
面積1の広告を基に、とりあえず位置は固定したまま上下左右をぐるぐる見ながら、広告を広げることが出来てかつそれがスコアを上げるなら広告を幅1ずつ広げることを繰り返しました。
これを提出すると45,268,726,139点でした。全ケースの広告を平均して0.9の満足度を得ました。
2．ゆさゆさしながら押し広げる
引っ掛かりがあるせいでデッドスペースが生まれがちなので、箱にものを詰めるときのイメージでゆさゆさ振りながら広告を広げたらいい感じに埋まるんじゃないかなと思ってそうしました。
これを提出すると46403189229点でした。最初の思い付きはここまでで、ここから少しずつに改善していきました。
- とりあえず時間いっぱいゆさゆさする（46,768,556,034点）
- 拡張する方向をランダムに設定する（47,101,438,138点）
- 拡張する幅を広げられる最大幅と面積に応じて変化させる（広い面積が必要な広告ほど速く広げるようにする。47,237,971,881点）
1日目はここまででおしまいです。確か80位ぐらいでした。
2日目
最初は何も思いつかず、とりあえずログを可視化するプログラムを作りました（上の動画のもの）。OpenGLなるものを勉強しながらやりましたがこっちも結構楽しかったです。
そうこうしているうちに、以前に参加したマラソン型コンテストのHTTFで、山登り法だったり焼きなまし法だったりといった名前を聞いたのを思い出しました。一部の操作をなかったことにして部分的にやり直してスコアが上がったら元々そっちをやっていたことにする、みたいな方法だという認識です。
今回の操作は順序がスコアに一切関係ないのでこれがやりやすそうだなと思い、これをすることにしました。
1．満足度の低い広告の周辺を消してやり直す
満足度の低い広告の周辺広告を爆破して面積1の状態に戻し、再びゆさゆさしながら拡張しました。面積1にするか1/4の面積にするかとか、満足度の低い広告も面積1にするか8割ぐらいにするかとか色々検討した気がしますがどれがどのくらい効いたか忘れました。
提出を振り返るとおそらく山登り法で47,919,875,095点、焼きなまし法で48,664,973,298点を得たはずです。
2．満足度の低い広告をじわじわ外側に押し広げる
ログを見ていると、満足度の低い広告が高い広告に囲まれているケースもあり、とりあえずこれはじわじわ満足度の低い広告を外に広げるととりあえずスコアが上がるよなと思ってそれをしました。あと、おまじないとして#pragma GCC optimize("Ofast")をつけたりしました。
が、微増で48,669,968,903点でした。
このあと、爆破する広告を隣の隣まで広げたり、1と2を行う割合を広告の満足度に応じて調整したりとか色々しましたが最高得点の更新には至りませんでした。実行時間を1分にすると全体平均が0.98にぎりぎり乗るか乗らないかぐらいになり、あと10-20倍高速化出来ればなぁと思いながら2日目は終わりました。確か30位ぐらいでした。
3日目
平日になったのでコードをいじって実験する時間はあまりなく、方針を新たに考えていました。思い返すと、何度も同じ場所を爆破しては不採用を繰り返すような場所がありました。そして、長時間計算させて得た結果ではそのあたりが短い時間のものと大きく変わっていました。
こういう場所は、最良ではないがローカルには良い結果であるためにそこから中々抜け出せない領域だと考えられます。
1．レプリカ交換
こういう山を越えて広くサンプリングする方法としてMDなどで使うレプリカ交換法が思い当たり、とりあえずレプリカ交換の実装は研究にも使えるかもしれないからと嘯いてコードを組みました。
組み終わってとりあえず流してみると普通の焼きなましより若干スコアが出ていませんでした。パラメータの調整をするかと思い、レプリカ交換の効率を上げるには各レプリカ間の交換確率が20％程度になるようにするのが良いとものの本で読んだのを思い出していたのですが、よく考えるとそのような温度設定は割と系によるのでは？と思い、任意の系に適した温度の自動設定を考えるのが簡単ではないなと思ったのでこれは止めました（未提出）。
レプリカ交換自体は並列計算が出来るのが割と嬉しいポイントな気がして、レプリカの温度を系に合わせてチューニングして性能を出すので、今回のマラソンコンテストのように多くのテストケースについて良いスコアを出すのには向いていないような気がしました。
ただ、コンテスト終了後にAHC001タグを見ていると多点スタートは効くというような話をみかけ、僕はレプリカの生成をさぼって同じ初期構造を複製していたので、ちゃんと温度ごとに初期構造を生成すれば今回の場合は性能が出たのかもしれません。システムテストが終わったら試してみようと思います。
2．細長い長方形を作る
どうなったら嬉しいかを考えたとき、普通に焼きなましてたら中々なれない形にさせたらよいのでは？という発想になりました。そこで、スコアの悪い広告を選んで縦か横に幅1で伸ばした長方形を作り、そこから焼きなますことをやってみました。 が、これは全然効果はなく、スコアの更新には至りませんでした。
結局2日目のコードの整形などをして微妙に点数が上がり48,796,792,032点になりました。40位ぐらいでした。
4日目
細長い長方形を作る2
3日目の細長い長方形を作る話をもう少しちゃんとやることにしました。スコアの低い広告について、他の広告がサイズ1のときに置ける長方形で幅が200以内のものを全探索してスコアの大きい順にスタックし、爆破機会が訪れるたびにその長方形で順番に置きなおしてみて、それとオーバーラップした他の広告を爆破して焼きなますことをやってみました。ゆさゆさして広げたときにスコアの低い広告は、だいたい正方形に近い形状で置こうとすると広い面積が確保できないものなので、細長い長方形で理想のスコアを取っておこうという考えです。
これは微増で、48,817,177,515点を得ました。確か50位くらいでした
5日目
流石に学会の準備をしないとまずい状況になったのでマイナーなバグの修正と思いついたパラメータの調整だけ試していました。
微増で、48,821,392,888点を得ました。確か70位くらいでした。
6日目
流石に学会の準備（略）。
確か90位ぐらいでした。
7日目
流石に…（´・ω・`）.;:…（´・ω...:.;::..（´・;::: .:.;:）
焼きなましの回転数をあげようと思ってやり直す広告をある程度選別をしていたのをやめたらスコアが上がりました。「ぼくのかんがえたさいきょうのほうしん」は脳死より雑魚かったということでちょっと悲しかったです。48,878,301,268点で、90位くらいでした。
8日目
学会を見ながら改善案だけは考えていました。簡単に出来る改善やバグ取りをし、多少手を加えてパラメータの調整することで微妙に上がったり下がったりしていました。
あと、#pragma GCC optimize("Ofast")よりも#pragma GCC optimize("O3")の方が1割ぐらい回転数が多かったので変更しました。ついでに#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")もつけるともうちょい速くなったのでこれも付けました。ちなみにこれを付けてもローカルでコンパイルしていると-O2でコンパイルしたときと速度は変わらず、コンパイル時に明示的に -O3をつけるとちゃんと速くなりました。おまじないはよくわかりません。
が、49には乗らなそうだなと思い、新しく方針を考えました。
- 初期構造を整列させて作る
今のやり方はおもちゃ箱に雑多に物を投げ込んでがさがさやっている感じなので、ちゃんと整列して詰めて初期構造を作るとより良いかもしれないなと考えました。 - 密度の低い方に逃がす
スコアの悪い盤面を眺めると、広告の密度が高いところと低いところに分かれているような盤面では、密度の高いところで広告の満足度が下がりがちだということが分かりました。そこで、密度の高いところから低いところへ上手く逃がしてやるような配置をすると良いかもしれないなと考えました。
この2つの実装方針として、
- 初期構造の整列
広告を伸ばすとき、辺に近い順にピンから辺までの間を順に埋め、それが長方形の短辺となるように考えながら、細長い長方形を作る話と同様に良いスコアを出す長方形を探索して広告を置く - 密度を逃がす
盤面を9つに分割し、密度の一番高い領域と低い領域を決定。密度の一番低い領域が中心の領域ではないとき、辺に沿って外の2方向から広告をその領域へと伸ばす。また密度の一番高い領域が中心の領域ではないとき、辺に沿って外の2方向に広告を伸ばす
ことを考えました。こうすれば、密度をならしつつ細長い長方形が盤面を分割してしまってデッドスペースを生むようなことを減らせる気がします。で、他の部分の焼きなましは今まで通りすればそこそこ行くんじゃないかなと。
しかし、これらはちょっと改修が必要で、改修時間が取れずちゃんと実装できませんでした……。多少の改善で48,919,878,271点になり、100位くらいでした。
9日目
学会が終わってから、今から新しいことを試すのは危険だと思い、最終提出用のプログラムを整えることにしました。潜在的なバグがないかローカルで試し、TLEにならないようにコードテストで確認してパラメータを調整して提出しました。
最終時点では暫定120位でした。
あとがき
学会と被ってしまって後半走り切れなかったのがやや心残りです。ですが、自分が思ったよりは成績が出せたので嬉しいです。49にのせるぐらいまではやりたいです。研究ではシミュレーションをしてなんか解析する感じのことをやっているのですが、今見た目に出ている変化を良い感じに定量したいな～といって色々解析を試すのとAHCでビジュアライザを見て改善案を色々考えるのがどことなく似ていてかなり楽しかったです。もしかして自分数日単位のマラソンの方がアルゴよりも好きなのでは？
これまでマラソンはHTTFに参加させていただいたくらいなのですが、色々参加していきたいような、生活リズムが破壊されるのでしたくないような、そんな気持ちです。とりあえずAHCは出ます。
おまけ
マラソン期間中の3月12日にバーチャルシンガーのHACHIさんの3rdシングル「20」のリリックビデオが公開されました。この曲はなんとPreferred Networks（PFN）とタイアップしており、PFNのデモムービー「PFN Digital Asset Generation System:「リアル」「バーチャル」の概念を越えた先にある未来」も公開されています。 www.youtube.com
皆さん良かったら見て聴いてみてください。
これは完全に関係ありませんが、マラソン期間中に開催されたバーチャルとリアルが交差する世界のライブが3/21までチケットを購入するとアーカイブ視聴が可能です。とても良かった……。
【不可解弐Q2情報】
— 花譜 information (@kaf_info) 2021年3月14日
花譜2nd ONE-MAN LIVE「不可解弐Q2」特別再放送をご覧いただいたみなさまありがとうございました。アーカイブは本日0時過ぎから3/21(日)23:59までご覧いただけますのでぜひまたお楽しみいただければと思います。https://t.co/KWyCjTmC9H#花譜 #不可解弐Q2
どうでしょう、AtCoderもVTuberとタイアップとかしませんか？HTTFでニアミスしたにじさんじのハッカーと未来人とかどうですか？僕は無責任に期待しています。真面目に考えると既に両方知っている人が思わぬコラボで面白くなる、以上の効果が中々なさそうですが……
