takumi152の競プロ日記

競プロとかその他諸々とかの記録

AHC003 参加記

とても面白い問題でした。

問題

atcoder.jp

30*30の辺重み（長さ）付きグリッドグラフがある（ただし、各辺の長さは入力としては与えられない）ので、以下のクエリを1000回処理してねという問題です。

  • 各クエリの入力として、始点と終点が与えられる。
  • 出力として、始点から終点までのできるだけ短いパスを1つ求めよ。
  • 出力後、そのパスの距離に0.9以上1.1以下の一様乱数を掛けた値が入力として返される。

各クエリについて、出力したパスの距離と実際の最短距離が近いほど高得点が得られます。
また、後の方のクエリになるほど、以下のように1回のクエリで得られる最大得点が上昇していきます。

f:id:takumi152:20210531023205p:plain

なお、1個のテストケースにおける満点は999,999,910点です。

結果

システムテスト前の点数は96,818,948,890点で、24位でした。

f:id:takumi152:20210531024225p:plain

システムテスト後の点数は2,905,238,839,320点で、順位は変わらず24位でした。

f:id:takumi152:20210531205841p:plain

解法

各クエリごとに、入力生成に使われたパラメータを焼きなまし法で推測（1クエリあたり1.97ms実行）し、求めた推測値を使った場合の最短経路を出力する（探索のために敢えて別の経路を取ることはしない）という方法をとりました。
推測するパラメータは、問題文中の「入力生成方法」のうち、 M = 2と仮定した場合の以下のパラメータとしています（ M = 1の場合は H_{i, 0}と H_{i, 1}の値が大体同じになる（ V_{i, 0}と V_{i, 1}についても同様）だろうと期待してこのような仮定を置きました）。

  • H_{i, p}, V_{j, p}
  • \delta_{i, j}, \gamma_{i, j}
  • x_{i}, y_{j}

評価関数は、あるパスの現在の推測値から求められる距離を a、そのパスを使ったクエリで返ってきた距離を bとして、 1.0 - (1.0 - \min(a, b) / \max(a, b))^{2}を各クエリについて求めたときの総和からペナルティ（後述）を引いたものとしています。
つまり、今までのクエリで返ってきた距離と、現在の推測値から求められる距離が近いほど、その推測値の基本評価が高いというようにしています。
ただし、 H_{i, p}, V_{j, p}の値と \delta_{i, j}, \gamma_{i, j}の値について、それぞれある定数との差異の2乗に比例したペナルティを与えることにしています。これは、パラメータとして現れにくい値（例えば、ある i, jについて \delta_{i, j} = 2000となることはほとんどない）を抑制することで、精度が上がりやすくなることを期待するものになっています。
このペナルティの基準となる定数と、ペナルティ自体の係数は、optunaを利用して設定しました。例えば、 H_{i, p}, V_{j, p}に対するペナルティ自体の係数と、100ケース（seed = 0, ..., 99）のスコアの関係はこんな感じになりました（実際には1000ケースのスコアを使ってパラメータを決めました）。

f:id:takumi152:20210531043927p:plain

optunaを使ったのは今回が初めてでしたが、簡単に使える上にとても便利だなと感じました。
実際、optunaを使って決めたパラメータを使った結果、手動で決めたパラメータを使った場合よりも、点数が0.33G点ほど上がりました。

感想

今回は焼きなましをしましたが、上位勢の方々の解法は機械学習や統計を駆使したものが多かったようです。
上位勢の方々の解法はまだあまり理解できていないので、少しずつその辺の知識を身につけていきたいなーと思いました。
（この辺の知識、ちゃんと身につけられたら業務とかでも普通に使えそう）

今回の解法に至るまで

ここからは今回の解法にたどり着くまでに何をしたかをざっくりと書いていきます。

1日目

問題を読みました。
とりあえず暫定1位を取っておくことを狙って、「クエリで使ったパスに含まれる各辺について、長さの推定値を返ってきた距離の1辺あたりの値に近づけるように更新する（ただし更新回数が多い辺ほど推定値の変更率を小さくする）」という感じの解法を2時間程度で作りました。
この時点での点数は89.87G点で、20分程度でしたが暫定1位を取ることに成功しました。

2日目

この日は実装はせず、考察をしていました。
この時点では、

  • 問題自体の印象として、Multi-armed banditに近い感じを持った
  • だとしたら、最短パスを推測するための探索をどんな感じでやるかが重要になってきそう
  • ということはUCB1とかを使うといい感じに探索ができるかも？
    • どうやって適用するかはよく分からない
    • 適用できたとして、探索による点数のロスは気になる

というようなことを考えていました。

3日目

前日に考えていた考察内容に進展はありませんでした。 一方で、こんなことを考えていました。

  • 過去のクエリとなるべく整合性が取れる推測をしたい
  • 辺の長さを推測するためにはテストケース生成に使われたパラメータを推測すればよさそう
  • 統計とかを使っていい感じに推定する方法はよく分からない
  • とりあえず焼きなましで殴ればよくないか？

そこで、今回の解法の元となった、入力生成に使ったパラメータを山登り法で推測する解法を実装しました（この時点ではペナルティは未実装。また、焼きなましだとパラメータ調整がうまくいってないせいか逆に点数が下がった）。
が、解法の項で挙げた全てのパラメータを推測しようとすると点数が大幅に下がったため、とりあえず H_{i, p}, V_{j, p}だけを推測することにしました。
この時点での点数は95.39G点（暫定98位相当）。

ちなみに、この時点で試して効果がなかった改善案として、

  • 最初の数回のクエリをできるだけ長いパスにする
  • 最初の数回のクエリをランダムなパスにする

があります。

4日目～5日目

この期間は特に進捗はありませんでした。

6日目

山登りの点数計算のうち、 x_{i}, y_{j}の値を変更したときの点数の更新部分にバグがあることが分かり、修正しました。
この時点でも全てのパラメータを推測しようとすると点数が下がったため、 H_{i, p}, V_{j, p}と x_{i}, y_{j}を推測するようにしました。
点数は95.53G点（暫定92位相当）。

7日目

山登りを焼きなましに変更したところ、全てのパラメータを推測したときに点数が上がったため、そのように変更しました。
この時点で点数は95.96G点（暫定66位相当）でした。

一方で、推測した H_{i, p}, V_{j, p}の値と、実際の値が大きくずれていることがありました。これがずれているということは、 \delta_{i, j}, \gamma_{i, j}の値も全体的にずれているはず（ H_{i, p}, V_{j, p}を軸に調整してほしいので、あまり望ましくない）だろうと思い、 \delta_{i, j}, \gamma_{i, j}の値にペナルティを付けたらどうなるか試しました。その結果、点数が上がることが分かりました。 ここで点数は96.27G点（暫定54位相当）になりました。

8日目

前日に \delta_{i, j}, \gamma_{i, j}の値にペナルティを付けたら点数が改善したことが分かったので、 H_{i, p}, V_{j, p}の値にも同じようにペナルティを与えたらどうなるか試したところ、点数が96.48G点（暫定42位相当）に上がりました。

この時点で、コンテスト期間内にこれ以上の改善をするのは難しいだろうと考え、optunaによるパラメータ調整に入りました。調整を行った結果、最終的な点数は96.81G点（暫定24位）になりました。