AHC 027 （HTTF 2024）

AHC 027 （HTTF 2024）参加記

問題は こちら

 

この記事に書いてあること

 

  • 最終提出（プレテスト 189 位）は、汚れやすいマスを TSP で回るのをベースとして、それを倍々に複製しながら、残りのマスを最も良い位置に入れる貪欲
  • マスをグループ分けしたとき、グループ i のマス数を c_i 、汚れやすさの和を x_i とすると、理想的には（頻度を自由に選べるなら）各グループは \displaystyle\sqrt{\frac{x_i}{c_i}} に比例する頻度で訪れるのが最適
  • 二重頂点連結成分分解を用いることで、あるマスの集合とそのうち 2 マス（入口と出口）を与えると、重複なく一度ずつ回って入口から出口まで行けるかどうかの擬似判定がマス数の線形時間でできる（稀に不可能な場合に可能を返すが、ほとんどのケースで大丈夫なはず）
  • グループ分けは汚れやすさが 11 以上のマスからなる連結成分をもとに作成する方法を試した
  • 同じ連結成分内でも比率が 10 を超えるものは別グループにする方法も試した
  • pygame をビジュアライザに使うと便利
  • その他いろいろ考えたけど使えるところまでいけなかった

 

1 日目 - 12 月 1 日（金）

 

考えたこと

  • 汚れがひどいマスを高頻度で掃除するのが最適
  • 最も汚れがひどいエリアを基地として、そこから遠征するイメージか
  • 遠征先は汚れやすさによって数値化して、汚れやすさに比例する頻度で遠征するのが良いか？（理論値の計算は後述）
  • A → B → A → C → A → B → A → D → A → のように、高頻度のものの合間に低頻度のものを挟むイメージ

 

実装してみるがこれムズくない？

この日は提出までいけず。

 

 

おまけ

最初にビジュアライザを見て、カラーモード "d" にしてみたところ、ぱっと見汚れやすさがどれぐらいか分からなかったので、カラーリストを作って、色を見たらすぐに汚れやすさ（ d_{ij} ）がだいたいわかるように練習した。

 

下から 1～10 （ 1 刻み）、 11～20 （ 1 刻み）、 10～100 （ 10 刻み）、 110～200 （ 10 刻み）、 100～1000 （ 100 刻み）。「ある色を見たときにその数値を 1.5 倍までの精度で当てる」（絶対色感）「2 色を見たときにどちらが大きいかを当てる」（相対色感）、ぐらいができれば実用上問題なさそう。

 

 

 

2 日目 - 12 月 2 日（土）

 

1 日目の方針をそれっぽく（雑に）実装

  1. まずは汚れやすいマスたちだけを使って基本のループを作る
  2. 1. の部分は焼きなまし法でやった
  3. 次に全体を 2 倍して、次のレベルのものを最適位置ひとつずつ付ける
  4. 3. での付ける位置は汚れやすさの順に貪欲にした
  5. 3. と 4. をあと 2 回ずつ繰り返す（つまりレベルの段階は全部で 4 つ）

 

この日瞬間最大で 9 位。絶対スコア 839 M 。

 

 

汚れやすさと最適訪問頻度の（簡略化）理論値計算

いろいろ煮詰まったので、基地からいくつかのループがあるときの（簡素化）理論値を計算してみました。簡単のために次の仮定を置きます。

 

  • 基地（例えば最も汚れやすいマスなど）からのループがいくつかあるとする
  • ループは全部で m 個あり、 i 番目（ 1 \le i \le m ）のループはマスが c_i 個、汚れやすさの合計が x_i であるとする
  • 各ループは互いに重ならず、ループ内でも複数回通るマスはないとする（厳密には基地は複数回通るがそこも無視）とする
  • i 番目のループは k_i 回行うこととし、 k=\displaystyle\sum_{i=1}^{m} k_i とする
  • i 番目のループの k_i 回は理想的に（つまり等間隔で）登場するとする
  • このとき、コストを最小にする k_i を求めたい

 

