AHC022 Exploring Another Space

[tipstar0125]

https://atcoder.jp/contests/ahc022/tasks/ahc022_a

• ワームホールと出口の対応を求める
• グリッドに温度を設定し、出口から(dy, dx)の位置の温度測定をすることができる
• グリッド間の温度差の2乗で配置コストがかかる
• 温度測定結果は、標準偏差S=1～900の誤差を持つ
• 測定は同じ測定を複数行ってもよい
• 測定回数に制限(10,000)があり、1回あたり最小で1,000コストかかり、dy+dx分の追加コストがかかる

[tipstar0125]

AHCでやっておいた方がよいこと

• 変数がたくさんある場合、マルチテストケースで、各パラメータのスコアをcsv出力やグラフ化して、どのように改善しているか可視化する
• こういうログを取りたかった。https://siman-man.github.io/ahc_statistics/022/
• 並列実行環境

延長戦やってみたいことリスト

• 複数の解法をアンサンブルするときにif分岐するのではなく、ダミーの答えで競わせて採用する

上位勢で出てきたしらない単語

• 最尤度推定
• ベイズ推定
• ポアソン方程式
• 誤り訂正符号
• ハミング符号

[tipstar0125]

えおむ氏の解法ツイート

かなり考察が似ている。細かい工夫がスコアにかなりの影響を与えていそう。

https://twitter.com/e_o_m_2_3_5_7/status/1693203587638452403 https://twitter.com/e_o_m_2_3_5_7/status/1693521485904973835

とろちゃ氏の解法ブログ（にぶたん）

https://trooooche.hatenablog.com/draft/entry/i2YimjscF6mEx-jwcUvjKgnpYW4

ぽか氏の解法ツイート（最小費用流）

https://twitter.com/poka_cp/status/1693213099598463290

[tipstar0125]

AHC解説放送 https://www.youtube.com/watch?v=lOPnnHCFc30

• 1点高温解法
  • 一度答えとして使われたら計測しない
  • 明らかに高温な場合はその時点で計測を終了する（固定回数測定しない）
  • 高温に近い順に計測
  • 各出口からの距離の和が最小になる位置に高温を置く
  • 計測時、(dy, dx)を固定で、ワームホールを変化させて、小さい(dy, dx)が多く計測されるようにする

[tipstar0125]

ベイズ推定

• bowwowさん記事：https://bowwowforeach.hatenablog.com/
• toastUzさん、誤差関数erfのRustコード：https://atcoder.jp/contests/ahc022/submissions/44799111

[tipstar0125]

誤差関数erf

erf: toastUzさんのコード erf2: 以下のWilliams=山内の近似式 http://invar6.blog.fc2.com/blog-entry-16.html

cdf: 累積分布関数のこと

fn erf(x: f64) -> f64 {
    const A1: f64 = 0.254829592;
    const A2: f64 = -0.284496736;
    const A3: f64 = 1.421413741;
    const A4: f64 = -1.453152027;
    const A5: f64 = 1.061405429;
    const P: f64 = 0.3275911;

    let t = 1.0 / (1.0 + P * x);
    1.0 - (((((A5 * t + A4) * t) + A3) * t + A2) * t + A1) * t * (-x * x).exp()
}

fn erf2(x: f64) -> f64 {
    let re = -1.2732395447351626861510701069801e+0;
    let x = x.abs();
    let sx = x * x;
    (1.0 - (re * sx).exp()
        * (1.0 + sx * sx * (0.1101999999998335 / (sx + 7.2085122317063002) + 0.0219999999999997)))
        .sqrt()
}

fn cdf(x: f64, S: f64) -> f64 {
    (1.0 + erf2(x / 2.0f64.sqrt() / S)) / 2.0
}