約3年ぶりに Heuristic のコンテストに参加しました。競技プログラミング自体ここ数年は離れていたのですが、春休みに元JOIerたちと会い、モチベが出てきていたところにTLでコンテストを見かけ、参加することにしました。
久々の参加ながら、今までで一番ちゃんと取り組んだので、記録を残しておきます。
問題
atcoder.jp
大きな長方形のホールについて、たくさんのお客さんから「これ以上の広さの場所を割り当ててほしい」という要求が何日かにわたってたくさん来るので、それに沿うように各日について場所の割り当て方を決め、長方形を敷き詰めていく問題です。ペナルティは、要求された面積未満しか割り当てられなかったときと、長方形の仕切りを撤去・設置するときに生じます。仕切りの撤去・設置にコストがかかるのがこの問題特有で、前日で使った仕切りをいかに利用していくかが大事になります。
最終的な方針
- 基本的に、行仕切りはほぼ固定で、左上から順に長方形を横に並べていきます。
- 縦の長さ W=1000 を、長さ 153, 134, 125, 106, 93, 81, 72, 66, 53, 47, 38, 32 の行に分けます。なお、この値に論理的な裏付けは一切ありません。
- 日ごとに、その日に発生するスコアを最小化する焼きなましをします。遷移は基本的には並べる順序の2点swapで、たまに1つの行仕切りの有無の切り替えが入ります。
- 各日ではスコアが上位5位以内の解を保存し、次の日には5通りそれぞれの仕切りの初期配置について焼きなましをし、また上位5位以内を求める、というビームサーチをします。
コンテストの記録
コンテストは 3/22～4/1 の10日間で、その間で時間を見つけてやっていく感じでした。
3/26 (5日目)
コンテスト5日目の夜、ぼんやりツイッターを見ているとAHCをやっているらしいという情報が。軽い気持ちで参加登録し、問題を見てしばらく紙に書いて考えました。
長方形を敷き詰めるのに何も制約を付けないのは自由度が高すぎるので、一旦行仕切りを固定してみることにします。まずは扱いやすそうということで、2べきな感じの分け方をしました。1000=500+250+125+62+31+16+8+4+2+1+1 と分けました。 これだと行同士をくっ付けても上の行より幅が短くてうれしそうです。
そうすると、要求面積が大きい順に上から配置していきたくなります。配置しきれなかった分は調整が必要ですが、割と簡単に実装できました。
行の仕切りを付ける/付けないは2^10通りなので、そこは一旦全探索することとします。面積ペナルティが最小になる仕切り方を選びます。
これを出すと82488771点が取れます。400位/800人中 くらいになった覚えがあります。
ここまで一切仕切りペナルティを考えてこなかったので、同じ行の中だけでもうまく調節して前の仕切りを使いたくなります。前の仕切りと置く長方形の辺とをマッチングすることを考えると、DP（+経路復元）でそこそこ高速にできることがわかります。dp[i][j]: i個目まで置いて、j回マッチングできたとき、最小でどこまで埋まっているか とします。これで29395566点が取れ、点数が約36%になりました。
行ったDPは置く順序は動かさないやつでしたが、置く順序もbitDPで決められることに気づきます。その行に置く長方形の個数が小さい（18未満）のときbitDPをすると、25792122点が取れました。これで200位台くらいに入った覚えがあります。
ここで、「500,250,...ではなく別の分け方の方が良いケースがあるのでは？」と思い、200,200,200,...や300,230,170,...といった色々な分け方でこれまでのアルゴリズムを実行し、最も適した分け方で答えることにします。さらに、行仕切りの位置を少しずつ変えて評価する山登り法で分け方を微調整しようとしました。当然重いので、TLE。直そうにも提出頻度制限で結構待たされます。この時点で朝の5時になろうとしていたので眠ることに。ハマるといつまでもやってしまうのが恐ろしいところ......。
3/27（6日目）
起きた後、すぐに昨日のTLEを直したコードを出すと、15567836点が返ってきました。この時点でスコアが最初の提出の1/5くらいになっていて嬉しかったです。
ただ、これ以上の改善が思いつかなかったので、この日はこのまま手を付けずに寝かせました。
3/28（7日目）
ここまでの方針を思い返してみると、行の中で色々配置を変えてはいましたが、行を跨いだ変更は何もしていません。そこで、置いていく全体の順序そのものをいじっていく方針を試してみます。今の方針では決めた順序のままに左上から順番に置いていっているので、逆に言えば最初の順序さえいじれば結果的に行を跨いだ変更もできるわけです。ランダムに順序をswapしていく山登り法を書くと、9099622点が取れます。ついに桁が1つ減りました。
ただ、この時の山登りのイテレーションの回数はなんと65回です。なぜならば、1回1回ちゃんと行の中でも並び替えていて、bitDPの計算が重いからです。
ここで一旦諦めて風呂に入ります。
風呂でぼーっとしていると、「行の中での並び替えって最初に順序を山登りで決めるのであればいらないのでは？」ということに気づきます。そこで、bitDPをやめることにすると、イテレーションを4000回回せるようになりました。これを出すと9186869点で、全然良くなってはいませんが、こちらの方針の方がここから色々改善できることが分かっていたのでむしろ気分は良かったです。
なお、行仕切りの位置も山登り中に動かせるようにしたかったため、遷移は「全体順序の2点swap」「行仕切りを1つ設置/撤去」の2通りで、ほとんどが前者になるように調整しました。
何も考えずに山登りを焼きなまし法に変換し、vectorを配列にするなどの高速化を行ってイテレーションを稼ぐと、6547551点が取れます。
また行仕切りの分け方について考えてみます。試しに 130, 130, 130, 130, 130, 130, 100, 70, 30, 15, 5 にしてみると、手元のスコアが結構伸びました。要求面積的に、縦の長さとして100~200だと収まりがいいケースが多いみたいです。一旦、試した中で一番良さそうだった 120, 115, 110, 105, 100, 95, 90, 85, 80, 60, 40 にしました。
さらに、焼きなましのイテレーション回数をN*Dに比例させるようにし、回せるケースはどんどん回していくことにすると、4381880点が取れます。また午前3時とかになっていたので、寝ました。
3/29（8日目）
明らかなミスとして、「1日目は仕切りペナルティがない」ということを見落としていたので、実装すると4294689点が取れます。ほんの少しの改善。
ここまで右端の壁を使ってきませんでしたが、一番右の長方形は壁まで伸ばすと節約できるので伸ばすことにします。4089468点。
色々パラメータ変えるも伸びず、諦めモードに。
3/30（9日目）
焼きなましの初期解を変えつつ複数回やるように変更してみたら、手元でちょっと伸びたような気がしつつ提出すると伸びず。その分一回の焼きなましのイテレーションが減るので、単に複数回やるだけだとダメなんですね。また諦めモードに。
3/31 - 4/1（10日目）
最後の夜。半ば諦めながらマラソンの記事を読んでいました。すると、焼きなましの高速化手法として、「一定以上スコア減少することが分かった時点で評価関数を打ち切る」というものを発見（shindanninさん、ありがとうございます）。
shindannin.hatenadiary.com
自分の評価関数は、前半で面積ペナルティ、後半で仕切りペナルティを計算しており、後半の計算でsetを使ったりしているので、前半で打ち切れるとうれしい気がしました。実装すると1.5倍ほど高速化され、イテレーションを増やせました。ただ、提出したスコアは4023567点と微妙な伸びに。
さらにマラソン記事を掘っていると、貪欲とビームサーチの対応についての説明をいくつか発見しました。ビームサーチは実装したことがありませんでしたが、現状の解法が日ごとに最適に割り当てる貪欲法であり、折角のオフライン性を無駄にしていると思っていたので、書いてみようという気になりました。グローバル変数を多用した実装のせいで改造は難航しましたが、何とか夜のうちにビーム幅5のビームサーチが完成。イテレーションは減るものの、目論見通り全体のスコアは伸び、2824303点が取れました。パラメータを多少いじったもののそれより良いスコアは出ないようだったので、これを最終提出としました。
大分頑張ったつもりでしたが暫定38位、最終は35位で、1ページ目の壁は厚いなという気持ちになりました。上位陣には行と列を両方焼きなましている人がいて、やはり行仕切りの位置を最初に決定してしまっているのが良くなかったのかなと思いつつ、列仕切りの組み方コンテストならだいぶ上位なのでは、などと考えていました。
AHC Standings を見ると、自分のプログラムは日数の多い場合に強く、Nの大きい場合に弱いことがわかりました。ビームサーチ化の効果という感じがします。N,Dの値によってビーム幅を変えるなどの改善はできたなと思いました。
また、AHC031 - Event Hall - Statistics を見ると、配置が疎な場合に限っては相対的にとても弱いことが分かりました。こういうケースごとに相対評価するスコア計算の場合、ケースの特性ごとに効いてくるやり方が変わってきそうなので、苦手なケースの特徴を洗い出すのが大事そうです。
感想
スコアをじわじわと伸ばしていくのが気持ちよかったです。ビジュアライザも見やすくてグッドでした。
Algorithm は限界を感じてやめていたのですが、Heuristic はまだ向いている可能性が残されているので、AHCはまた出ようと思います。