なお、問題の条件および上の仮定によって、 k_i は（絶対数ではなく）比率のみを決めることと考えられます。

移動回数の和 \mathrm{MOVE} は \mathrm{MOVE}=\displaystyle\sum_{i=1}^{m} c_{i} k_{i} 

i 番目のループに含まれるマスは \displaystyle \frac{\mathrm{MOVE}}{k_i} 回ごとに通るので、このグループからの寄与は一次近似で \displaystyle \frac{1}{2} \left(\frac{\mathrm{MOVE}}{k_i}\right)^{2} になります。よって、問題文で定義される「平均汚れ」は、

\displaystyle \sum_{i=1}^{m}x_i \cdot \frac{1}{2} \left(\frac{\mathrm{MOVE}}{k_i}\right)^{2} \cdot k_i \cdot \frac{1}{\mathrm{MOVE}} = \frac{1}{2} \sum_{i=1}^{m}\frac{x_i\ \mathrm{MOVE}}{k_i} = \frac{1}{2} \sum_{i=1}^{m}\frac{x_i}{k_i} \sum_{j=1}^{m}c_{j} \ k_{j}

と計算できます。ここで q_i = c_i\cdot k_i とおき、さらに \displaystyle \sum_{i=1}^{m}q_i = 1 を仮定します（先述のとおり、比率だけを考えれば良いのでこれで一般性を失いません）。

すると平均汚れは \displaystyle \sum_{i=1}^{m}\frac{c_i \ x_i}{q_i} となります。ちょっと実験すると、これは q_i が \displaystyle\sqrt{c_i\ x_i} に比例するとき、すなわち k_i が \displaystyle\sqrt{\frac{x_i}{c_i}} に比例するときに最小値を取ることが分かり、このときの最小値は \displaystyle \frac{1}{2}\left( \sum_{i=1}^{m}\sqrt{c_i \ x_i} \right) ^{2} となります。

当初は汚れやすさに比例する頻度で訪問するのが良いかと思ってましたが、マスの数が同じなら汚れやすさの平方根に比例するという結果になりました。

また式をよく見ると、複数のループに分ける際、平均汚れやすさ \displaystyle\frac{x_i}{c_i} が均等になるように分けても意味はなく、なるべく偏りが大きいように分けると効率が良くなることが分かります。

 

なお、この仮定では各ループが基地を始点・終点としているとしましたが、元のループに対して「寄り道」をすることで追加的に到達できる部分についても同様の結果が得られます。

メインループを 1 つ決めて、そこからの「寄り道」をいくつか作り、上の理論値を参考に頻度を割り振るという方法もありそうです。

 

例えば次のような方法が考えられます。

  • 汚れやすさがなるべく高いものを使ってメインループを作る
  • 全体を網羅するようにメインループから分岐する「寄り道」をいくつか作る
  • その際、なるべく寄り道部分のセルの汚れやすさに偏りが出るようにする
  • 上で計算した理論値をもとに、寄り道のタイミングを決定する

 

3 日目 - 12 月 3 日（日）

ビジュアライザを見るとコース取りがいまいちすぎる。同じマスを複数回ることが多く、同じところを行ったり来たりすることもある。

悪いところは分かるけど何をすればよいのか分からんぐぬぬーー。

 

無駄な往復をする理由を調べるために TSP 部分の挙動も調べられるようにしてみた。ついでに RGB 目利きにも限界があったので、そのへんも見れるようにした。

 

 

TSP で汚れやすいマスを結んでいるところ（Turn を動かすことで焼きなましの様子が分かる）

 



ビジュアライザはこの前の yukicoder score contest 8 で使われてた pygame を使ってやってました。

 

 

キーで進めたり戻したり、表示する内容（道筋・ TSP の焼きなまし状況・後述のグループ分けや部屋割りなど）を変えたり、マスに表示する数を変えたりする機能を付けた。

