🧳
AHC036振り返り

2024/09/07に公開
 はじめにRECRUIT 日本橋ハーフマラソン 2024夏（AtCoder Heuristic Contest 036）に参加した。かなり苦戦したので反省も込めて振り返りのためのメモ。

 問題問題は初見では何を言っているのかよくわからかったが、以下のような感じ。
与えられたノード数N(=600)のグラフにおいて、T(=600)個のノードを指定された順番で回る
移動先に指定できるのは配列Bに含まれるノードだけ
配列Bへは配列A上の任意の長さをコピーできる。このコピーの回数が少ない方がいい
NとTが同じだったので、全部のノードを回るのかと思ったが、そうではないらしい。

 処理の順番いかのような順番で処理することを考えた。この順番は最後まで変更していない。

T個の指定ノードを回るルートを算出する
ルートから配列Aを作成する

Bに何をどのタイミングで入れるかを決める

 ルートの算出
 どんなルートを選ぶかL_Bへのコピー回数が少ない方がいいので、総パス長が短いほど良い。さらに、L_Aには通過するノードが少なくとも1つは入っている必要があるが、L_Aのサイズには制限があるので、ノードの種類は少ない方が良いと判断した。
以後最初に最終的な方式、その後に、試行錯誤した案を示す。試行錯誤した案は結局使わなかったのでタイトルに🆖をつけている。

 最短経路ベースで選択する総パス長さを短くするために、指定ノード間の最短経路を求めた。この時、最短経路は複数の候補が導出される、できる限り同じノードのパスを選択することを考える。それぞれのノードiを通過する経路の最大本数を重み w_iとしてパスのコストを重みの合計\sum_{i \in \textrm{path}} w_iで求めることとした。「最大本数」の意味は、指定ノード間の複数の最短経路の中から、1本の経路を選択した時、最大w_i本の経路がノードiを通過するという意味である。
ノードの重み(左)とコスト最大のパス(右)
各ノードの重みと、最短経路の候補からコストが最も大きいパスを選択した時の総パスは上の図のようになる。色が濃い程重みが大きい事をしめしており、中心の方が大きくなっているのが分かる。

また、コストでパスを選択することで、通過するノードを減らす事ができている。
ノードの重みの分布
この時のノードの重みの分布をグラフ化してみると、重み1のノードが多いので、削除することを考える。グラフ理論を使ってできそうな気はしないではないが、単純にそのノードを通る最短経路を、そのノードなして再計算して経路があるかどうかで判断した。
重みの小さいノードを削除した結果
重み20までのノードについてノードが削除できるかどうか判断して、可能であれば削除した結果。結構すっきりした。

 🆖 最短経路以外も候補に含める当初は、多少遠回りになっても、最短経路以外も考慮した方がいいのでは？と思い、2番目に短い経路に対しても「経路の候補」として採用していた。しかしながら、経路の候補数が膨大になって計算時間がかかるのと、経路長が伸びることのデメリットの方が大きかったので、最短経路のみを考慮することとした。
特に計算時間は大きな課題で、2番目に短い経路まで導出していた最初の提出では、制限時間3秒のところ2.7秒もかかってしまっていた。

 🆖 高速道路を作るできるだけ同じ経路を通したいので、ノードを位置情報を元に5×5のマスに分割し、それぞれのマスの中心に距離的に近いノードを高速道路の入口ノードとした。経路を入口ノードまでの最短経路と、高速道路（入口ノード間の経路）の2段階にすることで共通部分の多い経路を選択する。入り口ノードを動かす事で、最適解を見つけることができないかな？という思いで実装。
高速道路を使った例。ピンクが入口ノード
入口を動かすところまで作ったが、総経路長が長くなってしまい、スコアは伸びなかったのでこの方向性はあきらめた。コンテスト期間中はビジュアライズしてなかったのだが、改めて見ると、中心近くもうまくノードを間引けているので、この路線を詰めてもよかったのかも知れない。

 配列Aを求める
 どのようにして作るのか配列Aに求められるのは以下の2つだと考えた。
