AHC003 参加記
システス後 2.911T点（17 / 1000位）
なにこれ
AHCというプログラミングコンテスト！の３つめ
大まかに書くけど、詳しくは本文をよんでね
- 辺の長さが不明のグリッドグラフ上で、与えられた2点間を結ぶ
- 結んだ長さが大体いくらだったかだけ教えてもらえる
- それを1000回やって、結んだ長さの合計が短いほど高得点
他の人の解法はここにいっぱいあるよ
#AHC003 hashtag on Twitter
かんがえた解き方
例！今4つのパスについて長さを取得したとするよ
一旦これらを正確なものと仮定すると、辺の長さは例えばこう↓なる
この1枚目の画像から、2枚目の画像をなんとなく求める計算がしたい！
でもどうしたらできるの…
悩んだ挙句ひねりだした案↓
- パスの主張を聞いて、辺の長さを推定
- 推定された辺の長さを見て、パスの主張の補正（再配分）
主張って？とりあえずパスの長さを等分してみよう
このピンク文字が、パスが主張する辺の長さです
これを合算して辺の長さを推定しよう
このとき、主張の重みは 1 / パスの辺の数 とします
青字が、パスの主張から推定された辺の長さです
今度は、ここから逆にパスの主張を補正しよう
たとえば6333の下にある辺数4のパス、
今の辺長を足すと6333*2 + 5000*2 = 22666 で、これはパスの長さ20000 を超えてるね
この超過分 2666 を等分しそれぞれの辺への主張から引きます
するとこんなかんじ
ここまでを1巡として、何回もやるよ
ためしに10回やってみた結果↓
うーん…これは…どうなの…？（微妙な結果）
僕の解法はクエリごとにこの計算を1巡します
500クエリ目なら500個のパスを再配分するので重い
解き方ほか
- 辺同士の相互作用
とりあえずM=1用とM=2用で2つモデルをつくって、辺に対し以下の処理をする
M=1: 同じ線上にある29個の辺の平均値に、すこし値を近づける
M=2: 隣の辺の値に、すこし値を近づける
M=2のほうもっと良い案だしたかった
- モデルの切り替え
Mの判別は僕にはできなかったので…
クエリごとに、両モデルに「今の経路長いくつだったと思う？」クイズで正解にどれだけ近かったかという点数をあげる
経路を決めるときは、その時点で点数が高い方のモデルに決めてもらった
ほかにやったこと
- ローカルテスト環境
Rust分からなかったけど、公式が「1ケース生成」と「1ケース実行」を公開してたので、 合体くらいなら出来るかもということで「n個のケースを実行して平均点を求める」にしました。
100ケース実行するのに2 * 100 秒くらいかかるけど、無いよりずっと良かったと思う
並列化はやり方がわからなかった…
- その他
他にも色々あったけど長くなっちゃったから今回は割愛
感想
がんばってブログかいたのにただの絵日記になっちゃって泣いてる
