見出し画像

AtCoder Heuristic Contest 001 AHC001 参加記 25位でした！！

にゃにゃん(山名琢翔)

ものづくりとプログラミングとルービックキューブが大好きなにゃにゃんです。今回はプログラミングコンテストの「マラソン」というものについて書きます。

「マラソン」とは

通常のプログラミングコンテストでは解が一意に定まったり、最適解が必ず見つかると理論的に証明されている問題が出題されますが、マラソンでは最適解を見つけるのが非常に難しい問題が出て、それに対してどれだけ最適な解を導けるかで点数が付きます。

簡単な例としては、

1以上100以下の整数を1回ずつ使って四則演算して、整数Nになるべく近い数を作ってください。
Nが入力として与えられます。
点数はNと解の値の差の絶対値で与えられます

みたいな問題です(chokudaiさん(超有名人)が例として出した問題のアレンジです)。

私のマラソン歴

マラソン歴はとても浅いです。まだ始めて半年も経っていないと思います。

AtCoderのHack To The Future 2021の予選と本選オープンに出たり、TopCoderのMarathon Matchに3回くらい出たりしました。

過去問ではHack To The Future 2018本選「ツカモの栽培」で記事執筆現在の人類最高得点を持っています。

貪欲解法を書くのが比較的得意で、かろうじてビームサーチと焼きなまし法が書けます。

参加したコンテスト

AtCoder Heuristic Contest 001、通称AHC001に出場し、最終順位25位を獲得しました！暫定では28位だったので嬉しいです！

画像7

(暫定28位)

画像6

https://atcoder.jp/contests/ahc001

問題の要約です。

・10000x10000の正方形の領域に長方形を敷き詰めたい(重なってはいけない)。
・長方形はN個(50<=N<=200)ある。
・それぞれの長方形には目標とする面積がある
・それぞれの長方形にはその領域内に入っていないと得点にならない点が1つある
・Nと、長方形に関する情報(目標面積、点の座標(x, y))がN個与えられる。
・それぞれの長方形の左上と右下の座標を出力せよ。
・点数は各長方形の点数の和で与えられ、各長方形の面積が目標面積に近いと点数が高くなる。

こんな感じで長方形を敷き詰めます。

画像5

ということで今回は私がコンテスト期間中に何を考え、何をしたのかを記事にしようと思います。

点数に関する基本的な考察

理論上あり得る最高点は一つのテストケースで1.0e9点です。採点に使うテストケースはコンテスト中は50個、コンテスト終了後に1000個です。この記事ではテストケース50個の点数と、理論上の最高点に対する割合で点数を表します。

点数の式を見ると、目標面積に実際の面積が近いほど高得点ですが、実際の面積が目標面積より小さいと極端に点数が下がります。

グラフはx軸が目標点数に対する実際の点数の割合、縦軸が得点率です。

画像1

また、少しくらい長方形が目標より小さい分にはあまりスコアが動かないので、ある長方形は点数を捨てて他の長方形の点数を最大化するより、みんなが少し小さい方が点数が高くなると思います。

最終的な方針

とりあえず最終的な方針を先に書きます。

・貪欲解法+焼きなまし法で頑張る
貪欲について
・まずそれぞれの点(入っていないと得点にならない点)について、領域を広くしたほうが良くて、領域を広げても他と重ならなければ領域を少し広くする。これを貪欲1とする。
・長方形をすべてリセットする。貪欲1の各長方形について得点を計算し、得点が低い(領域が狭い)長方形から順番に、領域を広げられたら広げる。これを貪欲2とする。

この貪欲だけで4.0e10点から4.5e10点、得点率80%から90%になります。

焼きなまし法について
・数個の長方形をランダムに選んで、その中で一番点数が低い(領域が足りていない)長方形を1つ選ぶ。
・選んだ長方形の縦か横をランダムに選択して、ランダムに縮める。
・縮めたほうでない辺をランダムに広げる。
・この操作で影響を受けた長方形たちを貪欲に変更する。
・点数の変化で焼きなます。
・温度の高い焼きなましを長時間やったあと、微修正として温度の低い焼きなましを行った。

この操作をすると4.95e10点ほど、得点率99.0%になりました(調べてみると分布は98.0%から99.8%くらいまででした)

得点率98.0%のビジュアライザです。白い長方形は目標面積に近く、青くなると目標面積に足りない、赤くなると目標面積より大きい、といった色付けをしています(公式のビジュアライザは見にくいし途中経過を見るのに不便だったので自前で作りました)。黒い点は含まないと得点にならない点です。

画像3

次に得点率99.7%のものです。

画像4

最後にビジュアライザが動いている様子です。どのように処理が進むかがわかります。


得点状況と順位の変動

コンテスト中の得点と順位の変動をグラフにしました。

画像5

最高瞬間順位は21位で、なんと2回獲得しました。

やっておいてよかったこと

自作ビジュアライザはとても役に立ちました。焼きなましにおいて動いている様子を見ることは大いに重要です。

