AtCoder Heuristic Contest 003

https://atcoder.jp/contests/ahc003

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/25276/442ecb89-b9b8-9a33-3e5a-04746e39ae4f.png)

暫定 96,845,023,619点、23位。手元で1,000ケース動かすとギリギリ97G（×10<sup>9</sup>）点なので、システムテストで順位が上がることを期待。

TODO: システムテストが終わったら、スコアと順位を書く。

## 問題概要

インタラクティブ問題。これまでのAtCoder Heuristic Contest（AHC）では計算量的に最適解が求められなかったが、今回は真の情報が得られないので最適解が求められない。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/25276/0ee8a147-0957-5d93-2f77-1982db628a3e.png)

こんな感じのグリッド状の道が与えられ……ない。テスターが内部的に持っているだけ。テスターから始点と終点を指定され、それに対して経路を返す。テスターは返した経路の（誤差を含んだ）距離を教えてくれるので、それを使って頑張る。返した経路の距離が最短経路の距離に近いほどスコアが増える。

スコアの計算がまずややこしい。全1,000回で各回ごとにこんな感じの係数を掛けて合計する。最初のほうは重みが低い。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/25276/82884f8d-4a02-82c0-8af1-1f12ed27a38b.png)

最終的なスコアを求めるときに、2,312,311を掛けているのは、全て最短経路を返して満点だったときのスコアをほぼ1 Gにするため。

道路の距離の生成もまたややこしい。

ビジュアライザでは赤いほど距離が長く、青いほど短い。上の図を見れば分かるように、y座標が同じ横向きの道路同士、もしくはx座標が同じ縦向きの道路同士は、だいたい同じ距離になる。ただし、1/2の確率で`M=2`となり、この場合は途中のどこかでこの距離が切り替わる（y=4の横の道路が分かりやすいだろうか）。で、ここに各道路ごとに独立な乱数がちょっと加えられる。この乱数の値の範囲も問題ごとにランダム。

## 解法

ソースコード。

https://github.com/kusano/ahc003