手元で実装するとそのままグラフ表示できるのでとても便利。

 

4 日目 - 12 月 4 日（月）

うーん、あまり進捗がない。

貪欲に頂点を追加していくという方法だとどうしても無駄な道ができてしまう。頂点集合を決めてから、そこを重複なく通る方法を考える方が効率が良さそうな気がしてきた。

Line Racing のときに使った二重頂点連結成分分解が使えるのか。

 

二重頂点連結成分分解による簡易判定と道順検索

判定

ある頂点からスタートしてある区画（頂点集合）が一筆書きできるかどうかの判定をしたいが、これは二重頂点連結成分分解を使うと概ね判定できるはず。稀に例外があるけど、ほぼ出くわさなかった気がする。二重頂点連結成分分解は頂点数に対して線形時間でできるので時間効率も悪くない。

 

  • 区画全体を二重頂点連結分解する
  • 各連結成分は木になる
  • 木が直線でなければ一筆書きはできない *1 
  • 直線であれば、各連結成分の要素をすべて選びながら順に進んでいくしかない
  • 各連結成分では入口と出口が一意に決まるので、連結成分ごとの判定に帰着できる（最後に到達する連結成分は出口に自由度がある可能性があるが、何パターンか試すことにする）
  • 各連結成分の判定は次のようにする 
    • 入口と出口を除く頂点集合について考える
    • 入口の隣接点のうち複数が葉（次数が 1 ）であれば失敗
    • 出口についても同様
    • 入口と出口の偶奇（市松模様にしたときの色）が異なる場合、残りの頂点集合は偶奇がちょうど半数に分かれる必要がある
    • 入口と出口の偶奇が一致する場合、残りの頂点集合の偶奇は、入口・出口の偶奇ではない方がちょうど 1 だけ大きい必要がある
    • ここまでではじかれなかったものは成功と判定する

 

これでだいたいの場合にうまくいく。稀に反例もあって、図のようなとき、緑から赤マスをすべてちょうど一回ずつ通って逆の緑に行くことはできないが、上の判定法だと可能と判定されてしまう。

 


道順検索

例外を無視して判定が正しいとすると、一マス進んでも条件が満たされるかどうかを判定しながら、 OK になる方向に進めば良い。

（この実装では、一マス進むごとにマス数に対して線形時間かかるので、全体ではマス数の 2 乗オーダーになる。）

 

5 日目 - 12 月 5 日（火）

 

昨日考えてたのもなんかいまいちな気がして、部屋割りをいろいろやってみる。

通常マス（「汚れやすいゾーン」に入ってない）場合の汚れやすさは 10 以下なので、 11 以上のものは必ずゾーンに入っていることが分かるが、逆は言えない *2 。

11 以上のマスだけを見て連結成分をいい感じに分解すれば汚れやすいゾーンをまとめることができそう。同じ連結成分でも汚れやすさの比率が 10 倍を超えている *3 ペアがあれば、複数のゾーンが重なっていることが分かる。ふたつ重なっているとして、どちらのグループに属するかを判定するのはちょっと厄介。

適当に分けてみたけどいろんなパターンがあってむずい。

 

あとこれきれいにゾーン分けできたとして、そこからどうすれば・・・（ゾーンごとの順序焼きなましか？）

 

Seed 4

 

 

6 日目 - 12 月 6 日（水）

 

ゾーン方式だと形がいびつになって回収のときに困りそうだったので、部屋割り（長方形っぽいバージョン）も試してみた（けどここからどうすれば・・・）

 

 

7 日目 - 12 月 7 日（木）

上で書いた部屋内を重複なく回るロジックを入れてみた。 Seed 4 の上部の黄緑部屋を回る様子（ちゃんと重複なく進めてそう）。

 

 

 

進むロジック：

以降としている区間が二重頂点連結かつ一筆書きできる場合は、その条件を崩さないように動く