また、複数のテストケースを実行して点数を計算して、点数の分布も出してくれるプログラムも作ってよかったです。こんなグラフが出てきます(雑なグラフですが)

画像8

特に今回は同じコードを投げても50回のテストケースで0.1%単位のブレがあったので、ローカルでしっかりテストするのは大事だと思いました。

マラソンにおいてコードの綺麗さはとても重要でした。いきなりガツガツ書くのではなく、まず最初にやることを細分化して、よく使いそうな処理を関数にするととてもいじりやすかったです。今回なら焼きなましの処理まで関数化しました。

やっておけばよかったこと

焼きなましが結構短い時間で収束していることにはコンテスト中に気づいていました。これで点数が伸びなければ、局所解にハマってしまっていることを意味します。コンテスト後にこれに気づいて、点数が低い長方形とその周りを一回壊して、再度焼きなましをかけると99.2%くらいまで点数が上がりました。本番中に気づければ夢の順位表1枚目だったのに…

1日目

とりあえず勘で縦に細長い広告スペースをたくさん作ったら良さそうだと思った。優先度つきキューとビームサーチを使って頑張る。4.17e10点。

2日目

ビジュアライザを見て、縦に細長く切っていくとあまり良くない場合があると思った。いくつかの段に分けて縦にスライスするようにした。4.40e10点。

ビジュアライザを見て、少し形を変えたらうまくいきそうなところがたくさんあることに気づく。1つの広告スペースを少し小さくして、その後貪欲をかけて点数の上下を見る山登り法を実装。4.49e10点。

最初の貪欲での段組みの数を2から14までで全通り試して(Cythonの力によってこの貪欲は超高速)そこまでの貪欲で一番点数が高いものを採用して焼きなまし法(山登り法から変更。だが実はバグっていて山登り法と同等になっていた)を使うようにした。4.70e10点。

ローカルで複数のテストケースを実行して点数を計算するプログラムをやっと作る。

時々8.8e8点くらいを取る大失敗ケースがあることに気づく。また、最初の段組みでの点数の大小が最終的な点数に直結することに気づき、ビジュアライザをよく見たところ希望する点が縦方向に密集しているケースに弱いことがわかった(考えれば当然の話)。縦にスライスすることにこだわる意味はないので横のスライスも2から14まで試し、縦横スライス全部合わせて一番点数の高いものを採用し、焼きなましをかけることにする。4.76e10点。

グラフを描いて、エリアが小さい場合の減点が大きい場合の減点よりも圧倒的に大きいことに気づく。

3日目

焼きなましで1つの長方形とそれに隣接する4つの長方形を選んでそれぞれランダムに小さくするようにした。焼きなましはこれでとりあえずおいておいて、貪欲を良くする方針でコードを書いた。

まず盤面を4つの正方形に分割し、それぞれの中で縦横いずれかの1<=X<=8段スライスで貪欲を書き直してみたが、点数が下がりそうだったのでもとに戻す。

最初の貪欲で、隙間が多い配置を採用した方が焼きなましで点数が伸びやすいことに気づく。貪欲終了段階で得点が高く、段組みの数が多く、隙間が多いものを採用するようにした。4.82e10点。

貪欲の段階であまり密に敷き詰めると焼きなましがうまくいきにくいことに気づき、実はスライス戦法はあまり良くないんじゃないかと思い、なるべく正方形に近くなるように貪欲を根本的に変更。4.84e10点。

各長方形の目標値からの外れ方は均等の方が点数が高くなる傾向があるので、焼きなまし終了後にそのバランスを取るようにした。4.85e10点。

処理途中の様子がわかるビジュアライザを自分で開発。

4日目

焼きなましの中で長方形が重ならないギリギリの部分を探す処理を線形探索でやっていたので、二分探索にして高速化。4.87e10点。

乱択を工夫して焼きなましをさらに高速化。焼きなましのwhileが回る回数と更新回数を調べてみると、回数はNに依存するが概ね10000から20000程度、更新確率は1から2%くらいであった。焼きなましの中の処理を少し変更した。4.877e10点。

焼きなまし後の後処理として行っていた貪欲(各長方形の面積が足りない割合を調整する部分)は一部乱択を使っているので、制限時間いっぱい繰り返すようにした。また、点数計算のpowが遅い気がしたので離散化して事前計算しておいた。結果、焼きなましは15000から25000回くらい回るようになった。4.878e10点。

貪欲でどうでも良くて少し重い処理があったので高速化した。また、焼きなまし後の貪欲処理の順番を変更した。4.88e10点。

焼きなましで長方形を小さくしてから軽い貪欲を回していたが、一定の確率で各長方形の面積の足りなさのバランスを取るようにした。4.883e10点。

ここでアイデアが尽きる…

5日目

