oldlickの日記

競技プログラミングと電子工作をします

AHC003参加記

AHC003に参加しました。暫定94.6G点(119位)です。
なかなか現実世界がおろそかになりましたが、後悔はしていません、、 f:id:oldlick:20210531015112p:plain

  • 追記
    システムテスト後 125位でした。 プログラムを変えたので (詳細は後述) 順位が下がるのは覚悟の上でした。思ったよりも下がらなくてよかったです。
    パフォーマンスは2050、新レートは1050とのことです。*1 f:id:oldlick:20210601153351p:plain

  • 追記2
    システムテストのリジャッジ後 126位でした。

atcoder.jp

問題概要

  • 下記を1000回やってね
    • 与えられた二点の最短経路予想してね。けど各辺の重み教えないよ。
    • 予想した経路の実際の長さを教えるよ。

考察

  • 予想していた距離と大きく違った時、どの辺が原因で誤った値になっているのか分かると良さそう。
  • 何度も通った辺は、信頼度が高そう。
  • M=1 の時でも、M=2 として考えて良さそう。*2
  • D がマップ全体で統一なので推定できると強そう。

基本方針

  • 辺の推定値を元にダイクストラを用いて最短経路を計算。
  • 各辺は実測値,信頼度,推定値の三つの値を保持しておく。
    • 実測値は各クエリの返答を元に計算した辺の重み。
    • 信頼度は実測値の信頼性。
    • 推定値はマップ全体を総合的に見た時に推定される辺の重み。

実測値と推定値が別になっているところと、信頼度を持っているところがオリジナリティーかも。

詳細

1.実測値の更新

  • 実測値はクエリの返答から計算される。
  • 実測値の更新の際、各辺の更新度合いは信頼度の逆数の比で決める。

クエリの返答はパス上の辺の重みの総和だから*3、それぞれの辺の重みに分解する必要があります。話を簡単にするために、予想していた返答と実際の返答の差を \mathrm{diff} とします。その差 \mathrm{diff} をそれぞれの辺に分配するというイメージ。その時、信頼度が高い辺はあまり更新する必要はなく、信頼度が低い辺は沢山更新するべきとなります。この性質から、 \mathrm{diff}信頼度の逆数の比で分割して、各辺の更新度合いを決定しました。
この実測値の更新の方法を採用したことで、かなりスコアが伸びました。

例) \mathrm{diff} が840の時

path上の辺 辺0 辺1 辺2 辺3 辺4
実測値 5000 5000 5000 5000 5000
信頼度 0.1 0.1 0.1 0.1 0.5
信頼度の逆数 10 10 10 10 2
5 5 5 5 1
更新度合い 200 200 200 200 40
更新後の実測値 5200 5200 5200 5200 5040

2.信頼度の更新

  • 信頼度は下がらないものとする。
  • クエリのパスに、ある辺と同一直線にある辺が多いなら、その辺の信頼度を大きく上昇させる。(図参照)

この信頼度の更新方法の選定が最も大変だったことの一つでした。信頼度は実測値の更新をするうえで非常に重要なデータとなるので、この数値の更新を誤ると一気にスコアが下がることが多々ありました。
「クエリのパス上にある辺はすべて一律で一定数上げる」、「クエリのパス全体の長さが短いとき、一律で多めに信頼度を上げる」、「実測値の更新の際にあまり変化しなかった辺の信頼度を大きく上げる」等の方法を試しましたが、どれも微妙な結果となりました。 結果的に良かった方法は、下図のように「クエリのパスに直線状に並んでいるほど、信頼度を上げる」という方法でした。 f:id:oldlick:20210601151707p:plain この例では、赤のパスなら、20%の部分の辺はあまり信頼度を上げず、80%の部分の辺は大きく信頼度を上げます。また青のパスなら、全体的に信頼度を上げる。といった具合です。

3.推定値の計算

  • Dと、M=2の際の x_{i}  H_{i,0}  H_{i,1} を推定し、その値から各辺の実際の重みを推定する。
  • x_{i} は辺の重みのクラス内分散が最小となるものとした。
  •  H_{i,0} は実測値の平均とした。( j\in\{0,\cdots,x_{i−1}-1\} )
  • D は推定した  H_{i,0} と実測値の差の平均とした。( i\in\{x_{i-1},\cdots,29\} )

先の方法で実測値を更新し計算しましたが、その値はミクロな各辺のみの情報でしかないので、全体の状態を考慮した値 (推定値) を計算したくなりました。 x_{i} はいわゆる崖ができている部分なので、クラス内分散が最小となる x_{i} を計算すれば良いだろうと考えました。*4。(中盤までクラス内分散の計算が間違っていました… *5 )


(クラス内分散) := (x_i*σ_1^2+(30-x_i)*σ_2^2)/30\\
σ_1^2=\frac{1}{x_i} \sum_{j=0}^{x_i-1} ( (実測値)_{i,j} - (平均値) )^2\\
σ_2^2=\frac1{30-x_i} \sum_{j=x_i}^{29} ( (実測値)_{i,j} - (平均値) )^2

x_{i} H_{i,0} , D を計算した後、下記の方法で推定値を計算しました。


(推定値) := H_{i,0} + f( (実測値) - H_{i,0} ) * D * (定数)

ただし f(x) := sigmoid(x)*2-1

4.重複したパスの活用

以前見たパスが今回指定したパスの誘導部分グラフになっている時があります。ここで、以前見たパスの情報を活用すればより精度の高い推定が行えるのでは、?と考えました。 f:id:oldlick:20210601142304p:plain 図のように補グラフの部分に注目すると、以前と今回のコストの差を計算すれば青線の部分のコストも分かります。赤全体でだけ実測値を計算するのではなく、青線の部分でも同様に実測値の更新を行いました。
結論としては…これを行うとスコアが下がりました。 冷静に考えると当たり前です。 赤線と緑線共に絶対誤差 err1,err2 を含んでいるので、青線の絶対誤差は |err1|+|err2| となり、誤差が大きくなっています。
これを改善するために、各パスの絶対誤差を計算しておき、その絶対誤差が大きいほど、実測値と信頼度の更新を緩く行うように変更しました。すると微小ではありましたが、スコアが伸びました。
ここで、クエリの返答は真値に対して e 倍になっているので、クエリの返答を \frac1{e} 倍したものが真値になります。eは0.9から1.1なので、\frac1{e} つまり 約0.909~1.111倍の範囲に真値があります。そのため、絶対誤差 err は最大でクエリの返答の約11.11%であることに注意します。

最終提出

最終提出は、過去最高得点のプログラムにはしませんでした。 過去最高得点を取ったプログラムは、クラス内分散の計算が間違っていて、さらにパラメータ調節もしていなかったからです。 今でもなぜそっちの方が得点が高かったのかは謎のままですが、それをそのまま提出するのは嫌だったので、そちらは出さずに、正しいプログラムの方を提出しました。

終わりに

初のAHC参加で、思ったことは一通り試せたので個人的に大満足でした。 次回参加するときはビジュアライザーにも手を出してみたいです。

*1:これ緑レートって言ってもいいの、?

*2: H_{i,0} H_{i,1}が一致していると捉えれば良いため

*3:ここでは相対誤差eは考えないことする

*4:モノクロ画像の二値化などで良く用いられる手法

*5:序盤で作るプログラムは確実に書きましょう…(自戒)