二重頂点連結でなければ、各二重頂点連結成分に分解して、成分ごとに最適ムーブをする

具体的には、各成分を頂点とする木ができるので、スタートからゴールまで進む

 

例えば、二重頂点連結成分を頂点とする木が次の図のようになっている場合で、①から⑤に行きたい場合は、①→③→①→②→④→⑤→⑥→⑤→⑦のように進む。複数回入る成分があるが、各成分の最初の入口から最終出口までの最適路を作っておいて、横道にそれるときはその部分を置き換えれば無駄なく回ることができる。

例えば②では①からの入口（関節点）から⑤への出口に向かう最短路を作っておいて、④につながる関節点を通ったときに寄り道して行って帰って来る感じで。

 

（左：①→②→⑤と動く場合の②内の動き、右：①→②→④→②→⑤にする場合の②内の動き）

 

あとは部屋の順番を焼きなませばそれっぽくなる。

近傍は①部屋の追加、②部屋の削除（複数ある場合のみ）、③部屋の順番の入れ替え（2-opt）の 3 種類。下記の前提で最終コストが部屋の順番から直接計算できるのでこれを評価関数とする。

  • 部屋のマス数および汚れやすさの合計を前計算
  • 部屋の中は必ずマス数で通れる前提
  • 部屋内の順番の違いは無視

 

連結成分内で重複なく取り切るのが不可能な場合などは、単純に「今いるマスに隣接する訪問予定マスのうち、出口から最も遠いマス」に進むことにした。その結果非連結になる場合は今いるマスを訪問予定のまま残した。

 

 

 

実際に Submission してみると、二重連結判定と最適経路計算が重くて 14 ケース TLE 。。

Submission

 

速度改善方法はいろいろあるのでなんとでもなるんだけど、ここまで実装つらくて萎えてしまった。

 

スコア改善の余地もまだだいぶあるはず

  • 最初の方針では汚れやすさがひどいマスを中心に基本ループを作っていたが、この方針だと部屋内の汚れやすさの違いを考慮できていない
  • 広い部屋や、部屋内部での汚れやすさにムラがある場合に部屋を分割する方法が考えられる
  • 行き止まりの部屋（特に隣接部屋が 1 つだけの部屋）は必ずその前の部屋を二度通ることになるので、ふたつを合体したベースで最適化をするのが良い
  • もともとの仕切りが少ない盤面では、部屋が少なすぎる（ Seed 0 では 2 部屋になるのでこの場合も適宜分割する必要がある
  • 部屋間を繋ぐマスは適当に 1 つ固定したが、偶奇問題があるので少なくとも 2 つは試した方が良い

 

 

 

8 日目 - 12 月 8 日（金）

結局 2 日目（ 9 位のとき）の Submission に戻した方が（TLE でケースが減ってるのを考慮しても）良くなったので一旦こちらに戻しておいた。

 

 

結局その後もアイデア止まりで実装まで行けず、これが最終提出。

 

 

ぐぬぬー

最初の方針と二重頂点連結成分分解をうまく融合させたかったけど、結局独立になっちゃったし後者は TLE しちゃったしで方針ミス感が否めないところ。一週間あるからいろいろ試してみるかーと思ってたけど二重頂点連結成分分解は結構つらいというのを思い出した。 Line Racing のときは（常設でやってたので）制限時間がないので無限時間かけて良かったけど、一週間ぐらいだと自分の実装力だとリスクが大きい。

探索アルゴリズムを使わずに CodinGame の Line Racing をやって Legend になった話 - Kiri8128の日記

 

 

 

End

 

*1:Line Racing のときはどの子に行くのが最善かを木 DP の要領で計算した

*2:ちなみにゾーンに入っていない場合の汚れやすさの平均は約 3.9 で、ゾーンに入っている場合の平均は 84 程度

*3:厳密には、小さい方を a として大きい方が 10a+5 以上