広告スペースの重なり判定を少し軽くするため、あらかじめ重なる可能性がある長方形の番号を列挙するようにした。また、Pythonのlistを使っていて遅そうなところをCの配列で書き直した。焼きなましのループ回数は20000から50000回になった。なぜか点数が4.87e10点まで下がる…

焼きなましの処理がごちゃごちゃしてきたし、後処理が必要なのは性能があまり良くない証拠なのではないかと思い、焼きなましを書き直す。領域が狭い長方形を一つ選んでランダムに選んだ方向にランダムに引き伸ばし、それによって影響を受ける長方形を適宜アップデートし、そしてこの状態から軽い貪欲をかけて点数を評価するようにした。点数更新などについても少し高速化を試みた。焼きなましのループ回数は30000から50000回程度で更新確率は15%程度。4.884e10点。

焼きなましで軽い貪欲をかけていたが、その処理をさらに高速化した。また、焼きなましが狂っていたので直した(前まで実質山登り法になっていた)。温度調整をして提出。4.896e10点。

焼きなましの状態更新にO(N)かかっていたので、軽い貪欲を修正したことに伴って、状態更新を少し高速化した。ここまでの高速化で焼きなましのループ回数はだいたい30000から150000回になった。また、焼きなましにあったいくつかのバグを潰した。4.907e10点。

6日目

焼きなましの温度の上限と下限、さらに状態を変化させる量をNによって動かすようにしたが、調整が難しすぎて断念。

定数調整。4.908e10点。

焼きなましのバグを潰し、焼きなまし前の貪欲をやりすぎないように(あまり隙間を埋めすぎないように)した。4.910e10点。

状態遷移を更に高速化した。4.912e10点。

コード全体で似た処理を関数にした。また、焼きなましについて状態遷移の処理を少し良くなるようにし、高速化した。焼きなましは100000から350000回くらい回るようになった。さらに、これだけでは点数が上がりそうになかったので貪欲を工夫した。まずこれまでの手法で貪欲をかけ、それぞれの長方形の点数を見て小さい順番にソートしておく。次に一から貪欲をやり直すが、前回の貪欲で点数が低かった長方形から優先的に領域を確保するようにした。4.915e10点。

自作の動くビジュアライザを見ると、焼きなましで最後の方は局所解に収束してしまっている(点数の低い長方形を変化させず、点数の高いものばかり変化させている)ことに気づく。とりあえず最終温度を上げて、温度と確率を計算する関数の高速化をした。4.918e10点。

7日目

貪欲段階での点数と最終的な点数にかなり相関があり、貪欲を改善できないかと思ってビームサーチを試したが微妙で却下。そもそも貪欲が難しい盤面だと最適化が難しいだけな気がする。

焼きなましで最後の方に局所解に収束しているのはもったいないので、焼きなましを前半と後半の2回行うことにした。前半は温度を非常に高くし、後半は低くした。また、前半は厳密な焼きなましではなく、焼きなましの中で出てきた最高点を記録しておいて後半の焼きなましの初期状態とした(温度が高いので必ずしも最終的な解の点数が高いとは限らないと思った)。4.922e10点。

定数調整。特に前半の焼きなましの温度と状態遷移する量を調整した。4.925e10点。

前半の焼きなましで温度が高いと言っても最終解がほぼ最適化されたものなので前半の焼きなましもどきを純粋な焼きなましに戻す。前半の焼きなましの最初の温度を高くしてみた。4.927e10点。

前半の焼きなましの最初の温度をさらに上げた。4.9273e10点。

得点計算は各長方形の得点をそれぞれ計算して合算するようにしていて、計算は十分軽くて高速なもののO(N)かかるため、差分だけ見るようにして高速化した。また、焼きなましを2回行うので今後のために関数化した。さらに前半の焼きなましの最初の温度を、貪欲の点数が高ければ低く、貪欲が低ければ高くした。4.9296e10点。

ただひたすら定数調整(3時間かかった)。4.9306e10点。

焼きなましで状態を変化させる長方形を選ぶ時、何回か乱択して一番スコアが小さい長方形を選ぶようにした。4.9430e10点。

8日目

焼きなましの状態遷移のバグを潰した。4.9484e10点。

定数調整。4.9504e10点。

2フェーズあった貪欲を1フェーズにしてみたが、点数が下がった。

最初の焼きなましで時間が経過すると極端に点数が伸び悩むことに気づく。伸び悩む場合は大抵貪欲もうまくいっていない(全体的に難しいケース)なので、貪欲の結果によって前半の焼きなましの最終温度も変更するようにした。4.515e10点。

焼きなましの確率計算を行う関数で、相対的な点数差だけでなく、絶対的な点数も指標として導入した。それに伴って初期温度や最終温度の調整をした。しかし点数は下がった。

9日目

定数調整がんばった。4.952e10点。

貪欲のバグを見つけた。直して試しに提出したら少し点数が下がったが、手元の100個のテストケースでは少し上がったのでこちらを最終提出とする。あとはシステムテストに祈るのみ…



この記事が気に入ったらサポートをしてみませんか？