結果

117位

最終的にやったこと

ジャッジから与えられるパスの長さの情報をもとに辺の長さをどうにか推測して最短経路問題の復元をおこないました。

まず、通った回数が一番多い辺を一つ選びます。

次に、選んだ辺が含まれているパスの $b_k e_k$ を使って辺の長さを推測します。

このとき、 $\displaystyle\frac{b_k e_k}{パスが含む辺の個数}$ の平均を推測した値として使いました。

最後に、パスの $b_k e_k$ と、パスが含んでいる辺の個数を、選んだ辺の分だけ引きます。

上の操作を全ての辺に行うまで繰り返します。

縦と横の辺に対してガウシアンフィルタをかけるようなことをしました。

M=1の場合に対しては、行（または列）の辺の長さを平均したものを、行（または列）の辺全てに上書きしました。

M=2の場合に対しては、よく分からなかったのでお気持ちをしました。

具体的には、行（または列）の辺を、ある辺を中心とした座標を変数にとる正規分布に従う重みで平均して、正規分布の中心の辺の長さを重みつき平均の値で上書きしました。

全ての辺が中心になる場合を計算して、全ての辺の長さを上書きしました。

本当はM=1とM=2を区別して処理を切り替えたかったんですけど、うまく区別することができませんでした。

なので、スコアが最大になるような比率を調べてM=1用の処理とM=2用の処理をどっちも使いました。

推測した辺の長さを使ってダイクストラ法で最短経路問題＋復元を解きました。

初めて見るタイプの問題で本当に楽しかったです。

他の人の解法を見て、いろいろ勉強したくなりました。