estie プログラミングコンテスト2022（AtCoder Heuristic Contest 014） お疲れ様でした。
プレテストの結果は 67,798,337 点で 11 位、システムテストは 2,757,683,578 点で 10 位でした。AHC の最高順位は今まで 25 位だったので、大きく更新できて嬉しいです。
問題概要
頂点を 1 つ増やして長方形を書き足すという操作を繰り返し、頂点の重みの総和を最大化する問題です。頂点の重みは中心からのユークリッド距離の二乗で定義されています。
操作を行うときに次の条件を満たす必要があります。
- 長方形のちょうど 3 頂点が既に存在している。
- 長方形の外周上に他の頂点が存在しない。
- 他の長方形と辺を共有しない。（辺が交わってもよい。）
詳しくは公式の問題文を参照してください。 atcoder.jp
方針
焼きなまし法を使用しました。いくつかの操作を取り消して新しく操作をやり直すということを、焼きなまし法の遷移として採用しました。
部分的破壊と修復を繰り返すというのは AHC001 でも見られた方針だと思います。
操作の依存関係
書き加えた頂点を別の操作で使用することがあるため、操作には依存関係があります。依存関係を無視して操作を取り消すと無効な解となってしまうため、依存関係を適切に把握する必要があります。
次の例を考えてみます。
書き加えた頂点が長方形を構成する他の 3 頂点に依存するため、次のような依存関係があります。
後に追加した頂点は先に書いた長方形の辺上にあるため、この 2 つの操作は入れ替えることができず、次のような依存関係もあります。
locks[x][y] = 頂点 (x, y) が他の頂点から依存される回数
とすると locks[x][y] = 0 となる (x, y) が削除可能な頂点ということになります。
破壊アルゴリズム
次のようなアルゴリズムで解を部分的に破壊します。
- 破壊する矩形領域を無作為に決定する。
- 削除可能な頂点を列挙する。
- 削除可能な頂点をシャッフルしてスタックに積む。
- 次の処理を何度か行う。
- スタックのトップの頂点を削除する。
- 新しく削除可能になった頂点をスタックに積む。
操作の優先度 その1
やみくもに探索するよりも、「よさそうな解」を優先して探索したほうが上手くいきました。
「よさそうな解」とは、例えば次のようなパターンをもっているものだと考えました。
軸に平行な正方形は市松模様のように 1 つおきに配置されていて、斜めの正方形は 1 列飛ばしで配置されていることがわかります。
- 軸に平行な
の正方形は、左下の頂点 (x, y) について x + y が偶数なら優先する。
- 斜めの
などというように、偶奇を決め打ちして優先度をつけました。
上下左右の領域で独立させたかったため、全体を次のように 4 つにわけ、それぞれで偶奇を決め打ちしました。
焼きなまし法の初期解として、偶奇のパターンを 256 通り全探索してスコアが高かったものを採用しました。
操作の優先度 その２
可能な操作の数が多いほどよさそうだと考えたため、可能な操作を増やす操作を優先しました。
オセロにおける、可能な指手が多いほど有利であるという特徴を参考にしました。
操作の優先度 その3
大きい長方形を使うと頂点が疎になりそうだったので、周の長さが短い長方形を少しだけ優先しました。
解の絞り込み
単純な焼きなまし法よりも、多点スタートで少しずつ解を絞り込んだほうがスコアが上がりました。
その他
vector をできるだけ array に変えたり、関数のインライニングをしたり、ちょっとした高速化・最適化でもスコアが上がった気がします。パラメータ調整も重要だったと思います。
提出コード
言語は C++ にしました。
入力生成、テスト、無駄な関数を含めて900行弱なので、長期 AHC の割には実装が短かったと思います。
日記
考察したことを雑に書いておきます。
1日目
問題文を読んで、2 週間コンテストにしては設定が単純だと思いました。
とりあえず操作を可能な限り行う貪欲法を実装しようと決めました。
ビームサーチはやろうと思えばできそうですが、グリッドが小さいとは言えないうえに途中の評価が難しそうだと思いました。
操作に依存関係があるので焼きなまし法は難しそうだと思いました。
2 ~ 5 日目
貪欲法の実装をしました。貪欲法で 33 M 点、random playout で 38 M 点ほどのスコアを出しました。
貪欲法では、可能な操作を増やす操作を行うようにすると少しスコアが上がりました。
AHC013 のように、依存関係をうまく解消して焼きなまし法に落とし込めると強そうだなあと考えていたら、依存されていないものから操作を取り消せばいいということに気づいて、操作の取り消しを行う関数を実装しました。この関数の実装には時間がかかりました。
焼きなまし法を完成させて 44 M 点ほどのスコアを出しました。
6 ~ 7 日目
局所探索をよさそうなものに限って行えば、焼きなまし法の精度が上がりそうだと考えました。
モンテカルロ木探索の要素を取り入れたり、得点への寄与率のような概念を取り入れたりしましたが上手くいきませんでした。
8 ~ 11 日目
よいパターンについて真剣に考えました。そこで市松模様のように 1 個おきに正方形を書いたら密な解を得られることに気づきました。
思いついた些細なアイディアが半分以上当たり、どんどんスコアが伸びました。このときが一番気持ちよかったです。
パラメータ調整や高速化も行い、66 M 点ほどのスコアを出しました。
12 ~ 15 日目
スコアが伸び悩みました。
可能な操作を増やす操作を優先するようにしたら少しスコアが伸びました。
bowwowforeach さんの AHC013 の参加記 を読んでいたら「状態を複数持つ」というのがあって、実装したら少しスコアが伸びました。
パラメータ調整を再び行い、最終的に 68 M 点ほどのスコアを出しました。
環境
大学生の夏休みということで 2 週間ほぼ全てを AHC に使えるぐらいの時間がありました。運動をしに出かけたり、映画を観たり、気分転換する時間があったのはよかったです。
マシンリソースはノート PC 1 台だったので、大量のテストを行うには時間がかかりました。コードの変更を行うたびに、序盤は 80 ケース、終盤は 800 ケースを試して評価しました。800 ケースでもスコアがぶれやすかったので、サーバを借りてテストケースを増やすとよかったかもしれません。
反省点
改善できそうな部分について述べます。
枠について考える
公式の解説配信 で述べられていたことです。
頂点から伸ばせる辺が最大 8 つあり、その枠の合計を減らさないように評価値をつけると確かにうまくいきそうだなあと思いました。
適切に実装すれば「操作の優先度 その1 その2」の上位互換になりそうです。
破壊方法
私は外側から操作の取り消しを行いましたが、ある頂点を削除すると決めて、その頂点に依存する全ての頂点を削除すれば、内側の部分もうまく焼きなませてスコアが上がりそうです。
高速化
焼きなましの状態として、点の有無や辺の有無についての情報を保持する必要があります。
私は edge[x][y][d] = (x, y) から方向 d に突き進んだときに最初にぶつかる頂点 という少し変わったものを採用しましたが、各直線を 64 bit 整数で表現したほうがビット演算で高速化ができそうだと思いました。
ちなみに、私の提出における焼きなましの試行回数は 1 万 ~ 15 万回程度で、テストケースによってまちまちでした。
最後に
反省点はあるものの、自己ベストを大きく更新できたのでよかったです。
writer の wata さん、主催企業の estie さん、参加者の皆さん、ありがとうございました。
次のコンテストも楽しみにしてます。
最後まで読んでいただきありがとうございました。