[コミット履歴](https://github.com/kusano/ahc003/commits/master)に沿って書いていく。


### 雛形を作る

[https://github.com/kusano/ahc003/commit/97ac6c70b6eb9e469a76e2f380b5ae4eb154cde7](https://github.com/kusano/ahc003/commit/97ac6c70b6eb9e469a76e2f380b5ae4eb154cde7)

いちいちテスターを使うのは面倒なので、単体で動かせるようにする。

問題に書かれているサンプルだと、

```cpp
string query(s, t, prev_result) {
    // WRITE YOUR SOLUTION HERE
}
```

このように今回のクエリと前回の入力を受け取っているけど、これだと書きづらい。クラスを作り`Tester::answer`で経路を返して距離を受け取れるようにした。クラスの中身を切り替えることで、そのまま提出もできるようにした。なお、AtCoderの環境では`ONLINE_JUDGE`が定義されているので、これで切り替えるようにすると、手元でのコンパイル時に何かをする必要が無くなる。

まずは、全ての道路の距離を1とみなして、ダイクストラ。全ての道路の長さが全て1で、グリッド状なのだから、単に始点と終点を見て`LLLLUUU`とか出力すれば良いが、まあ結局ダイクストラは使うことになるだろうから実装。

63.1 G点。

### hとvをまとめて扱う

[https://github.com/kusano/ahc003/commit/e1365d0c1a29b89647bde9c3ec9ce9c17f7e3d5f](https://github.com/kusano/ahc003/commit/e1365d0c1a29b89647bde9c3ec9ce9c17f7e3d5f)

横向きの道路は2次元配列`h`、縦向きの道路は2次元配列`v`で与えられる。横向きと縦向きで同じ処理を2回書くのが面倒。

```
+ h + h + ...
v   v   v
+ h + h + ...
:   :   :
```

59x59の配列を使ってこんな感じに`h`と`v`の値を入れておけば、縦と横をまとめて扱える。デメリットはメモリ消費量の増加と、それにともないキャッシュに入りきらなくて速度が落ちること。メモリは余裕だし、速度も今のところ時間いっぱい使って何かをする予定は無い。

### hとvを推測する

[https://github.com/kusano/ahc003/commit/9ccec4d8503827fa701b8751574ec3a025d349a1](https://github.com/kusano/ahc003/commit/9ccec4d8503827fa701b8751574ec3a025d349a1)

ここからが本番。テスターから返ってきた距離を使って、`h`と`v`の値を推測する。

こちらが距離`d1`だと思っていて、テスターから距離`d2`が返ってきたら、経路上の各道路の距離は合計`diff=d2-d1`だけ実際より小さいことになる。とりあえず、これを通った道路の個数で割って`h`と`v`に足せば良いだろう。足し引きで合わせるのではなく、乗除で合わせるという手もあったか？

なお、初期値が期待値の5,000ではなく1なのは、未探索の道路の距離を短くすることで、最初のうちにその道路を使うことを期待しているから。

84.6 G点。

### HとVを推測する

[https://github.com/kusano/ahc003/commit/48c5b4d73837f0eeab6d02d297c2d7fae9807c56](https://github.com/kusano/ahc003/commit/48c5b4d73837f0eeab6d02d297c2d7fae9807c56)

$h_{i, j}=H_{i, 0}+\delta_{i, j}$ or $h_{i, j}=H_{i, 1}+\delta_{i, j}$。$v$と$V$の関係も同様。

各道路の長さ`h`と`v`はそれぞれ29x30=870個の要素を持っている。合計1,740個。一方、テスターとのやりとりは1,000回。変数のほうが数が多いのだから、正確な値が求まらない。「y座標が同じ横向きの道路は、だいたい同じ距離になる」の同じ距離が`H`。こっちは合計60個なので、こっちを推測しよう。

推測の方法は`h`や`v`と同じ。$h_{i, j}$の代わりに$H_{i, 0}$に足す。ただし、全部で29個あるので、29で割る。

`M=2`の場合は……とりあえず考えないでおくか。全体の平均値を推測することになるけど、そんなに悪くはないだろ。

なんか手元で実行したスコアがおかしいなと思ったら、浮動小数点の誤差でスコアが大きくズレていた。「ジャッジ用プログラムの例」そのままだとダメなの……。

```diff
-        score = score*0.998+a[k]/b;
+        score += pow(0.998, 1000-(k+1))*a[k]/b;
```

91.9 G点。

### 実数を使う

[https://github.com/kusano/ahc003/commit/869e972e910859c731a0bfe1fdb440abe719ebd3](https://github.com/kusano/ahc003/commit/869e972e910859c731a0bfe1fdb440abe719ebd3)

前の項目のソースコードで唐突に出てきた`*1024`は29で割ったりしていたら精度が足りなくなったから。計算速度勝負にならないのだったら、そんなことをしないで実数を使えば良いよね。

92.1 G点。

ちょっとだけスコアが増えた。

### HとVを分ける

[https://github.com/kusano/ahc003/commit/de3737a06ed00a0302cf18530d3ca0cfe8b94436](https://github.com/kusano/ahc003/commit/de3737a06ed00a0302cf18530d3ca0cfe8b94436)

先に無視していた`M=2`の場合の話。これを無視したままで良いのだったら、作問者も問題文を複雑にしてまで`M=2`を作らないはずである。しかし、これどう取り扱えば良いのだろうな。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/25276/508e5c80-f3b8-075c-e5b2-fe681a3cf3b3.png)

両端の値を持って線形和（赤線）で良いか。平均値は青線。黒線との差分が誤差なので、小さくはなるだろ。

今度は`M=1`を無視していることになる。まあ、その場合は両端が同じ値になってくれるだろう。たぶん。これで良いなら、作問者は`M=1`の場合なんて作らないわけで、考えたほうが良くはあるのだろうけど。

分割したことによって、実際の距離との差分を足す部分がややこしくなった。

`H`を分割した`HL`と`HR`から、位置`x`の道路の距離は

$d_1=\frac{HL((2*W-3)-x)+HR(x-1)}{2*W-4}$

として求めている。実際の距離`d2`との差分が`d=d2-d1`だったとき、

$t=d \frac{2*W-4}{((2*W-3)-x)^2+(x-1)^2}$

として、`HL`には`((2*W-3)-x)*t`、`HR`には`(x-1)*t`を足すと、$d_1$に寄与が大きいほうが大きくなり、合計も何か良い感じになる。計算したらこうなったけど、2乗とか出てくるのか。

これ、値を2個持つなら、x=0とかもうちょっと離れた位置の値を持っておいたほうが式が簡単になったかもしれない。

93.0 G点。

### 推測時に過去の情報を使う

[https://github.com/kusano/ahc003/commit/dd8df481b67d66e479b97aff2f57794fe0859a8b](https://github.com/kusano/ahc003/commit/dd8df481b67d66e479b97aff2f57794fe0859a8b)

これまでは、結果が返ってきたときに、`H`と`V`の値を補正していた。たとえば、500回目の時点だとだいぶ値が分かってきているので、ここで1回目をの結果を再度使うとより正確に推測ができる……はず？

各回ごとに1回目からその回目までの結果で推測するようにしたらスコアがだいぶ上がった。これを何回か繰り返せばさらにスコアが上がるかと思ったけど、上がらず。良く分からない。どうしてそのようになるのかの仕組みを調べたら、さらに工夫する余地があったかもしれない。

95.8 G点。

### δの値も推測する

[https://github.com/kusano/ahc003/commit/6772be65c50d782f3139c08de7efce0e9ed38f1f](https://github.com/kusano/ahc003/commit/6772be65c50d782f3139c08de7efce0e9ed38f1f)

`δ`は各道路の距離に加えられる乱数。

`H`と`V`を推測するようになって、`δ`を推測するのを止めていたけど、ビジュアライザを見ているとたまたま1箇所だけ距離が長いところに突っ込んでいたりする。やっぱり推測しよう。

問題は、δの値の範囲`D`がテストケースごとに変わることである。期待値はD=1,000くらい。`H`と`V`は1000+Dから9000-D。3/4が`H`と`V`由来、1/4が`δ`由来と思えば良いだろう。`diff`をこの割合で分けて足す。

96.6 G点。

### ハイパーパラメタ探索

[https://github.com/kusano/ahc003/commit/e06866bd67fea8b6ea738188c88efeb0fab81d5e](https://github.com/kusano/ahc003/commit/e06866bd67fea8b6ea738188c88efeb0fab81d5e)

`H`と`V`、`δ`の初期値はどうしよう。今まではとりあえず下限にしていたけど、期待値に近づければ最初のほうの正確性が上がる。ただし、最初のうちになるべく探索するということをしなくなる。あと、1/4を`δ`に回しているけれど、これが正しいのかという話もある。極論、全てを`δ`に回しても（クエリの回数が充分に多ければ）正しい距離になるはずである。

ということで、出でよ！Optuna。Optunaの話は001の記事を参照。

https://qiita.com/kusano_k/items/82fb97b7218fd5871e1c#%E3%83%91%E3%83%A9%E3%83%A1%E3%82%BF%E8%AA%BF%E6%95%B4

誤差が大きくてなかなか難しいのだけど、あるパラメタの寄与が大きければ、そのパラメタは固定してしまって、他を探索するとかで何とか。

`delta_param`（↑の1/4）と`H`や`V`の初期値はだいぶ効いていた。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/25276/67c64b24-e611-e51d-fe88-dc7c69b37417.png)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/25276/b7af21a4-d143-f12b-7a8b-19e3eb108164.png)

えいやで決めたところがあるから、これが本当に正解というわけではないが、`δ`の初期値に大きな値が出てきたのが面白い。`H`や`V`と`δ`を足して期待値の5,000くらいになり良い感じ。`δ`が大きくても、`H`と`V`が小さいから、最初のうちに探索する動きに支障は無いということだろうか？

96.8 G点。

### 学習率（？）をHやVとδで別にする

[https://github.com/kusano/ahc003/commit/15bd4c0c9f8d405893060e6f94dd3e3143da4f17](https://github.com/kusano/ahc003/commit/15bd4c0c9f8d405893060e6f94dd3e3143da4f17)

テスターから返ってきた距離との差分`diff`を、`δ`には`diff*PARAM_DELTA_RATE`、`H`と`V`には`diff*(1-PARAM_DELTA_RATE)`振り分けていた。再計算が終わった時点で、もう1回経路の距離を推測すると、テスターからの返り値と同じになっているはず。そういえば、初期値を小さくすることによって、まだ見ていない道路をなるべく使うようにしていたのだった。これ、テスターからの返り値よりもちょっと小さな値になるようにしたら、見た回数が少ない道路は再度見てくれるかな？　ということで、`1-PARAM_DELTA_RATE`ではなく、別のパラメタを用意して探索。Optunaが適切な値を探してくれるはず。結果、`PARAM_HV_LEARN_RATE+PARAM_DELTA_LEARN_RATE=0.5`くらい。

96.78 G点。

### テストケースを1,000個に増やしてパラメタ調整

[https://github.com/kusano/ahc003/commit/1ab97e8fcd549b6c7fdbaa2154108b24c184fd36](https://github.com/kusano/ahc003/commit/1ab97e8fcd549b6c7fdbaa2154108b24c184fd36)

手元でも100ケースでスコアを評価していた。サブミットしたときのスコアが手元でのスコアよりも小さい。オーバーフィットしているっぽい。ということで、1,000ケースに増やして再度調整。

96.76 G点。

サブミットした結果ではスコアが減っているけど、手元の1,000ケースでは増えているので、システムテストのスコアは上がるんじゃないかなぁ。

0.1 G点の勝負になってくると、もはや100ケースの暫定スコアも当てにならない。

統計検定の勉強を思い出しながら考えてみると……。

手元で100ケース実行した結果の標準偏差は0.01 G点くらい。これは、≒母集団（0～∞の全てのシードについて実行した場合）の標準偏差と考えて良いはず。標準偏差が0.01 G点ということは、平均値の±0.1 Gに入るサンプルは68%くらい。標準偏差の2乗が分散で、100個の要素を持ってきたときの合計の分散は1個の場合の100倍になるから、n=100ケースで求めている暫定スコアの標準偏差は、1個の場合の√n=10倍で、0.1 G点、かな。真の値の±0.1 G点以内になる確率は68%。これを0.01 G点にしようと思うと、10,000ケース必要。1,000ケースではたいして精度が上がらないし、オーバーフィッティングが嫌なだけなら、固定の100ケースではなくランダムに生成した100ケースにすれば良かったのかもしれない。

### やり残したこと

`δ`の値などの推測がある程度進んだところで、`M`と`D`の値を推測したかった。あとは、`M=2`のときの切り替わる場所。ある道路を通ったかどうか（何回通ったか）の情報を、距離に暗黙的に載せているのは良くない気がする。普通に回数を記録しておいて、経路を決めるときにそれを使って何とかできれば……。この辺、普段から機械学習をやっている人が強そうなので、他人のブログ記事を読んで勉強するか。