経路上のノードを全部含んでいないといけない
できる限り経路と同じ組み合わせを持っている
なので、経路パスの先頭から初めて出てくるノードであれば配列Aに入れる。初めてでないが、よくでてくる組み合わせであれば挿入する。という感じで作っていくこととした。

 利用頻度が高いエッジを優先する初出でないノードをどのタイミングで挿入するか？であるが、エッジの利用頻度を算出しておいて、それが高い組み合わせを残すようにしてみた。正直言うと思いつかなかったので、とりあえずこうしてみた感じである。ただ、まだ出現していないノードの数と、配列Aの残り枠数が同じになった時点で、それ以上利用頻度に基づいてノードは入れない。
配列Aの最大連続利用数
後述するが、マッチングした数だけどAからBにコピーする。このコピーの回数を少なくするのが今回の問題なので、できるだけ長くコピーした方がいい。なので、Aの各要素がBにコピーされる時に最大何要素まとめてコピーされたかをプロットした。
最初の方は、最大値であるL_b、この問題だと5個の要素をコピーできているが、後半の方は1つずつしかコピーできていない。これは隣接ノードが既にAに含まれてしまい、孤立したようになっているためである。

 既に同じパターンがあった場合は挿入しないそれよりも問題なのは、0の範囲がある事。つまり、この並びと同じ列が既にAの中にあるということである。完全に無駄なのでなんとかしたいので、4個の既に出てきたパターンを入れようとした時、それをキャンセルする機能を入れた。ここで2個にしないのは、[0, 1, 2]というパターンがあった時、[0, 1, 4]を入れられないため。短くすると今度はバリエーションが減ってスコアが低くなってしまった。
配列Aの最大連続利用数
完全に無くなってはいないが、白い部分を減らすことができた。

 配列Bに要素を入れる
 Xのアルゴリズム旅行好きのXが、あらかじめ決めた経路R = [r_0, r_i, \ldots]を通るアルゴリズムは以下のようにした。
現在の配列Bに含まれるノードで進めるまで進む。ゴールまで進めたら終了
進めないノードr_iからL_B個を経路からとりだし、配列Aから最も多くのprefixがマッチする範囲[p, q]を探す。（r_iは必ず含まれる）
範囲[p, q]を配列Bにコピーし、1に戻る
ここで注意すべきは、配列Bは順番に依存しないこと。例えばこれから先の経路が[4, 5, 6, 7, 8]の場合、配列Bに入れるパターンは[8, 6, 7, 4, 5]でも良い。なので、あらかじめ「辞書」を作ってから対応した。ただ、本当に全パターンを作るとL_Bが大きい時に処理時間が足りないので、連続したものだけを対象とした。

 反省点順位としては200位ぐらいから始まって、あまりスコアを上げる事ができず、最終的な順位としては240位ぐらいであった。配列Aを求める部分が良いアイデアが出せなかったのが原因の１つであると思われる。全部を繋げた経路をベースに作成したが、終了後の解説を見ると各指定ノード間の経路に分割したままの状態で処理をしていた。配列Aを作る時に順番は関係ないので、その方がよかったのかもしれない。
Xのアルゴリズムも必ずL_Bの長さコピーする場合は動的計画法で厳密解がでるので、それをベースにしているようであった。これらの情報を元にどこが悪かったのかの解明をやるのも大事かもしれない。

 おまけ
 rust-parallelを使うアルゴリズムの試行の中で、特定の入力だけに最適化するのはよくないので、複数の入力に対して実行し、その結果を集計する必要がある。それぞれの入力に対する処理は独立で、今時のCPUはマルチコアなので並列化できる。
今回は、rust-parallelを使ってみた。Linux/Macだとパッケージとして提供されているので、導入は簡単である。
rust-parallel -r '(.*)/(.*)' -s 'python3 main.py < {1}/{2} > out/{2}' ::: in/*
記述形式はちょっと独特で、:::以下が入力で in 以下のファイル一覧を使った。-rで正規表現を使って入力を解析、ディレクトリ名({1})とファイル名({2})に分けている。あとは、-sで実行するスクリプトを書けばいい。ここではoutディレクトリに出力している。
昔からあるGNU Parallelと同じものではあるが、Rustで最近いろんなツールが作られているなぁということで使ってみたという話。