AHC 030

 

AHC 030 参加記

 

AHC 030 おつでした。

プレテスト 7,885 M で暫定 55 位です。

(追記)システスは 528 B で 51 位でした。

 

最終提出

 

提出コード

 

  • M が小さい場合は可能なすべての状態(各油田の左上の座標の組)を持って、期待獲得情報量がなるべく大きくなるクエリを投げるのを繰り返す(☆)
  • M が大きくなるにつれて
    • 行・列ごとに☆を行い、状態数がある程度減ったらマージして再度☆を行う
    •  \bmod 5 と行 \bmod 4 から行を復元する
    • 3 列などだけを見て 23 個の油田の位置を確定してから上のことを行う
    • それも無理そうなら 4 セルごとに組にして、それぞれをベイズ推定する
    • それも無理そうなら 1 セルごとに聞く

 

 

情報量の計算

一般論

事前分布 P(X) に従う統計量 X を観測することで事後分布 Q(X) を得た場合に得られる情報量は

-\displaystyle\sum_{x}Q(x)\log \frac{P(x)}{Q(x)}

あるいは連続の場合は確率密度関数 p(x) および q(x) を用いて

-\displaystyle\int_{x}q(x)\log \frac{p(x)}{q(x)}dx

と表せる *1

 

情報量最大化への帰着

問題の言い換え

問題は「油田埋蔵量が正のマスをすべて特定すること」だが、これを「すべての油田の位置を特定すること」と言い換えたい。

実はこれは M が小さければほぼ正しい。つまり油田の配置は油田埋蔵量が正のマスとほぼ一対一に対応する。 M が大きい場合は単射にならないことが多いが、 M が大きい場合は大変なので(後述するつもり)、この言い換えをする。

 

情報量のオーダー

油田の配置は、初期情報だけからだと \displaystyle\prod_{i=1}^{M}(N-h_i+1)(N-w_i+1) 通りある。これを一意に特定するにはこの対数に相当する情報量 \displaystyle\sum_{i=1}^{M}\log(N-h_i+1)(N-w_i+1) を得る必要がある *2

状態数は N^{2M} で抑えられるので、 01 かを全部持つ状態数 2^{N^2} よりかなり小さくなっている。

コスト当たり約 x の情報量が得られるとすると、  \displaystyle\frac{2M\log N}{x} で正解に辿り着くことができるという計算になる。

 

貪欲法

いろいろ不確実性が高いので、「各ターン、(得られる情報量の期待値)÷(コスト)を最大にするムーブを繰り返す」という貪欲法でも十分強そうということが分かる。

 

 

 

 

 

 

正規分布で近似

(この項は結局使わないので読み飛ばしても OK)

仮定

  • X の事前分布が正規分布 X \sim \mathcal{N}(\mu, \sigma^2)
  • 観測により、実際の値に誤差  e \sim \mathcal{N}(0, \sigma_{e}^{2}) を加えた値が得られる

観測値の分布

このとき観測値 Y の分布は Y \sim \mathcal{N}(\mu, \sigma^2 + \sigma_{e}^{2})

事後分布

また観測値が Y=y であれば事後分布は正規分布 \mathcal{N}(\mu_{\mathrm{post}}, {\sigma_{\mathrm{post}}}^2) に従う

ここで

\mu_{\mathrm{post}}=\displaystyle\frac{\frac{\mu}{\sigma^2}+\frac{y}{{\sigma_{e}}^{2}}}{\frac{1}{\sigma^2}+\frac{1}{{\sigma_{e}}^{2}}}

{\sigma_{\mathrm{post}}^2}=\displaystyle\frac{1}{\frac{1}{\sigma^2}+\frac{1}{{\sigma_{e}}^{2}}}

得られる情報量

これを上の一般の場合の式に代入して、簡単のために t=\displaystyle\frac{{\sigma_e}^2}{\sigma^2} とすると、得られる情報量は

-\displaystyle\frac{1}{2}\log (1+\frac{1}{t})+\frac{1}{2t}+\frac{y^2}{2t(1+t)\sigma ^2}

 

得られる情報量の期待値

これを y について期待値を取ると得られる情報量の期待値が次だと分かる。

-\displaystyle\frac{1}{2}\log (1+\frac{1}{t})+\frac{1}{t}

 

何マス選べば良いか

kマス選んだときの平均・分散

適当に近似すると k マスを無作為に選んで占ったときに得られる情報量の期待値が分かるのでそれを最大化すれば・・・

あたりまで考えたときに、少し実験してみると \epsilon が小さいと情報量が増えすぎちゃうことに気付いた(例えば 01 しかとらない場合、情報量は最大でも 1 だけど正規分布で近似すると 5 とかが得られてしまうなど)。

 

離散

なので事前分布も誤差関数も離散でやった方が良さそう。

 

誤差と遷移確率

k, \epsilon を固定して考える。

あるサイズ k のマスの集合について、油田数の合計の分布は、それまでに聞いたクエリから理論上厳密に計算できる。

よってこの場合もその集合についてクエリを投げたときに得られる情報量の期待値が(計算量を気にしなければ)厳密に求まる。

可能なすべてのクエリに対してコスト当たり期待獲得情報量を計算するのが良いが、時間的に難しいのでいくつか候補を選んでコスト当たり期待獲得情報量が最大のものを選ぶこととしたい。

 

計算方法(離散の場合)

事前分布が P(x) および事後分布が Q(x) が分かると、得られる情報量は上述のとおり次のように表される。

-\displaystyle\sum_{x}Q(x)\log \frac{P(x)}{Q(x)}

 

あるマスの集合について質問するという観測について、観測を行う前の段階でどれぐらいの情報量を得られるか計算するには、次のように考える必要がある。

 

  1. 各観測結果について、その観測結果が得られた場合の情報量を計算する
  2. それらを事前分布の重みで加重平均する

 

1. については、観測結果から事後分布を計算する必要があるが、これはベイズで計算できる。ちゃんとやるとでかいテーブルが必要になって結構大変だが、 \epsilon はケースごとに固定なので、 k (クエリに投げるセルの個数)ごとにテーブルを前計算しておけばなんとかなる。 Python だとそれでも結構つらいので、なるべく同じ k でクエリを投げるようにした。

 

実装方法

方針

  • すべての状態について、クエリ結果をもとに確率分布を管理する。
  • トップの状態が 2 番目にある程度差を付けたら Answer クエリを投げる

データの持ち方

  • \displaystyle\prod_{i=1}^{M}(N-h_i+1)(N-w_i+1) 通りの状態をすべて管理する。
    • 初期状態では事前分布は互いに等確率なので、すべて同じ重みとする
  • クエリを行うごとに、結果に対して整合的になる確率を掛ける
    • 実装上は対数確率を加算する
    • 管理する量が膨大になるのを防ぐため、十分小さい確率になったら管理対象から外す

どのクエリを選ぶか

  • なるべく結果の分散が大きくなるようなクエリを聞くのが良い
  • マス同士の共分散が高い(≒近くにある)マス同士を一緒に選ぶのが効率的であることが多い
  • ただし一度クエリを投げると、次回からはそのクエリの結果は既知となるので、同じ(あるいは似ている)クエリをたくさん投げても得られる情報量の期待値は少なくなりがち

 

 

計算量削減の工夫

 

 

独立空間への分解

 

O(N^{2M}) 個の状態を管理・更新するのは、 Python では M=2 かせいぜい M=3 ぐらいしか対応できない *3

 

行だけ見て、すべての油田の行の位置を決定する

→列だけ見て、すべての油田の列の位置を決定する

 

みたいな方針だと管理する状態数を O(N^{M}) まで減らせるので M=4 ぐらいまで対応できる。

「行だけ見る」というのは、 (i, j)i に移す関数 f((i, j)=iにより「圧縮」操作をしたと考えることができる。

これでうまくいくのは、「行だけ見る」が加群の商群になっていることが効いている。

 

より一般化すると加群 f:\mathbb Z ^{2} の部分加群 X を固定すると、その商群で考えることができる。

 

一部のマスだけで判定する

例えば左 3 列だけを見て、ここにかぶっている油田が 3 個以下であると仮定すると、調べるパターンは  {}_{M}C_{3} \times (3N)^{3} になる。さらに行をまとめたり列 \bmod 5 などを考えることで探索パターンを減らし現実的な計算量で順次特定していくことができる。

私の実装では、これを一度行って 23 この油田の位置を固定して、上の独立空間に分解する方法になった。

 

その他やったこと・考えたこと

  • 今回はローカルで実行せず、すべてコードテストでデバッグした
    • 提出コードと同じコードでコードテストデバッグできるようにした 
    • せっかくビジュアライザ練習してたので使えば良かった
    • 途中まで導入してないと心理的に途中から作るのがめんどくなってしまって良くない
    • コードテストで困ったこと
      • クエリ回数が多いと、クエリ部分だけに絞っても全部出力できないのでデバッグできない
  • 序盤は M=2 以外は打ち切るとかでやっていて、後半に徐々に M を増やしていこうと思っていたが増えきらなかった
  • Web 版ビジュアライザの罠:
    • NM の上限・下限が設定されている雰囲気があるが、あり得ないパターンが含まれている
      • N=10 かつ M=20 とかを表示して、特定むずそうだなーとか言ってたけど存在しないケースだった

 

できなかったこと

  • 全部の状態を持たなくても、クエリの結果に矛盾しない配置を焼きなましとかギブスサンプリングとかで得るのでも当てられるか
    • 焼きなましは、全部当てないと使いづらそうだし、自分の実力だとだめそうなので棄却
    • ギブスサンプリングだと、最初例えばランダムに 10000 状態持っておいて、クエリごとに尤度を更新して、ある閾値を下回ったらダメな部分を付け替えるみたいなイメージを考えていた(けどこれも自分の実力だと無理そうなので棄却)
  • 「一部のマスだけで判定」を逐次的に実行することで M が大きい場合も計算量を爆発させずに探索ができるはず
    • 実装しきれなかった。
    • PyPy では 1 回やるだけで 1 秒程度かかってしまうので、高速化しないとむり

 

今後やりたいこと

  • 焼きなまし(無限回言ってる)
  • Rust に乗り換える(無限回言ってる)
    • 今回ちょっとだけ chat GPT くんに翻訳してもらおうとしたけど無理だった

 

関連ツイート

 

 

 

(追記) M ごとのシステス順位

6 以上ほぼ 1000 位付近ですね・・・

(これで全体 51 位取れてるので力の入れどころは合っていたということで・・・)

 

 

M \mathrm{Rank} \mathrm{Score} \mathrm{Case} \mathrm{Average}
2 36 146,610,872,823 369 397,319,438
3 27 144,668,767,503 354 408,668,834
4 22 137,882,178,018 358 385,145,748
5 348 23,766,708,507 398 59,715,348
6 1002 7,026,140,456 288 24,396,321
7 703 7,877,432,650 241 32,686,442
8 998 5,235,875,353 190 27,557,238
9 975 6,288,036,010 156 40,307,923
10 981 4,758,143,130 109 43,652,689
11 672 7,383,989,361 140 52,742,781
12 972 5,054,494,368 84 60,172,552
13 979 4,430,272,358 71 62,398,202
14 968 4,682,556,825 60 78,042,613
15 659 5,073,713,315 51 99,484,574
16 955 4,973,223,557 43 115,656,361
17 970 3,373,058,320 28 120,466,368
18 972 6,253,621,561 36 173,711,710
19 952 1,569,309,822 12 130,775,818
20 979 1,215,604,211 12 101,300,350

 

ソース: 

https://siman-man.github.io/ahc_statistics/030/index_m.html

 

 

 

End

*1:カルバック・ライブラー情報量。これがいわゆる情報量の獲得量と一致するのかは未確認

*2:情報量の対数の底はなんでも良いが、実装の都合で私は e のつもりでやった。

*3:状態ごとにシミュレーションをする必要があるので、計算量オーダーとしてはもっと大きい

AHC で出てくる分布

 

 

AHC でよく出てくる分布について書きます。

(書きかけ。あとで追記する。)

 

確率分布と確率変数

あとで書く。

 

期待値と分散

確率変数 X の期待値を E(X) 、分散を V(X) と書きます *1

 

 

正規分布

こんな やつ。

確率変数 X が平均 \mu 、分散 \sigma ^{2}正規分布に従うとき X \sim N(\mu, \sigma^{2}) *2 と書きます。

 

特徴

あとで書く

 

 

対数正規分布

 

X \sim N(\mu, \sigma^{2}) のとき、 Y=e^X が従う分布を対数正規分布と言い、 Y \sim \Lambda(\mu, \sigma ^{2}) と書きます。

 

特徴

このとき E(Y)=e^{\mu+\frac{\sigma ^{2}}{2}} が成立します。

 

お気持ち

X の平均が \mu なんだから Y=2^{X} の平均は e^{\mu} なんじゃないかと思いがちですが、それよりは分散がある分だけ若干大きくなります。

例えば X-101 の値を等確率で取る確率変数だとすると、 2^{X}\displaystyle\frac{1}{2}12 となり、平均は \displaystyle\frac{7}{6} なので 1 を若干超えますね。

 

 

AHC029 では、プロジェクトの残務量および価値や、方針カードの労働力およびコストが対数正規分布 *3 になっていました。

 

プロジェクトの生成

このように生成されます。

 

何やらややこしい数式が書かれているように見えますが、 round と clamp を無視すれば *4 、大したことはないですね。

このとき、プロジェクトの価値を残務量で割った比率の期待値がどれぐらいになるか気になりませんか?ほぼ同水準に近いように作られているように見えますが、平均は 1 ではありません。

round 関数と clamp 関数を無視すれば、 \displaystyle\frac{v}{h}\displaystyle\frac{2^{\mathrm{gauss}(b,\ 0.5)}}{2^{b}} の部分、つまり上の記法で \Lambda (0, 0.5^{2}) の対数正規分布になっています。底が 2 であることに注意すると、これは \Lambda(0, (0.5 \log 2)^{2}) に従います。よってこの期待値は \displaystyle\frac{(\log 2)^2}{8} \fallingdotseq 1.061896 \cdots であると分かり、価値の期待値は初期残務量より 6.2\% 程度大きくなることが分かります *5

 

方針カードの生成

このように生成されます。

(なお各ターンで 0 枚目に与えられるコストゼロのカードはこの分布に従いませんが、ここでは使わない前提で考えています。)

 

こちらは指数がかかっていない普通の正規分布なので、攻撃力 1 に対するコストの期待値はほぼ 1 です。

 

最初の記載が間違っていたので修正しました(12/27 18:00)

 

プロジェクト完了までに得られる利益の期待値

プロジェクトの初期残務量を基準とすると、価値はそれより約 6.2\% 高く、必要なカードのコストの期待値は残務量と等しいので、すべてのプロジェクトをキャンセルせず無駄なく完了すると期待値としておおよそ 6.2\% の利益が得られることが分かります *6

 

 

 

 

End

*1:アクチュアリー試験でもよく使われる記法。

*2:後者の引数は 2 乗を付けることで標準偏差ではなく分散になっています。

*3:正確には clamp 関数や round 関数で丸められていましたが、本質的には対数正規分布と思って良いです。

*4:いずれも影響があまり大きくないことが分かります

*5:正確には round 関数、 clamp 関数の影響で少しずれます

*6:前述のとおりコストゼロのカードは使わない前提です。また実際には「キャンセル」もかなり重要な戦略になるので、この期待値自体が直接使える訳ではないです。

AHC 029

 

 

AHC 029 参加記

 

AHC 029 でやったことと参加記です。

プレテストは 6.4B で暫定26位です。

 

 

やったこと

最終提出 の説明です。バグなどもありますがそのまま説明しています。細かいところは一部省略しています。

 

概要

評価関数による貪欲です。将来ターンのシミュレーションは行っていません。

 

 

カードを引く場面での選択

 

引くカードの評価をだいたい次の表のとおりとして、「(カードの評価)-(コスト)」が最大のものを選択する。

引くカードの種類 評価
通常労働カード 現在持っているプロジェクトに使ったときの評価の変動量の最大値
全力労働カード 現在持っているプロジェクトに使ったときの評価の変動量の合計
キャンセルカード 現在持っているプロジェクトのうち評価が最低のものの -1
業務転換カード 現在持っているプロジェクトの評価の合計の -1
増資カード 600 \times 2^{L}

 

ただし、プロジェクトの評価はだいたい次のとおりとした。

状態 プロジェクトの評価
未完了 0.83v - 0.85h + 0.1(h-h^{0.995})
完了 v

また増資カードは \displaystyle t \times (1 + \frac{p}{m - p + 1} \cdot \frac{1}{L + 5}) \le 999 のときに限り引くこととした。

ここで、 t はその時点のターン数、 m はその時点での所持金、 p はカードの価格、 L はそれまでの増資回数。

 

カードを使う(実行する)場面での選択

増資カードがあれば必ず使用する

そうでなければ「(お金の変動)+(プロジェクトの評価の変動)-(カード評価)」が最大のものを使用した。

プロジェクトの評価は上と同じものを使用した。カードの評価はだいたい次のとおりとした。

 

カードの種類 評価
通常労働カード 0.7w
全力労働カード 0.6Mw
キャンセルカード 2^{L}
業務転換カード 2^{L}

 

 

最終提出には使わなかったけど試したこと

  • 増資カードの評価を、増資カードの出やすさによって変える(実はやってるつもりだったけどバグっていた)
  • 「カードを引く」→「カードを使用する」の一連の流れをまとめて最適化する
  • 最後の方で実現可能性が低くなったプロジェクトは評価を下げるべきだった(一応何かは入れたけどあまりいい感じにならず・・)
  • プロジェクトごとに評価を作っていたので、特に M が大きいときは余りがちだった
  • Optunaでパラメタ調整をいろいろ試した(けど変動が大きすぎてよく分からなかったので結局手で決めたもの(上に書いたもの)に戻した)

 

できなかった・うまくいかなかったこと

  • N が大きいときも、選んだ直後のカードをそのまま使っていることが多かった(将来使う予定のカードをもう少し効率よくストックできると良かった)
  • 増資カードは 2 枚以上連続で買うと 2 枚目以降のコストが下げられることに気付いたが、うまく使えなかった
  • 高い買い物をしたときに、所持金不足で一定期間(ほぼ)ゼロコストのカードしか取れないみたいな状況に陥ることがあった。うまく指標化して避けるようにしたかったができなかった
  • 適当にシミュレーションすると上がりそうな気がしたけど、それ以前にいろいろバグってできなかった

 

 

参加記

 

序盤

最初の 1~2 日ぐらいはいい感じだったな(遠い昔の思い出)。

 

 

中盤

帰省

 

終盤

いろいろ改造したかったが試してみるとうまくいかず。。

 

 

 

 

End

AHC 027 (HTTF 2024)

AHC 027 (HTTF 2024)参加記

問題は こちら

 

この記事に書いてあること

 

  • 最終提出(プレテスト 189 位)は、汚れやすいマスを TSP で回るのをベースとして、それを倍々に複製しながら、残りのマスを最も良い位置に入れる貪欲
  • マスをグループ分けしたとき、グループ i のマス数を c_i 、汚れやすさの和を x_i とすると、理想的には(頻度を自由に選べるなら)各グループは \displaystyle\sqrt{\frac{x_i}{c_i}} に比例する頻度で訪れるのが最適
  • 二重頂点連結成分分解を用いることで、あるマスの集合とそのうち 2 マス(入口と出口)を与えると、重複なく一度ずつ回って入口から出口まで行けるかどうかの擬似判定がマス数の線形時間でできる(稀に不可能な場合に可能を返すが、ほとんどのケースで大丈夫なはず)
  • グループ分けは汚れやすさが 11 以上のマスからなる連結成分をもとに作成する方法を試した
  • 同じ連結成分内でも比率が 10 を超えるものは別グループにする方法も試した
  • pygame をビジュアライザに使うと便利
  • その他いろいろ考えたけど使えるところまでいけなかった

 

1 日目 - 12 月 1 日(金)

 

考えたこと

  • 汚れがひどいマスを高頻度で掃除するのが最適
  • 最も汚れがひどいエリアを基地として、そこから遠征するイメージか
  • 遠征先は汚れやすさによって数値化して、汚れやすさに比例する頻度で遠征するのが良いか?(理論値の計算は後述)
  • A → B → A → C → A → B → A → D → A → のように、高頻度のものの合間に低頻度のものを挟むイメージ

 

実装してみるがこれムズくない?

この日は提出までいけず。

 

 

おまけ

最初にビジュアライザを見て、カラーモード "d" にしてみたところ、ぱっと見汚れやすさがどれぐらいか分からなかったので、カラーリストを作って、色を見たらすぐに汚れやすさ( d_{ij} )がだいたいわかるように練習した。

 

下から 1~101 刻み)、 11~201 刻み)、 10~10010 刻み)、 110~20010 刻み)、 100~1000100 刻み)。「ある色を見たときにその数値を 1.5 倍までの精度で当てる」(絶対色感)「2 色を見たときにどちらが大きいかを当てる」(相対色感)、ぐらいができれば実用上問題なさそう。

 

 

 

2 日目 - 12 月 2 日(土)

 

1 日目の方針をそれっぽく(雑に)実装

  1. まずは汚れやすいマスたちだけを使って基本のループを作る
  2. 1. の部分は焼きなまし法でやった
  3. 次に全体を 2 倍して、次のレベルのものを最適位置ひとつずつ付ける
  4. 3. での付ける位置は汚れやすさの順に貪欲にした
  5. 3. と 4. をあと 2 回ずつ繰り返す(つまりレベルの段階は全部で 4 つ)

 

この日瞬間最大で 9 位。絶対スコア 839 M 。

 

 

汚れやすさと最適訪問頻度の(簡略化)理論値計算

いろいろ煮詰まったので、基地からいくつかのループがあるときの(簡素化)理論値を計算してみました。簡単のために次の仮定を置きます。

 

  • 基地(例えば最も汚れやすいマスなど)からのループがいくつかあるとする
  • ループは全部で m 個あり、 i 番目( 1 \le i \le m )のループはマスが c_i 個、汚れやすさの合計が x_i であるとする
  • 各ループは互いに重ならず、ループ内でも複数回通るマスはないとする(厳密には基地は複数回通るがそこも無視)とする
  • i 番目のループは k_i 回行うこととし、 k=\displaystyle\sum_{i=1}^{m} k_i とする
  • i 番目のループの k_i 回は理想的に(つまり等間隔で)登場するとする
  • このとき、コストを最小にする k_i を求めたい

 

なお、問題の条件および上の仮定によって、 k_i は(絶対数ではなく)比率のみを決めることと考えられます。

移動回数の和 \mathrm{MOVE}\mathrm{MOVE}=\displaystyle\sum_{i=1}^{m} c_{i} k_{i} 

i 番目のループに含まれるマスは  \displaystyle \frac{\mathrm{MOVE}}{k_i} 回ごとに通るので、このグループからの寄与は一次近似で  \displaystyle \frac{1}{2} \left(\frac{\mathrm{MOVE}}{k_i}\right)^{2} になります。よって、問題文で定義される「平均汚れ」は、

\displaystyle \sum_{i=1}^{m}x_i \cdot \frac{1}{2} \left(\frac{\mathrm{MOVE}}{k_i}\right)^{2} \cdot k_i \cdot \frac{1}{\mathrm{MOVE}} = \frac{1}{2} \sum_{i=1}^{m}\frac{x_i\ \mathrm{MOVE}}{k_i} = \frac{1}{2} \sum_{i=1}^{m}\frac{x_i}{k_i} \sum_{j=1}^{m}c_{j} \ k_{j}

と計算できます。ここで q_i = c_i\cdot k_i とおき、さらに \displaystyle \sum_{i=1}^{m}q_i = 1 を仮定します(先述のとおり、比率だけを考えれば良いのでこれで一般性を失いません)。

すると平均汚れは \displaystyle \sum_{i=1}^{m}\frac{c_i \ x_i}{q_i} となります。ちょっと実験すると、これは q_i\displaystyle\sqrt{c_i\ x_i} に比例するとき、すなわち k_i\displaystyle\sqrt{\frac{x_i}{c_i}} に比例するときに最小値を取ることが分かり、このときの最小値は \displaystyle \frac{1}{2}\left( \sum_{i=1}^{m}\sqrt{c_i \ x_i} \right) ^{2} となります。

当初は汚れやすさに比例する頻度で訪問するのが良いかと思ってましたが、マスの数が同じなら汚れやすさの平方根に比例するという結果になりました。

また式をよく見ると、複数のループに分ける際、平均汚れやすさ \displaystyle\frac{x_i}{c_i} が均等になるように分けても意味はなく、なるべく偏りが大きいように分けると効率が良くなることが分かります。

 

なお、この仮定では各ループが基地を始点・終点としているとしましたが、元のループに対して「寄り道」をすることで追加的に到達できる部分についても同様の結果が得られます。

メインループを 1 つ決めて、そこからの「寄り道」をいくつか作り、上の理論値を参考に頻度を割り振るという方法もありそうです。

 

例えば次のような方法が考えられます。

  • 汚れやすさがなるべく高いものを使ってメインループを作る
  • 全体を網羅するようにメインループから分岐する「寄り道」をいくつか作る
  • その際、なるべく寄り道部分のセルの汚れやすさに偏りが出るようにする
  • 上で計算した理論値をもとに、寄り道のタイミングを決定する

 

3 日目 - 12 月 3 日(日)

ビジュアライザを見るとコース取りがいまいちすぎる。同じマスを複数回ることが多く、同じところを行ったり来たりすることもある。

悪いところは分かるけど何をすればよいのか分からんぐぬぬーー。

 

無駄な往復をする理由を調べるために TSP 部分の挙動も調べられるようにしてみた。ついでに RGB 目利きにも限界があったので、そのへんも見れるようにした。

 

 

TSP で汚れやすいマスを結んでいるところ(Turn を動かすことで焼きなましの様子が分かる)

 



ビジュアライザはこの前の yukicoder score contest 8 で使われてた pygame を使ってやってました。

 

 

キーで進めたり戻したり、表示する内容(道筋・ TSP の焼きなまし状況・後述のグループ分けや部屋割りなど)を変えたり、マスに表示する数を変えたりする機能を付けた。

手元で実装するとそのままグラフ表示できるのでとても便利。

 

4 日目 - 12 月 4 日(月)

うーん、あまり進捗がない。

貪欲に頂点を追加していくという方法だとどうしても無駄な道ができてしまう。頂点集合を決めてから、そこを重複なく通る方法を考える方が効率が良さそうな気がしてきた。

Line Racing のときに使った二重頂点連結成分分解が使えるのか。

 

二重頂点連結成分分解による簡易判定と道順検索

判定

ある頂点からスタートしてある区画(頂点集合)が一筆書きできるかどうかの判定をしたいが、これは二重頂点連結成分分解を使うと概ね判定できるはず。稀に例外があるけど、ほぼ出くわさなかった気がする。二重頂点連結成分分解は頂点数に対して線形時間でできるので時間効率も悪くない。

 

  • 区画全体を二重頂点連結分解する
  • 各連結成分は木になる
  • 木が直線でなければ一筆書きはできない *1 
  • 直線であれば、各連結成分の要素をすべて選びながら順に進んでいくしかない
  • 各連結成分では入口と出口が一意に決まるので、連結成分ごとの判定に帰着できる(最後に到達する連結成分は出口に自由度がある可能性があるが、何パターンか試すことにする)
  • 各連結成分の判定は次のようにする 
    • 入口と出口を除く頂点集合について考える
    • 入口の隣接点のうち複数が葉(次数が 1 )であれば失敗
    • 出口についても同様
    • 入口と出口の偶奇(市松模様にしたときの色)が異なる場合、残りの頂点集合は偶奇がちょうど半数に分かれる必要がある
    • 入口と出口の偶奇が一致する場合、残りの頂点集合の偶奇は、入口・出口の偶奇ではない方がちょうど 1 だけ大きい必要がある
    • ここまでではじかれなかったものは成功と判定する

 

これでだいたいの場合にうまくいく。稀に反例もあって、図のようなとき、緑から赤マスをすべてちょうど一回ずつ通って逆の緑に行くことはできないが、上の判定法だと可能と判定されてしまう。

 


道順検索

例外を無視して判定が正しいとすると、一マス進んでも条件が満たされるかどうかを判定しながら、 OK になる方向に進めば良い。

(この実装では、一マス進むごとにマス数に対して線形時間かかるので、全体ではマス数の 2 乗オーダーになる。)

 

5 日目 - 12 月 5 日(火)

 

昨日考えてたのもなんかいまいちな気がして、部屋割りをいろいろやってみる。

通常マス(「汚れやすいゾーン」に入ってない)場合の汚れやすさは 10 以下なので、 11 以上のものは必ずゾーンに入っていることが分かるが、逆は言えない *2

11 以上のマスだけを見て連結成分をいい感じに分解すれば汚れやすいゾーンをまとめることができそう。同じ連結成分でも汚れやすさの比率が 10 倍を超えている *3 ペアがあれば、複数のゾーンが重なっていることが分かる。ふたつ重なっているとして、どちらのグループに属するかを判定するのはちょっと厄介。

適当に分けてみたけどいろんなパターンがあってむずい。

 

あとこれきれいにゾーン分けできたとして、そこからどうすれば・・・(ゾーンごとの順序焼きなましか?)

 

Seed 4

 

 

6 日目 - 12 月 6 日(水)

 

ゾーン方式だと形がいびつになって回収のときに困りそうだったので、部屋割り(長方形っぽいバージョン)も試してみた(けどここからどうすれば・・・)

 

 

7 日目 - 12 月 7 日(木)

上で書いた部屋内を重複なく回るロジックを入れてみた。 Seed 4 の上部の黄緑部屋を回る様子(ちゃんと重複なく進めてそう)。

 

 

 

進むロジック:

以降としている区間が二重頂点連結かつ一筆書きできる場合は、その条件を崩さないように動く

二重頂点連結でなければ、各二重頂点連結成分に分解して、成分ごとに最適ムーブをする

具体的には、各成分を頂点とする木ができるので、スタートからゴールまで進む

 

例えば、二重頂点連結成分を頂点とする木が次の図のようになっている場合で、①から⑤に行きたい場合は、①→③→①→②→④→⑤→⑥→⑤→⑦のように進む。複数回入る成分があるが、各成分の最初の入口から最終出口までの最適路を作っておいて、横道にそれるときはその部分を置き換えれば無駄なく回ることができる。

例えば②では①からの入口(関節点)から⑤への出口に向かう最短路を作っておいて、④につながる関節点を通ったときに寄り道して行って帰って来る感じで。

 

(左:①→②→⑤と動く場合の②内の動き、右:①→②→④→②→⑤にする場合の②内の動き)

 

あとは部屋の順番を焼きなませばそれっぽくなる。

近傍は①部屋の追加、②部屋の削除(複数ある場合のみ)、③部屋の順番の入れ替え(2-opt)の 3 種類。下記の前提で最終コストが部屋の順番から直接計算できるのでこれを評価関数とする。

  • 部屋のマス数および汚れやすさの合計を前計算
  • 部屋の中は必ずマス数で通れる前提
  • 部屋内の順番の違いは無視

 

連結成分内で重複なく取り切るのが不可能な場合などは、単純に「今いるマスに隣接する訪問予定マスのうち、出口から最も遠いマス」に進むことにした。その結果非連結になる場合は今いるマスを訪問予定のまま残した。

 

 

 

実際に Submission してみると、二重連結判定と最適経路計算が重くて 14 ケース TLE 。。

Submission

 

速度改善方法はいろいろあるのでなんとでもなるんだけど、ここまで実装つらくて萎えてしまった。

 

スコア改善の余地もまだだいぶあるはず

  • 最初の方針では汚れやすさがひどいマスを中心に基本ループを作っていたが、この方針だと部屋内の汚れやすさの違いを考慮できていない
  • 広い部屋や、部屋内部での汚れやすさにムラがある場合に部屋を分割する方法が考えられる
  • 行き止まりの部屋(特に隣接部屋が 1 つだけの部屋)は必ずその前の部屋を二度通ることになるので、ふたつを合体したベースで最適化をするのが良い
  • もともとの仕切りが少ない盤面では、部屋が少なすぎる( Seed 0 では 2 部屋になるのでこの場合も適宜分割する必要がある
  • 部屋間を繋ぐマスは適当に 1 つ固定したが、偶奇問題があるので少なくとも 2 つは試した方が良い

 

 

 

8 日目 - 12 月 8 日(金)

結局 2 日目( 9 位のとき)の Submission に戻した方が(TLE でケースが減ってるのを考慮しても)良くなったので一旦こちらに戻しておいた。

 

 

結局その後もアイデア止まりで実装まで行けず、これが最終提出。

 

 

ぐぬぬ

最初の方針と二重頂点連結成分分解をうまく融合させたかったけど、結局独立になっちゃったし後者は TLE しちゃったしで方針ミス感が否めないところ。一週間あるからいろいろ試してみるかーと思ってたけど二重頂点連結成分分解は結構つらいというのを思い出した。 Line Racing のときは(常設でやってたので)制限時間がないので無限時間かけて良かったけど、一週間ぐらいだと自分の実装力だとリスクが大きい。

探索アルゴリズムを使わずに CodinGame の Line Racing をやって Legend になった話 - Kiri8128の日記

 

 

 

End

 

*1:Line Racing のときはどの子に行くのが最善かを木 DP の要領で計算した

*2:ちなみにゾーンに入っていない場合の汚れやすさの平均は約 3.9 で、ゾーンに入っている場合の平均は 84 程度

*3:厳密には、小さい方を a として大きい方が 10a+5 以上

焼きなまし法が使えなくても AHC 橙になれたよ

 

 

AHC レーティング橙になりました!

AtCoderヒューリスティックレーティングが橙(2400+)になりました。

 

 

 

(参考:アルゴ橙記事)

kiri8128.hatenablog.com

 

AHC で橙になるまでにやったこと

  • AHC に出る

 

言語

基本 Python(PyPy)でやってました。 1 回だけ Rust で書き換えたことがあります(AHC 014)。

 

 

得意問題・苦手問題

 

同じレート帯の中では、基本的に高速化や探索ゲーは苦手で、評価関数や貪欲系が得意だと思っています。AHC と言えば焼きなまし法やビームサーチ等の最適化アルゴリズムを使う印象がある人が多いかもしれませんが、私は AHC でこれらをうまく使えたことはほとんどありません。逆に言えば、焼きなまし法が使えなくても橙ぐらいまでは十分狙えるということが示せたと思います。

 

【得意】

  • 評価関数ゲー
  • 貪欲ゲー
  • 戦略ゲー

 

【中間】

  • 盤面構築ゲー
  • 推定系

 

【苦手】

  • 焼きなまし
  • ビームサーチ

 

 

問題形式としてはインタラクティブのものに得意意識がありました。ただ入橙したときの AHC 026 が短期かつ非インタラクティブで大当たりを引いた影響が大きく、プロットしてみるとむしろ非インタラクティブ寄りにいるみたいです。

 

 

 

 

プロット方法について

なおプロットに用いた計算方式の概要は次のとおりです。

  • コンテスタント(参加者) c およびコンテストいくつかからなる集合 S について f_c(S) を、過去に S に含まれるコンテストのみに出ていたとした場合の  c の Rating とする
  • 長期コンテストの集合を S_{long} などする
  • x = f_c(S_{long}) - f_c(S_{short})y = f_c(S_{int}) - f_c(S_{non int}) をベースにして、次の 2 つの調整をした位置に c の ID をプロットする
    • レートが高いほど影響を強くする(一色で 1.08 倍)
    • プロットが一部分に集中しすぎないように単調増加な奇関数で調整
  • 文字の大きさはレート依存(1600 以上は一色で 1.5 倍、 1600 以下は 3 色で 1.5 倍)
  • ただし文字数による調整あり

 

使ったコンテストはこれまでの Rated コンテストです。カテゴリは下記のとおり設定しています *1

 

コンテスト 問題 長期 or 短期 回答形式
AHC001 AtCoder Ad 長期 インタラクティブ
AHC002 Walking on Tiles 短期 インタラクティブ
AHC003 Shortest Path Queries 長期 インタラクティブ
AHC004 Alien's Genome Assembly 短期 インタラクティブ
AHC005 Patrolling 短期 インタラクティブ
RECRUIT 日本橋ハーフマラソン 2021〜増刊号〜 農場王X 長期 インタラクティブ
HACK TO THE FUTURE 2022 予選 Project Leader 長期 インタラクティブ
AHC006(京セラプログラミングコンテスト) Food Delivery 短期 インタラクティブ
AHC007(THIRD プログラミングコンテスト 2021) Online MST 短期 インタラクティブ
AHC008 Territory 長期 インタラクティブ
AHC009(モノグサ プログラミングコンテスト2022) Robust Memory of Commuting Routes 短期 インタラクティブ
AHC010(ALGO ARTIS プログラミングコンテスト2022) Loop Lines 短期 インタラクティブ
AHC011 Sliding Tree Puzzle 長期 インタラクティブ
AHC012 AtCoder 10th Anniversary 短期 インタラクティブ
AHC013(RECRUIT 日本橋ハーフマラソン 2022夏) Server Room 長期 インタラクティブ
AHC014(estie プログラミングコンテスト2022) RectJoin 長期 インタラクティブ
AHC015(トヨタ自動車 プログラミングコンテスト2022) Halloween Candy 短期 インタラクティブ
AHC016(HACK TO THE FUTURE 2023 予選) Graphorean 長期 インタラクティブ
AHC017(THIRD プログラミングコンテスト 2022) Road Repair 長期 インタラクティブ
AHC018(RECRUIT 日本橋ハーフマラソン 2023冬) Excavation 長期 インタラクティブ
AHC019(MC Digital プログラミングコンテスト2023) Silhouette Block Puzzle Creation 長期 インタラクティブ
AHC020(ALGO ARTIS プログラミングコンテスト2023) Broadcasting 短期 インタラクティブ
AHC021(TOYOTA Programming Contest 2023 Summer) Pyramid Sorting 短期 インタラクティブ
AHC022(RECRUIT 日本橋ハーフマラソン 2023夏) Exploring Another Space 長期 インタラクティブ
TOYOTA Programming Contest 2023 Summer final Transit Warehouse 短期 インタラクティブ
AHC023(第10回 Asprova プログラミングコンテスト) Crops on Grid 長期 インタラクティブ
AHC024(丸紅プログラミングコンテスト2023) Topological Map 短期 インタラクティブ
AHC025 Balancing by Balance 長期 インタラクティブ
AHC026(トヨタ自動車プログラミングコンテスト2023#6) Stack of Boxes 短期 インタラクティブ
AHC027(HACK TO THE FUTURE 2024) Recurring Cleaning Route 長期 インタラクティブ
AHC029(RECRUIT 日本橋ハーフマラソン 2024冬) Business Simulation Game 長期 インタラクティブ
AHC028(ALGO ARTIS プログラミングコンテスト2023 冬) Lucky Words 短期 インタラクティブ
AHC030(THIRD プログラミングコンテスト2023) Polyomino Mining 長期 インタラクティブ

 

成功回の傾向と戦略

これまでの参加で順位が良かった回(Rated 50 位以内)の戦略です。表を見ると、評価関数や貪欲で稼いでいることが分かります。

 

順位 コンテスト 問題 解法概要 解法リンク
【番外編】Unrated 2 位 新ジャッジテストコンテスト -Heuristic- AtCoder Contest Scheduling (Online Version) 謎の評価関数に基づく貪欲 リンク
4 位 AHC 026 (トヨタ自動車プログラミングコンテスト2023#6) Stack of Boxes 貪欲 リンク
13 位 AHC 018(RECRUIT 日本橋ハーフマラソン 2023冬) Excavation 評価関数と戦略 リンク
26 位 AHC 025 Balancing by Balance 戦略 リンク
27 位 AHC 021(TOYOTA Programming Contest 2023 Summer) Pyramid Sorting 評価関数に基づく貪欲 リンク
36 位 RECRUIT 日本橋ハーフマラソン 2021〜増刊号〜 農場王X 評価関数と戦略 リンク
38 位 AHC 008(MC Digital プログラミングコンテスト2022) Territory 盤面構築+戦略 リンク

 

 

評価関数・貪欲の考え方

 

評価関数・貪欲ゲーのときに高順位になることがあり、評価関数をどうやって作っているかなど聞かれることがあります。

 

「天才貪欲」「天才評価関数」のような呼ばれ方をすることもありますが、天から降って来る訳ではなく、また何も考えずに作ったらたまたま当たるという訳でもなく、ある程度根拠のある(数値化できる)指標や簡素化した状況での理論値をもとにアレンジして作るというのが基本だと思っています。

以下で自分なりの考え方や普段考えていることを書きます。なお、今後のコンテストでも広く使えるようにしたいので、なるべく汎用的・抽象的な記載にしています *2

具体的な使用例があるものは後述します。

 

  • 問題を簡素化する
    • AHC の問題は厳密解が計算できないように適度に複雑になっていますが、なんらかの簡素化を行うことで状況をつかみやすくします
    • 簡素化というのは、問題の本質を失わない範囲で情報を捨てるなどにより簡単にすることです。例えば「取得・計算できうる情報のうち、『ある部分』について計算コストがとても大きいが、そこを無視しても結果に 10% 程度しか影響しない」などが分かれば、その部分を捨てることで、考察を簡単にしたり計算の実行時間の節約につなげたりすることことができます
    • なんでも切り捨てればよい訳ではなく、考察・計算のコストが高い割に最終結果にほとんど影響しない部分を捨てるのが大事です
  • 寄与の概算
    • いくつかの簡素化前提をおくことで、その前提の下での理論値を計算できたり、各種指標に対する寄与を直接計算できるようになったりことがあります
    • 仮に最終スコアに対する寄与が計算できれば、それが最大になるものを選ぶとそれっぽい貪欲になります
  • どうなると嬉しいかを理解する
    • 嬉しさを数値化をしておくと便利です
    • この嬉しさは、直接何らかの寄与になっていなくても、大小比較のための順序を決めるためだけの情報でも OK です
    • 複数の嬉しさを合算する場合は、係数を吟味する必要があります
    • 例えば AB も大きい方が良いなら単純に A+B を指標にする手もあるかもしれませんが、 A1 増えることが B10 増えるぐらいの効果がありそうなら 10A+B を指標にするのが良いですね。
  • 評価関数の設定
    • 行動を決定するタイプの問題では、各行動に評価を定めることで評価関数ゲーに落とし込むことができます
    • 最終スコアに対する寄与でなくても、「嬉しさ」を基準とした評価関数でも OK です
    • 複数の指標がある場合もすべて評価関数に合計すれば良いですが、優先度の高いものの影響が大きくなるように調整します(嬉しさの項と同様)
    • 不確実性による評価の補正が有効な場合も多いです(すぐに実現できるものは確実性が高いが、将来実現できる予定のものは状況によって変わる可能性があるので適当に割り引くなど調整する)
    • ターゲットを定めることも有効です(1 ターンで○点ぐらいは欲しい、最適解だと△点ぐらい取っているはずだ、など)
  • ステップを分解する戦略
    • 特にターン制の問題では、まず序盤で○○という状況にする→その後△△を行う、という複数ステップでの攻略が有効になることがあります
    • 「○○なら△△が計算できるのに・・」「□□という状況ならあとは貪欲でできるのに・・」のような願望があるときに、現実的なコストをかけることで実現できるなら試してみるのもありかもしれません
  • 解法選択時の概算
    • 解法・アイデアが浮かんだとしても、結果的に外れ方針になることもあります
    • 実装に走る前にその方法でどれぐらいのスコア・順位が見込めるかを概算することで、外れ方針に突っ走ってしまうリスクを減らせます *3
    • あるいは逆に、上位陣のスコアや目標スコアをもとに、どれぐらいの改善が求められるのかを想定しながら解法を考えることが有効になることもあります
    • 例えば 1 ターンのコストを平均 10 に抑えたい場合、ターンごとに  8 のコストを掛ける処理は相当なベネフィットがないと使えないが、平均 0.5 程度のコストであればガンガン使って良さそう、など。コストとリターンの両方が数値化できるとなお良いです。
  • パラメータの設定
    • 上位陣では、手元でたくさん回すことでチューニングしているのを見かけますが、私はあまりやっていません(できていません)
    • 基本的に、パラメータは最初はなんらかの概算を行って最適そうなものを選びます
    • コンテスト終盤になったらいくつかのパターンを比較することも検討しますが、当初の予定と大きくずれることはあまりないです
    • 序盤でチューニングしすぎるとメタ局所最適に陥る可能性があります。
  • 平均と分散
    • たくさんの入力変数や乱数がある場合、個々の平均と分散(および独立でない場合は共分散)が分かればそれらの合計の分布の平均と分散が分かります
    • 変数の推定の際、平均と分散が分かれば十分なことも多いので、分布が複雑な場合などでもまずは平均・分散を調べるのは有効です
    • 理論値が計算できなくても、入力データを乱数から作成することで、平均・分散の予測をすることもできます
  • 入力の分布
    • AHC では、入力の制約だけでなく、入力の生成方法(確率分布)が与えられます *4
    • 回によっては「必ずしも理解しなくても良い」のような文言があることもありますが、これはワナです。必ず熟読して理解しましょう。
    • 各パラメータがどのような値を取り得るかを理解することで、その後の各種概算が可能になります。
    • 場合によっては、いろいろな指標の理論値(平均・分散など)が計算により求まることもあります。

 

イメージが付きづらいものもあるかもしれないので、次節でうまくいった例を挙げてみます。

 

うまくいった例

寄与と嬉しさ、ターゲット

寄与と嬉しさを考えてうまくいった例としては、(上でもでてきた)新ジャッジテストコンテスト Heuristic があります。こんな感じで考えてました。

「上振れ」は上述の「ターゲットを定める」に近い考え方です。

 

 

 

複数ターンで達成できる効果

複数ターン等を使ってある状況を得るような場合は、 1 ターンあたりなどのコストに置き換えると公平に評価できます。例えば 農場王X では、連結を保っているマスの集合から k マス離れたところに評価が s であるマスがあれば、 \displaystyle\frac{s}{k} などと評価できます。ただしあまり遠い場合は不確実性が増える(そこまで行くまでに他の有力候補が出てくるなど)ので、適宜割り引く方法もあります。もし厳密解を求めたいなら他のすべての選択肢を考慮して今やろうとしている方法に勝つのがあるかを計算する必要がありますが、それだと計算量が爆発しますよね。ヒューリスティックではあまりに複雑なところは確率処理することで簡素化できます。

 

 

解法の概算

解法の概算が役に立った例としては、 AHC 026 があります。本問の戦略としては、

  1. 各列をソートする
  2. 列ごとに近い数を集める(例えば 0~19 は左端の列に置くなど)

などが考えられます。 1. では、ひとつずつ出す・戻すをすると一回のコストは 2 なので、列ごとに 40 、合計 800 のコストがかかりスコア 9200 点ぐらいが狙えそうです。複数同時移動も許すと、確率 \displaystyle\frac{1}{2} でくっ付けられると考えると一回のコストは 1.5 程度に抑えられるので、特に工夫しなくてもスコア 9400 は出せそうと予測することができます。

一方、 2. の方法では、例えば

  • 一旦すべて右端の列に集める(コスト 21\times 9=189
  • 上から見て列 1~9 に分解する(コスト約  2 \times 200=400
  • 小さいやつの列から見て順に回収する(コスト 2\times 200=400 弱ぐらい)

という方法がありますが、これだとスコア 9100 も達成が難しそうです。

 

実はコンテストの序盤(30 分~ 1 時間ぐらい?)で、一瞬 2. の方法を検討していたんですが、順位表を見たら既に 9300 程度の人がいたのですぐに棄却して再考したところ 1. を思い付くことができました。

 

 

 

 

影響による優先度付け

概算ではなく実験によって効果が小さそうだったから無視した例もあります。下記は ハーフマラソン2021 のコメントです。

 

 

 

ステップに分解する戦略

「ステップ分解」は AHC 026 (ソートしてから出す)、 AHC 025 (グループソートしてからチャレンジする)、 AHC 008 (まず犬トラップをして、その後は壁を配置してから仕留めに行く)などで使えました

 

簡素化前提による理論値計算

AHC 018 解法 の最後のところで一段階の攻撃力を  \sqrt{\displaystyle\frac{2hC}{k}} にするところなどでは、問題を簡単にして相加平均・相乗平均の関係から(簡素化前提での)理論値を求めて使いました。

 

 

 

その他工夫など

その他、 AHC コンテスト中に考えていることや工夫などを列挙しています。

 

  • 盤面の設定
    • テストケースによらず強い盤面が存在するときは、事前に盤面を決めて固定する(AHC 008 など)
  • 拡張性の高いコード
    • 最初のアイデアだけでなく、将来的に使うであろうアイデアを考えて拡張しやすい設計にしておく
    • 最初は使わない機能でも枠だけ作っておいて自明設定にしておく(あとで必要があれば書き換える)など
    • 終盤に局所的に良いアイデアを思いついたとき、設計が窮屈だと実装が大変すぎて断念してしまうことになるともったいない
  • 戦略の工夫
    • 自由度と扱いやすさのトレードオフ
      • AHC 018 では、ルートを必ず 10 マス刻みの格子を通るという制約を付けることで、自由度を犠牲にしながら実装・考察を簡素化する選択をした
    • コンピュータに任せる探索と簡素化前提に基づく理論値計算の最適化の併用
      • AHC 016 では、ある前提に基づく理論値を計算することで計算量を改善した。ただし 記事 にも書いたように結果的にはうまくいかなかった点もある

  • 実行速度と実装速度のトレードオフ
    • まずは動くことが大事なので、実行速度は遅くても実装しきるのが大事
    • ただし後から部分的に改善できるように、どの部分でサボっているかを理解しておくのと、後から修正しやすい設計にしておくとよい
  • デバッグの工夫
    • 提出コード、手元実行コード(1 ケースのみ)、手元実行コード(複数ケースで得点確認)、コードテスト、などを同じコードで実行できるようにしておく
    • 手元実行コード(1 ケースのみ)では、デバッグ用の出力を無限に吐き出して、意図通り動いているかをチェックする
    • 実行時間が大事な場合は、実行時間を処理ごとに計測して何がボトルネックになっているか検証できるようにする
  • 設計と実装の役割分担
    • 特に長期だと設計をちゃんと作らず実装を始めると混乱してやっぱりやめるみたいなことになりがち
    • 設計を作る人と実装を作る人を分けるとお互いに自分の役割に専念できて良い
    • ただし AHC では複数人参加が認められていないので、長期コンなら例えば「昼の自分が設計書を書いて夜の自分に実装を依頼する」→「夜の自分は依頼を見て、期日(翌朝)までに納品する」みたいにやるとよい
  • 手元の実行速度とジャッジの実行速度の差
    • 手元では PyPy 環境を構築していないので、ジャッジに比べて 5~10 倍ぐらいの時間がかかることが多い
    • コードテストでループ数を計測して、何倍の時間回せば同じ条件になるか調べておく
  • 得点・改善量の見積もり
    • 実装しようとしている解法で何点取れるのかを事前に見積もる
    • 局所的な改善では、改善量があまりに小さいと実装時間をかけたくないことがある
    • 改善量をある程度見積って効率(≒予測改善量÷実装時間)の良いものを優先する

 

 

 

  • ビジュアライザの活用
    • ある程度のものが作れたら、そこからの改善はアイデアや微調整が多くなる
    • そうなるとビジュアライザが有効。具体的には次のような感じ。
      • ビジュアライザをステップごとに実行して、「このターンではこっちの方が良いのでは?」というのを見つける
      • 単にビジュアライザの動きを見ているだけではなぜそう判断したのか分からないので、適宜コメントや手元実行のデバッグコメントを見てなぜそう行動したかを確認する
      • ロジックに改善点できるがあれば、それを抽象化して設計に落とし込み実装する
      • 修正前に比べて良くなったか検証する
    • ビジュアライザは自動実行ではなく、 1 ステップごとに見るのが良い(必ずしも全ステップ見る必要はなく、大きな動きをするところだけでも良いかも)
  • 入力パラメータによる場合分け
    • 特に長期コンでは、入力パラメータごとに最適な戦略が異なる場合が多い
    • 極端な例でのスコアを確認したり、ビジュアライザを回してみたりしてどういうケースで弱いのかを把握する

 

 

FAQ

Q: 焼きなましを使わないのはなんで?

A: 敢えて使ってないんじゃなくて、使おうとしたこともあるけど結果的に順位に反映されていない感じです。例えば AHC 024 も焼きなましを実装する予定だったけど本番中間に合わなかった感じ。

 

 

 

Q: ヒューリスティックでも Python しか使わないのなんで?

A: まだ環境構築などの準備と言語の習得が整っていないので使えていないです。幸い、私が得意な貪欲ゲーや評価関数ゲーのときは Python の実行速度面の弱点があまり効かないので、結果的にそこまで不利になっていない感じです。

焼きなまし法などを本格的に使うようになると高速化が本質になってくるので、そうすると Rust などの速い言語を使うのも有効だと思っています。

 

Q: 並列処理の環境構築するって言ってなかった?

A: まだできてませんごめんなさい。

 

Q: アクチュアリーをやってるって聞いたけど、業務でプログラミングしてる?

A: 今のところ、業務でプログラミングをすることはないです。

 

Q: アクチュアリー業務をしていて AHC に有利になることはある?

A: アクチュアリー業務で扱う決算数値や経営成績などの指標は、市場環境や顧客行動などさまざまな要因に影響されます。それを分析や経営判断に生かすため、(専門家ではない)経営陣等にも因果を含めて説明する必要があります。このため、どの事象がどの指標に影響しているかなどのメカニズムを理解し、簡易的に分かりやすくモデル化して説明するという必要性が多くあります。このように問題の本質を崩さない範囲でシンプルに体系化するという作業は、 AHC の評価関数を作る場面などでまさに必要とされることだと思っています。

 

Q: 新ジャッジコン(ヒュ)の 1.8 乗解法が意味不明なんだけど・・?「(d - last_i) を 2 乗したい」とか「それはやりすぎなので 1.8 乗」について詳しく教えて

A: [tex:(d - last_i)] はこれまでコンテスト i が開催されなかった期間です。コンテストの種類によってコストの係数 c_i が異なるので開催頻度は変わりそうですが、対称性からだいたいこれまでに経過した期間と同じぐらいの期間後に開催されると想定するのが自然ですよね。そこで c_i * (d - last_i)^{2} を使うのが一案になり、これでも十分強いです。

ただこれだと c_i * (d - last_i)^{2} が一致しているものは同等に扱うことになります。実際はこれらの中では c_i が少ない方( (d - last_i)^2 が大きい方)は回収までの日数の期待値が長く上振れを引きやすいことから、将来の大上振れに期待するのが( c_i が大きい方に比べると)良いことになります。この影響を含めると最適な指数は 2 乗より少し小さくなるはずですね。 1 乗や 1.5 乗にするほど大きな影響とは思えないので、 1.8 乗ぐらいに最適解がありそうと分かります。

 

Q: ほかに質問があったらどうしたら良い?

A: リプ等で教えてもらえればなるべく回答します。

 

 

 

 

 

 

*1:記事執筆以降も追加しています

*2:普段から考えている人にとっては当たり前と思うかもしれませんし、逆に慣れていない人にとってはイメージが付きづらいかもしれません。

*3:特に短期コンだと方針の修正が難しいので、早い段階で概算できるのが望ましいかもしれません

*4:保証されているかどうかは確認できていないですが、少なくともこれまではすべて与えられていたはずですし、競技性を考えると今後も与えられるべきだと思います

AHC 025

 

 

AHC 025

 

AHC025 の参加記です。

 

プレテスト 94.158B で暫定 27 位でした。

(追記:システス 469.343B で 26 位でした。)

 

総評

  • 面白い
  • 通常、焼きなまし・山登りはうまい近傍を作ることと、なるべく高速化することで時間内に探索をたくさん回すことを要求される
  • 今回はインタラクティブなので、実行時間ではなく、比較クエリの回数を少なくすることが重要になる
  • つまりある意味で制限付き最適化になっている

 

 

最終提出の方針

  • 山登り方式(悪化する方向の変動は許容しない)
  • 近傍は、 1 つ移動、一対一交換、複数交換など
  • 事前に全グループをソートして、入れ替えがあった場合もソートをキープする(最初に D\log_{2} D 回程度、入れ替え時に 2\log_{2} D 回程度のクエリを使う)
  • クエリ回数に余裕がある場合は、アイテムも事前にソートする
  • アイテムソート時は、 1 つ移動で可能な条件を調べておき、早めに使う(それ以降は 1 つ移動が有効になることはない)
  • 入れ替えの探索は主に下記を使っている。各方式の詳細は後述。
    • ランダム
    • 貪欲方式
      グループ 2 つから差が近いものを選び、その差にぎりぎりマッチするものを貪欲に選んで追加する
    • しゃくとり方式
      グループ 2 つの それぞれ について、小さい方から k 個を選び、それらの部分集合( 2^k 個ずつ)をソートし、しゃくとり法の要領で比較する
    • 二分探索方式
      グループ 2 つの 和集合 から、小さい方から k 個を選び、それらの部分集合( 2^k 個ある)をソートしておく。残りの要素で近いものを作って、二分探索の要領で最も近いものと比較する

 

個人的な目玉は「二分探索方式」で、少ないクエリ回数でソートできる(後述するが、例えば k=4 のとき 2^4 個の部分集合を 4 回のクエリでソートできる)ことなどから、効率よく探索することができる。

 

 

 

以下は各日にやったことの日記。

 

1 日目

問題を見る。考えたこと。

  • 情報が全部分かっていたら 1 個の移動、 2 個のスワップなどを近傍とする焼きなまし法が使えそう。
  • 天秤でも山登りはできる。
  • 各々の重さを推定できれば便利だけどどこまで正確に予測できるんだろう?
  • めちゃくちゃ正確に予測できればナップサック的に(例えば D=2 などなら)厳密解が出せたりするのかなー
  • たくさん試せるなら、まずは N 個をソートしておくのも便利そう。
  • 焼きなましはクエリ回数がもったいないのでさすがに使えないか・・?

 

山登り

とりあえず山登りで。

初期状態として、個数が均等になるように適当にグループ分けする。近傍は 1 つ移動と 2 つのスワップ2 つ。移動・スワップした方が良いかどうかは 23 回のクエリで確認できる。

 

1 つ移動

 

グループ A とグループ B を適当に選ぶ。このとき重い方を B とする(これは 1 回のクエリで確認できる)。

グループ B からアイテム i をグループ A に移動させる。アイテム i の重さを x とすると移動させた方が良い条件は、

 

|(w_A+x)-(w_B-x)| \lt w_B - w_A

\iff w_A - w_B \lt w_A-w_B+2x \lt w_B - w_A

\iff w_A \lt w_B - x

 

となり、これは 1 回(最初の判定とあわせて 2 回)のクエリで確認できる。

 

2 つスワップ

グループ A のアイテム i (重さ x )とグループ B のアイテム j (重さ y )のスワップも同様に

 

|(w_A-x+y)-(w_B-y+x)| \lt w_B - w_A

\iff w_A - w_B \lt w_A-w_B-2x+2y \lt w_B - w_A

\iff x \lt y かつ  w_A - x \lt w_B - y

 

となり、これは 2 回(最初の判定とあわせて 3 回)のクエリで確認できる。

 

第 1 提出

試しに 1 つ移動のみ実装して投げてみた。

 

 

これ実は 42 RE になっていて、 0.58 で割ると実質 99.5B ぐらい。案外いけるかも?

 

第 2 提出

バグを修正して、2スワップも実装して投げるとその時点で 1 位に。

 

 

絶対スコア 151,762,296

 

 

順位の逆算

 

今回は「順位スコア」を採用しているので、順位表を見ると自分が平均で何位を取れているかが分かる。

例えば、上の第 2 提出の得点 S=99446153841 点について、 (10^{11}-S)\times 130\div 10^{9}=72.00000067 となる。 130 は提出者数(順位表で確認しても良いが、この計算の小数点以下がほぼゼロまたは 0.5 に近くなるものを適当な区間で全探索しても良い)。四捨五入の端数を無視すると、全テストケース合計で 72 人に負けている、すなわち各テストケースで平均 1.72 位を取れていることが分かる。

得点より順位の方がイメージしやすいので、手元で変換して確認していた。

 

 

クエリ回数改善

過去にクエリに投げた情報を全部保持して、同じクエリ(左右逆も含む)を聞きそうになったら過去の結果を参照するようにした。

また、 1 つのアイテム同士を比べるクエリについては、推移率( x\le yy\le z から x\le z が分かる)も使って過去に聞いた情報だけで得られる場合は再度聞かないようにした。

 

 

推定

 

1 点同士の比較
  • 小さい方から大きい方に辺を張ってグラフを作る。
  • ある頂点の重さは、自分より小さい側の最大値と自分より大きい側の最小値の間に入るはずなので、その中間ぐらいに設定する。
  • 最初はどの重さも分からないが、たくさん繰り返すと収束するはず。
  • 平均が期待値と一致するようにスケール調整する。
  • 期待値は、上限が切られていることを考慮して \displaystyle\frac{1}{\lambda}-\frac{M}{e^{N/D}-1} とした。
順位統計量の期待値
  • 上の結果だとあまりきれいにならなかったので、計算結果の順位のみを使って順位統計量の期待値に一致するようにした
  • つまり、軽い方から i 番目(0-indexed)の重さを F^{-1}\bigg(\displaystyle\frac{2i+1}{2N}\bigg) とした。ただし F は累積分布関数で、ここでも上側が切られていることを考慮した。
複数グループの比較
  • 上で決めた結果を初期値とする。
  • 1 点同士も含む)すべての比較結果について、現在の推定値による結果で矛盾が生じたときに、比較したグループの結果を調整する。
  • 更新前のグループ LR の重さの和の比率が k であるときは、更新後の比率が \displaystyle\frac{1}{\sqrt{k}} になるように、両グループの重さにそれぞれ定数をかけた(倍率は連立一次方程式を解けば求まる)。
  • これを何度か繰り返す

 

Seed 0 でやってみるとこんな感じ。うーん、ないよりは点数上がったけどいまいち。。

 

真の値 42,789 26,023 52,131 52,694 41,816 1,734 25,720 142,117 34,123 18,227 74,649 4,126 62,911 83,007 175,627 2,819 232,807 210,456 70,234 184,590 86,146 26,456 48,810 33,189 180,024 134,174 45,597 59,565 56,446 124,428 75,874
予測値 58,093 39,809 5,967 12,461 50,456 8,244 11,677 364,369 34,685 16,996 180,839 29,021 64,862 82,005 74,523 33,275 302,911 350,207 185,087 99,226 52,976 41,785 76,042 121,018 98,192 68,048 142,293 64,041 132,559 190,753 73,054
比率 1.358 1.530 0.114 0.236 1.207 4.755 0.454 2.564 1.016 0.932 2.423 7.034 1.031 0.988 0.424 11.804 1.301 1.664 2.635 0.538 0.615 1.579 1.558 3.646 0.545 0.507 3.121 1.075 2.348 1.533 0.963

 

クエリが多い Seed 71 で試してみるともうちょいいい感じになった。

 

真の値 103,997 67,521 189,874 115,800 189,235 117,161 77,078 181,919 253,400 2,973 415,450 45,454 2,098 22,920 149,816 30,364 77,052 42,503 82,899 113,182 20,831 33,645 207,407 329,755 23,319 173,951 271,475 75,645 119,909 203,309 160,528 155,603 60,092 167,204 1,124 153,655 159,884 17,394 34,120 79,969 9,168 151,007 7,624 241,418 6,260 152,963 105,249 206,674 313,036 48,929 96,614 20,247 11,347 48,068
予測値 75,003 59,419 134,650 76,095 148,797 76,053 69,328 113,048 230,101 20,230 480,806 48,478 16,139 46,478 79,915 43,720 70,903 62,528 72,633 74,172 37,533 54,599 156,202 303,059 40,815 123,258 345,958 61,327 74,227 150,408 100,435 89,606 65,545 118,945 9,530 105,945 93,626 38,437 47,304 65,474 23,770 88,160 22,541 278,293 20,504 83,033 71,609 140,319 299,606 54,305 70,013 43,743 38,321 50,471
比率 0.721 0.880 0.709 0.657 0.786 0.649 0.899 0.621 0.908 6.805 1.157 1.067 7.693 2.028 0.533 1.440 0.920 1.471 0.876 0.655 1.802 1.623 0.753 0.919 1.750 0.709 1.274 0.811 0.619 0.740 0.626 0.576 1.091 0.711 8.479 0.689 0.586 2.210 1.386 0.819 2.593 0.584 2.957 1.153 3.275 0.543 0.680 0.679 0.957 1.110 0.725 2.160 3.377 1.050

 

 

2 日目

グループ同士の比較

グループ同士の比較についても 1 点同士の比較と同様、推移律を使って既に調べた情報から分かるものについては再度聞かないようにした。

 

考察として、情報を得るための行動と、実際に山登りを進めるための行動のどちらを選ぶかをうまく決める必要がある。

前者を優先するなら、まずはグループすべてをソートする方法がある。この場合、最上位の 2 つの比較などが有効になる。ただしこれを行う場合は近いものの比較を行っているため、実際に山登りが進む可能性は少ない。

後者を優先するなら、大きそうなグループと小さそうなグループを比べるのが可能性が高いが、グループ間の情報はほとんど得られない。

 

全部ソートするのは若干気が引けるが、最上位と最下位の 2 つを決めるというのはまあ悪くない方法だと思われる。

 

一対多の比較

特に小数の大きなアイテムを持つグループがあるとき、一対一だと限界があるので、一対多の比較も許容することにした。

 

一対多の比較

実装すると若干上がった。順位は下がっているように見えるが、提出直前は 13 位だったので一応上がっている。

 

 

絶対スコア 66,055,772 点。

 

バグ修正

発生確率は低いけど起こるとそこそこ大きそうなバグがあったっぽいので修正。このせいか乱数の影響か分かんないけど 6 位まで回復。

 

 

絶対スコア 60,420,846 点。

 

 

3 日目

グループ・アイテムの全ソート

グループごとの大きさはすべてソートしておくことにする。つまり最初にソートして、変動があったときにもソートをキープする。

最初のソートは D\log_{2}D 回ぐらい。また変動時にも 2\log_{2}D 回程度のクエリでソートをキープできる。一番大きいグループと一番小さいグループを動かすのが全体最適への効果も大きいことから、効率が良いと判断した。

なお制約から Q/D8 以上なので初期化は必ずできるが、最悪ケースで N=100,\ D=24,\ Q=200 のときは初期化に半分ぐらいのクエリを消費することになってしまうので、極端なケースは上下大きいところだけを調べる方法もありそう。ちょっとめんどくさそうなので後回し。

 

あと QN に比べて十分大きいときは、最初に N 個をすべてソートしておくことにした。

ソートにかかる回数は N\log_{2}N ぐらいなので、上記のグループソートと合わせてさらに N 回ぐらい余裕があることを条件とした *1

なおアイテム全ソートする場合は、先にソートしてからなるべく個数と重さが均等になるように初期グループを決めた。

 

 

深い探索 1 (貪欲方式)

11 だけじゃなくて、その差額に最も近いものを順次足していく方式にしてみる。

 

いろいろやると 1 位に!

 

 

4 日目

 

深い探索 2 (二分探索方式)

なるべく差が小さい入れ替えを行う工夫を考えてみる。

  • 2 つのグループ AB を固定して( B の方が重いとする)、それらの要素すべての中から小さい順に k 個選ぶ( k48 ぐらい)。
  • この k 個の部分集合は 2^k 個ある(この集合を S とする)が、これをソートしておく
  • 適当に差が小さいものを作って、その差ぎりぎりになるものを二分探索で求める

 

いくつか考察

  • SAB の両方の要素を含むとき、最後に調整できないと思うかもしれないが、最初 S\cap A 部分は含めず S\cap B 部分はすべて含めておくことで、 A 側の追加、 B 側の削除が同じ方向になるようにできる。
  • 2^k 個の要素は互いに比較ができる( 1 組の比較は 1 回のクエリでできる)。共通部分があればそれらを双方から除いて比較すればよい。
  • 個別要素がソートされている前提では、 2^k 個の要素のソートは実はクエリ回数はそんなにかからない。
  • 例えば k=32^3=8 要素)のとき 1 回、 k=42^k=16 要素)のとき 4 回以下のクエリでできる。 k=52^k=32 要素)でも 10 回ぐらいになりそう。
  • なお D=2 のときは、入れ替えが発生しても集合 S が変わらないので、このソートはサイズを決めたら全体を通して 1 回だけしか発生しない(つまり D=2 のときは大きめサイズで探索しておいても無駄が少ない)。

 

小さい方から i 番目の要素を 2^i のビットで表すと、 k=3 のときは

w_0 \le w_1 \le w_2,\ w_2 \le w_3 \le w_5,\ \ w_2 \le w_4 \le w_5,\ \ w_5 \le w_6 \le w_7 が分かるので、 1 回のクエリで w_3w_4 を比較すればよい。

 

k=4 のときは、次の通り比較すれば最悪 4 回のクエリでソートできる。なお簡単のため同じ重さにはならないとして不等号を記載しているが、同じ重さがあっても同じ方法でソートできる。

  • w_4w_3 を比較する
    • w_3 \lt w_4 のとき、 w_8w_6 を比較する
      • w_8 \lt w_6 のとき、 w_8w_5 を比較する
        • w_8 \lt w_5 のとき、 w_9w_6 を比較する
          • w_9 \lt w_6 のとき、 w_0 \lt w_1 \lt w_2 \lt w_3 \lt w_4 \lt w_8 \lt w_5 \lt w_9 \lt w_6 \lt w_{10} \lt w_7 \lt w_{11} \lt w_{12} \lt w_{13} \lt w_{14} \lt w_{15}
          • w_6 \lt w_9 のとき、 w_0 \lt w_1 \lt w_2 \lt w_3 \lt w_4 \lt w_8 \lt w_5 \lt w_6 \lt w_9 \lt w_{10} \lt w_7 \lt w_{11} \lt w_{12} \lt w_{13} \lt w_{14} \lt w_{15}
        • w_5 \lt w_8 のとき、 w_9w_7 を比較する
          • w_9 \lt w_7 のとき、 w_0 \lt w_1 \lt w_2 \lt w_3 \lt w_4 \lt w_5 \lt w_8 \lt w_6 \lt w_9 \lt w_{7} \lt w_{10} \lt w_{11} \lt w_{12} \lt w_{13} \lt w_{14} \lt w_{15}
          • w_7 \lt w_9 のとき、 w_0 \lt w_1 \lt w_2 \lt w_3 \lt w_4 \lt w_5 \lt w_8 \lt w_6 \lt w_7 \lt w_{9} \lt w_{10} \lt w_{11} \lt w_{12} \lt w_{13} \lt w_{14} \lt w_{15}
      • w_6 \lt w_8 のとき、 w_8w_7 を比較する
        • w_8 \lt w_7 のとき、 w_0 \lt w_1 \lt w_2 \lt w_3 \lt w_4 \lt w_5 \lt w_6 \lt w_8 \lt w_7 \lt w_{9} \lt w_{10} \lt w_{11} \lt w_{12} \lt w_{13} \lt w_{14} \lt w_{15}
        • w_7 \lt w_8 のとき、 w_0 \lt w_1 \lt w_2 \lt w_3 \lt w_4 \lt w_5 \lt w_6 \lt w_7 \lt w_8 \lt w_{9} \lt w_{10} \lt w_{11} \lt w_{12} \lt w_{13} \lt w_{14} \lt w_{15}
    • w_4 \lt w_3 のとき、 w_8w_5 を比較する
      • w_8 \lt w_5 のとき、 w_8w_3 を比較する
        • w_8 \lt w_3 のとき、 w_9w_6 を比較する
          • w_9 \lt w_6 のとき、 w_0 \lt w_1 \lt w_2 \lt w_4 \lt w_8 \lt w_3 \lt w_5 \lt w_9 \lt w_6 \lt w_{10} \lt w_{12} \lt w_{7} \lt w_{11} \lt w_{13} \lt w_{14} \lt w_{15}
          • w_6 \lt w_9 のとき、 w_0 \lt w_1 \lt w_2 \lt w_4 \lt w_8 \lt w_3 \lt w_5 \lt w_6 \lt w_9 \lt w_{10} \lt w_{12} \lt w_{7} \lt w_{11} \lt w_{13} \lt w_{14} \lt w_{15}
        • w_3 \lt w_8 のとき、 w_9w_6 を比較する
          • w_9 \lt w_6 のとき、 w_0 \lt w_1 \lt w_2 \lt w_4 \lt w_3 \lt w_8 \lt w_5 \lt w_9 \lt w_6 \lt w_{10} \lt w_{12} \lt w_{11} \lt w_{7} \lt w_{13} \lt w_{14} \lt w_{15}
          • w_6 \lt w_9 のとき、 w_0 \lt w_1 \lt w_2 \lt w_4 \lt w_3 \lt w_8 \lt w_5 \lt w_6 \lt w_9 \lt w_{10} \lt w_{12} \lt w_{11} \lt w_{7} \lt w_{13} \lt w_{14} \lt w_{15}
      • w_5 \lt w_8 のとき、 w_8w_6 を比較する
        • w_8 \lt w_6 のとき、 w_9w_6 を比較する
          • w_9 \lt w_6 のとき、 w_0 \lt w_1 \lt w_2 \lt w_4 \lt w_3 \lt w_5 \lt w_8 \lt w_9 \lt w_6 \lt w_{7} \lt w_{10} \lt w_{12} \lt w_{11} \lt w_{13} \lt w_{14} \lt w_{15}
          • w_6 \lt w_9 のとき、 w_0 \lt w_1 \lt w_2 \lt w_4 \lt w_3 \lt w_5 \lt w_8 \lt w_6 \lt w_9 \lt w_{7} \lt w_{10} \lt w_{12} \lt w_{11} \lt w_{13} \lt w_{14} \lt w_{15}
        • w_6 \lt w_8 のとき、 w_8w_7 を比較する
          • w_8 \lt w_7 のとき、 w_0 \lt w_1 \lt w_2 \lt w_4 \lt w_3 \lt w_5 \lt w_6 \lt w_8 \lt w_7 \lt w_{9} \lt w_{10} \lt w_{12} \lt w_{11} \lt w_{13} \lt w_{14} \lt w_{15}
          • w_7 \lt w_8 のとき、 w_0 \lt w_1 \lt w_2 \lt w_4 \lt w_3 \lt w_5 \lt w_6 \lt w_7 \lt w_8 \lt w_{9} \lt w_{10} \lt w_{12} \lt w_{11} \lt w_{13} \lt w_{14} \lt w_{15}

 

これを踏まえて、 2^k 個のソートをするとき、次のようにすることにした。

  • まず 2^{k-1} 個の要素 w_0,\cdots w_{2^{k-1}-1} のソートを(帰納的に)行う
  • このとき w_{2^{k-1}},\cdots w_{2^{k}-1} の順序も確定することに注意
  • 2^{k-1} 個のソートされたリストが 2 つできる(インデックスが小さい方を A 、大きい方を B とする)ので、 B 側の要素のそれぞれについて A 側の要素のどの隙間に入るか決めれば良い
  • B 側の要素のうちまだどこに入るか決まっていない要素のうち最小のものを b とする。現在分かっている情報から、 b との大小が分かっていない A の要素が x 個あるとする。
  • x \le 2 ならそれらのうち最小要素と比較し、そうでなければ小さい方から 2 番目の要素と比較する。

 

なおこのアルゴリズムは、上で書いた k=4 の場合の具体例の一般化になっている。

 

5 日目

 

 

D が小さくて Q/N がある程度大きいときは二分探索方式でかなり良い点数が出せるようになった。

Seed 147 などは 80 パーセントぐらいの確率で厳密解(スコア 1 )が出るようになった。ただし乱数要素が少ないので、確率はあまりあてにならず、例えば似たようなケースでも、Seed 99 ではほとんど 201 点(差が 2 )になる。

こういうケースなら割といい線行ってるんじゃね?と思って試しに D \le 3 かつ Q \gt 15 N の条件で絞って投げたけど、該当ケースなし。。仕方ないから D \le 4 かつ Q \gt 12 N の条件で絞ってみたら 1 ケースだけヒットしたみたいで、得点率 99.94\% で無事 896 人中 1 位タイ *2 になった。

 

 

 

深い探索 3 (しゃくとり方式)

さっきの「二分探索方式」では、入れ替える 2 つのグループを合わせて小さい方から k 個の部分集合をソートしたが、今回はグループ A とグループ B のそれぞれについて、小さい方から k 個の部分集合すべてをソートする。つまり大きさ 2^k のソート済み配列が 2 つできる(これらを L_1 および L_2 とする)。これらをしゃくとり法の要領で小さい方から見ていき、 L_1 側の要素と L_2 側の要素がこの順に隣り合う箇所について、うまくいくかチャレンジする。

 

「二分探索方式」では、ある程度のクエリ回数を使うとかなり小さい差でも山登り候補を見つけることができるという点は良かったが、集合 S に含まれないものも用意する必要があり、特に D が大きい場合には十分に収束する前にクエリ回数が尽きてしまうという問題があった。

「しゃくとり方式」では、比較のチェックが選んだ部分集合の中で完結するので、収束するまでの比較的山登り候補が見つけやすい状況では効率が良くなる。

 

 

6日目

目に見える進捗はなし。。

 

そういえばスコアの評価は、手元で 100 ケースとか回して、スコアの相加平均と相乗平均を見て適当に決めてたけど、相乗平均はスコアが 1 があるかないかで変わってしまうので 100 を足すとかにしても良かったかも。

あと回す Seed の開始位置は毎日ずらすことにした。そうしないと無意識に特定のケースに過学習してしまう可能性があるので(今までなりがちだった)。

 

7日目

最小値スライド方式

良く考えると、アイテム・グループのソートを維持している場合、 1 点移動ができるかどうかは最小グループとの交換のみ考えればよく、かつグループ間で移動・交換があっても条件が緩まることはないので、どのグループで何番目のアイテムまで可能性があるかを管理すれば無駄な 1 点移動のチェックを行う必要がなくなる。

 

 

8日目~9日目

確率的確認方式

だいたいの判定で良い場合、クエリ回数を使わずに確率的に判定する方法がある。要素ごとの期待値・分散から判定する方法もあるが、近いふたつの差などは独立と仮定するとうまくフィットしない。予め例えば 100 回ぐらい要素を作成してソートしておき、それぞれのセットで条件を満たすかどうかを判定し、すべて一致すれば採用、のような方法にした。ただしあまり改善しなかったので最終的には外した。

 

大したアイデアが浮かばず・・。パラメータ調整しようかと思ってたけど上位陣が圧倒的すぎて萎えてしまった

 

結局これが最終提出。絶対スコアは 52,985,874 点。

最終提出

 

やりたかったができなかったアイデア

聞かなくても分かる場合の省略

比較の際、過去の比較を使うことでクエリ回数を消費しなくても結果が分かることがある。一対一比較については最適化できたが、それ以外ではあまりできていない(全く同じクエリを省くのはさすがにやった)。特に過去のクエリを 1 つだけ見て差分から確実に分かる場合ぐらいは実装しても良かったかも。

 

微調整

どういう条件のときにどのパターンを使うかなどの調整をもう少し細かくやっても良かったかも。

 

まとめ・感想

序盤はいいアイデアがあり順位も良かったが、そこから伸びなかったのが心残り。上位陣の方法が気になるところ。

 

 

End

*1:最終的には、 Q \ge N\log_{2}N + 2D\log_{2}D + \displaystyle\frac{N}{2} を条件とした

*2:同点がほかに 1 名いる

(検証)すべての天皇の誕生日を祝日にすると何日休みになるか

この記事は何?

某ツイートで紹介されていた、 125 人の天皇の誕生日が一様独立に決まっている場合に、天皇誕生日の日数の分布と期待値を求める計算を厳密にやります *1

モチベーション

元記事だと何十時間もかかるみたいに書いてあったけど、競技プログラミングをやってる人ならすぐに計算できるよねと思ってたら書いてほしそうなコメントもらったので書いてみます。

問題の定式化(再確認)

M 人の天皇がいて、それぞれ誕生日が N 日の中から一様ランダムに決まっているとき、その誕生日として現れる日 *2 *3 の数を X とする。 X の期待値と分布を求めよ。以下 N=365,\ M=125 とします *4

期待値

期待値だけなら簡単です。 N 日のうちそれぞれが天皇誕生日である確率は 1-(1 - \displaystyle\frac{1}{N})^{M} なので、期待値はこれらの合計の N \big \{ 1-(1 - \displaystyle\frac{1}{N})^{M} \big \} です *5 。元論文でもこの結果に言及はされているが、なぜ「なぜ一致するのかは不明である」のように記載されているかは不明である。

分布

包除原理

一般論

競技プログラミングでよく使われる包除原理を使います。包除原理は、「または」と「かつ」に関する事象の数え方で、例えば「りんごまたはみかんのいずれかを食べた人数=(りんごを食べた人数)+(みかんを食べた人数)ー(どちらも食べた人数)」のような言い換えの一般化です。 詳細は ググって ください。

本問の場合

本問では、天皇誕生日の集合が 特定の x 日である確率は、 x 日それぞれを含む・含まないについての 2^{x} 通りについて包除原理を適用すると、  \displaystyle\sum_{i=0}^{x}\ (-1)^{x-i} * { }_{x} C_i * i^{M} となります。これは階乗・ M 乗計算の前計算を前提に O(x) 回の演算で計算できます。すべての x\ (0\le x \le M) について計算しても、前計算を含め全体で O(M^{2}) 回の演算で計算できるので十分高速です *6天皇誕生日の日数がちょうど x 日である確率はこの _{N} C_x 倍です。

コード例

以下にコード例を示します。 float をそのまま出力しています。次節以降のように桁数を増やす場合は少しいじる必要があります。

# 設定
N = 365
M = 125

# 階乗の前計算
fa = [1]
for i in range(1, 400):
    fa.append(fa[-1] * i)
def C(a, b):
    return fa[a] // (fa[b] * fa[a-b])

# ちょうど a 日になる確率(分母を N^M としたときの分子)
def calc(a):
    s = 0
    for i in range(a + 1):
        s += C(a, i) * i ** M * (-1) ** (a - i)
    return s * C(N, a)

# 出力
for a in range(126):
    print(calc(a) / N ** M)


計算結果

50 桁

小数点以下 50 桁だとこんな感じ。

x 天皇誕生日がちょうど x 日になる確率
 0 0.00000000000000000000000000000000000000000000000000
 1 0.00000000000000000000000000000000000000000000000000
 2 0.00000000000000000000000000000000000000000000000000
 3 0.00000000000000000000000000000000000000000000000000
 4 0.00000000000000000000000000000000000000000000000000
 5 0.00000000000000000000000000000000000000000000000000
 6 0.00000000000000000000000000000000000000000000000000
 7 0.00000000000000000000000000000000000000000000000000
 8 0.00000000000000000000000000000000000000000000000000
 9 0.00000000000000000000000000000000000000000000000000
 10 0.00000000000000000000000000000000000000000000000000
 11 0.00000000000000000000000000000000000000000000000000
 12 0.00000000000000000000000000000000000000000000000000
 13 0.00000000000000000000000000000000000000000000000000
 14 0.00000000000000000000000000000000000000000000000000
 15 0.00000000000000000000000000000000000000000000000000
 16 0.00000000000000000000000000000000000000000000000000
 17 0.00000000000000000000000000000000000000000000000000
 18 0.00000000000000000000000000000000000000000000000000
 19 0.00000000000000000000000000000000000000000000000000
 20 0.00000000000000000000000000000000000000000000000000
 21 0.00000000000000000000000000000000000000000000000000
 22 0.00000000000000000000000000000000000000000000000000
 23 0.00000000000000000000000000000000000000000000000000
 24 0.00000000000000000000000000000000000000000000000000
 25 0.00000000000000000000000000000000000000000000000000
 26 0.00000000000000000000000000000000000000000000000000
 27 0.00000000000000000000000000000000000000000000000000
 28 0.00000000000000000000000000000000000000000000000000
 29 0.00000000000000000000000000000000000000000000000000
 30 0.00000000000000000000000000000000000000000000000000
 31 0.00000000000000000000000000000000000000000000000000
 32 0.00000000000000000000000000000000000000000000000000
 33 0.00000000000000000000000000000000000000000000000000
 34 0.00000000000000000000000000000000000000000000000000
 35 0.00000000000000000000000000000000000000000000000000
 36 0.00000000000000000000000000000000000000000000000000
 37 0.00000000000000000000000000000000000000000000000000
 38 0.00000000000000000000000000000000000000000000000000
 39 0.00000000000000000000000000000000000000000000000000
 40 0.00000000000000000000000000000000000000000000000000
 41 0.00000000000000000000000000000000000000000000000000
 42 0.00000000000000000000000000000000000000000000000000
 43 0.00000000000000000000000000000000000000000000000000
 44 0.00000000000000000000000000000000000000000000000000
 45 0.00000000000000000000000000000000000000000000000000
 46 0.00000000000000000000000000000000000000000000000000
 47 0.00000000000000000000000000000000000000000000000000
 48 0.00000000000000000000000000000000000000000000000000
 49 0.00000000000000000000000000000000000000000000000002
 50 0.00000000000000000000000000000000000000000000000134
 51 0.00000000000000000000000000000000000000000000006693
 52 0.00000000000000000000000000000000000000000000306262
 53 0.00000000000000000000000000000000000000000012842139
 54 0.00000000000000000000000000000000000000000494379309
 55 0.00000000000000000000000000000000000000017502194209
 56 0.00000000000000000000000000000000000000570718561252
 57 0.00000000000000000000000000000000000017167082815289
 58 0.00000000000000000000000000000000000477008279721836
 59 0.00000000000000000000000000000000012259832950976278
 60 0.00000000000000000000000000000000291818717016426426
 61 0.00000000000000000000000000000006440516370891028059
 62 0.00000000000000000000000000000131942927401327094993
 63 0.00000000000000000000000000002511653937388687448285
 64 0.00000000000000000000000000044469776387538696424755
 65 0.00000000000000000000000000732991308273561543702357
 66 0.00000000000000000000000011257291689623893138523000
 67 0.00000000000000000000000161220007763865435317453560
 68 0.00000000000000000000002154664903164695993659167615
 69 0.00000000000000000000026891817244261475422203488208
 70 0.00000000000000000000313633700527307104493418542282
 71 0.00000000000000000003420183120323756116137974734068
 72 0.00000000000000000034893289008969334288321920425770
 73 0.00000000000000000333213544093248978447096467228458
 74 0.00000000000000002979852093334799030327112464497043
 75 0.00000000000000024965624533928166787418173808655934
 76 0.00000000000000196034112910927938213522829423249405
 77 0.00000000000001443144711343104963289514983044243745
 78 0.00000000000009963375232950231520606828788814725799
 79 0.00000000000064525701587182353132682521402204907374
 80 0.00000000000392086426120104166837266178657451209355
 81 0.00000000002235778210222252143317333455830595388718
 82 0.00000000011965481376017370947714846279678754485985
 83 0.00000000060106901466779236286427468565697572358993
 84 0.00000000283420023816929354443087287291147641260248
 85 0.00000001254436864237896912319048798931690429126539
 86 0.00000005211460987261729161495898797964623225033810
 87 0.00000020319945895308885758792252211300357232317833
 88 0.00000074349299816525269305446601008717814951136407
 89 0.00000255234572879600782819920559959990559210008211
 90 0.00000821872643132009821720626558935359032639280244
 91 0.00002481658723822685828330424618389530512789555765
 92 0.00007024200132149853779798579492345382833641555813
 93 0.00018628887710054298059385211219929704455464416797
 94 0.00046270220763230551469101864653151033294357500778
 95 0.00107572093635497549120586830910855861654490562302
 96 0.00233941363839182012697917707428223653520703534874
 97 0.00475569726555764925128173579970433097237877186738
 98 0.00902969454823963197816335569837876688750810305147
 99 0.01599902071684735311707167269883243876640355993412
 100 0.02642645186101604332042834519884242750139250530778
 101 0.04064640242550989770289652193736929845034216059434
 102 0.05814325286431799126232657034359961278047926768255
 103 0.07724378651833554325305570561166857899884926067212
 104 0.09515618079221206518708715200651902284131861935663
 105 0.10850800181092303010377596309864489775066306959617
 106 0.11431119375794554865094384716232284168591430565874
 107 0.11101057076605115750582271234480760463938205728739
 108 0.09913202234371060462882640199823127561617235437090
 109 0.08117497699936696104834682688344617854005686950940
 110 0.06075857131892151487894885425098393647292077777090
 111 0.04141820773548289752531546669140343882987080003057
 112 0.02560690163910682119462958297758573586383229456811
 113 0.01428889412374261269771887506486999998609594767337
 114 0.00715568591178599614354973820344429750419242042710
 115 0.00319446809428659065318361629834197501443248145594
 116 0.00126108348245205674744482240689592370868195395851
 117 0.00043594062314729866778935743971571882449610395656
 118 0.00013036369916699565445819482483698847236557635581
 119 0.00003320417875050856576738331041719815116384696533
 120 0.00000705795325653814827602770302808688067480052230
 121 0.00000121752030830107114964260494891524622157295032
 122 0.00000016366282845126500633221019981420807986083996
 123 0.00000001607545496124308388046859842434113617972278
 124 0.00000000102577721835750199052693495548861040355779
 125 0.00000000003189836253214941673767629990616194932354

厳密解

厳密に求めると書いちゃったので、正確な値も書いてみます。すべて分母が 365^{125} *7 の分数で書けるので、この場合の分子を記載しています。

x 天皇誕生日がちょうど x 日になる確率(分母を 365^{125} としたときの分子)
 0  0
 1  365
 2  2825619704319742765983996896461545285744900
 3  3509994716348150507042675103240652948571556517462176277955866984500
 4  1316124937159785216822500631328254287686971654250669956243568389673863541881013059600
 5  123476963671175483334552216571484646615415141488778394461214784347217134343308323534343322534038760
 6  58531943882068454044031930034365339990180752192232993326267870240037469010696850396372031883401044908759488000
 7  701032330246997252759162556424540208567315319362721867636349953946482825208907071510987257820890021154805466416979264000
 8  556575744990020681749960664906702197015866362357280361670506563093416958280042302287104424619657333752663056434017286928065216000
 9  54703348005851701326356612720175114901147021047216807303220790221099097516209596094540107351047554127473195959745614694177486463526432000
 10  1021276929632060936987154401660736597624992505466975709986765658666075734761741407781934545117584916090489161071910767984169268281882063400000000
 11  4920861240740888065811339632539089628993784845035185858774324004928824835051476807130194571523255247665621631906212497955638554649387953679522477120000
 12  7680097691243441426371287538727792112535208027803494221860461728223251514563298392061843102515130495887833267521262948758657541023723773265874107890039040000
 13  4616415352401098209376811746173695964649515967706261224929825574768278656919066386766140481879807390658515869780796070329765844331382074848082838066907044563840000
 14  1223159737556313930848975676633615900282752125910917666895581861113934599358096226437338564020151363433776036332013647567188105025571939673541901747563754248982528000000
 15  159040280189475064482488830580132129563240564846330593287295854646653555813332020334440430644028671053620442715990815091765327574126158285951375287297382645834930145689600000
 16  11067139885770835423997260330528934551338125800126708518620683659096144359778286491909220709574690121573549030113605618742619654894664373795079158030420439857858719125045248000000
 17  442514359082989367949859852403536188996896500506187893615360842546684020758048014396568373617774221291706159781817593165733305626313542920520152744524303649741780510835480901632000000
 18  10784033254373619988487007274352852019934115308556750301378537158857922619371264592912162601163990489148303136432599157318802136764917460077421938825393155602474631520166769710407680000000
 19  168290631613941616826136938263983475265305463182893864964892408397122596927974644418899048938616097422099183689277421246964089932113828314498649116630188436242358755811638438282171228160000000
 20  1753604495217061663452136928773457948183679810871778802096658955893086667982512600336222210200383273468131936592322473576713797909813232633074204395296762098930528338144983464904776216576000000000
 21  12644665219578091984279811463948251482754744881311063095723095564881650479683698035536805499559173659640012146239578726885689797518035542521471809797209954005279573856424725547857090884413112320000000
 22  65062698546062121635417257684023446522640203773547606017811351273603528819798258355268586350205557052483830134986295458142422364897186854675796235506378977508329806427503577424961232009203856179200000000
 23  245340002755975295439974954248144717703398671084201510237794807296599178956368615483791442957414776413012716802946986424088012048383503316614279478197130407227874783671541265575608259792178744688640000000000
 24  693903086847057005329314649839410769967004692727818658624180828470698100542331661493820947927964465414530732916365451516858976591453814058661935660103605430670013941994657374956990908183522680892411084800000000
 25  1502337880256514217935696912513985834450039447107391074754494463852443967203196224625589934174415308442319196028980652676308809039243771070162546176608771953814883656751960849526408945615746801949156330438656000000
 26  2534982851854328911238474408449303700975331329266649566155026664803934135040829209737815976622663001580873392167501223603038852791773811083145097234852441756354920400352142483135136599949778782228980690989875200000000
 27  3387157550809774325958910959545211089877963594273115593134583965464131443087335192334172475245662400941174249713369684153503797044821720017673207711958673974733478650853505422750907779187283045185552712416139673600000000
 28  3635017932741170722834981252821732604873179866286014158932034647570861308626352293515161756717575215571756238294131949359888619764951384436405982392554079448441507630155750760221234096896847762996189279969637197414400000000
 29  3173193157799125431290641915587918249052591540543725048193125076339143695175747623359269490853466527169325953675925669347671603789708733378673256640166334367450614629442335526976031458570840084889316019473980391345356800000000
 30  2279040511984152093899609543864774148568172926688702015039049033210827154603018259125772455003845678049836197700281006379763473084844530972901472384189206036878900621324832616036700483582733015628423679412068407050240000000000000
 31  1360607269985071562289233524881295451731423097980624369163967241804916111719135100656734435492763244943477300737256678400499446790918656577320372525347165384690100484974821359039352422977177562988126112962379697599096553472000000000
 32  681511853930257847648300101185281594430611249287377868344019546310833599993035863037321441929874489386034460604556609685036570995173275448334765056297856395742317278057293985089471851083591623121669765738425042980855709958144000000000
 33  288825979817585898213335654698423338832203933724964647696493593791635751742167055111354141642387348431299898711562532775936973004731527475356726257690066091059860814984013499417221520298534725838905414738312614852437032518549504000000000
 34  104365261756122085221520329166920075030200834911848572173995306133930711715784247633334780426874463227246528700512153559910281422912074234454337365767613034173419037651485614617264147672503687677827483368859506157689524244919091200000000000
 35  32380061604565281962338270396481383980161014522650325958375541726429549670962734837125841053727709426912443665185949910705660042125765986647320609938829283165892926335762407304099642285274210082962624385919035345314537653592559452160000000000
 36  8681397950123933561466432354506519702152987398010329165930767515542774690855670238515829559220839233559433432526488147128721719690683764116730722368630953145582799933893868149175363921088432482397138816859674958224672168773025750056960000000000
 37  2023259524735050802935446046015115467337986747018546907087197507429721825716146329597523296796333980280579076428834653725100940636503331373643618908193994999136363490547647357097644113419138566599202868467379246365579360861952666543063040000000000
 38  412115377207146949055581145089128286103060179822454877707894809186430235167067098143845817157076954207532021154418750963709451539428111565446004449033581129127282860951134800424127320923304555651270806358270165541056175687833915204671897600000000000
 39  73733284364055326250703432992037234241045739336640460570726001230994479868938185601400965013858274747556549831599436438384917744627529752723308159281248787782014391198608014300493929345239332021776509692306795343375741511885675987524072243200000000000
 40  11641084094791034585858224217595878326406233597245297403583798145394242876298994549600387597190791875038435528202536152850490559273837593637740486947353786065831281711938974076524225982857125633368445352947406913485761888311711414660943052800000000000000
 41  1628798498058402946105215873863811755414474707325226348127978118434241617412753515936797531367893265899281504611440916218008736024224631505348200961241610692115224590044404720299983655585715485551705210287800120105057984560944304717360562962432000000000000
 42  202772931800835117856006601888712992450480214369279261105066016460658045423359307939199992267058932523115193616517345787935547683195606770354665625147594375125993892801591670658116301867358259107989879965652087183008531928176447839919784088043520000000000000
 43  22543635309616964220591641757822014155584960390056445993360630524091514349626332852016786995575817315598958157001567725847911404589093313071291407110063402474390646407418016774954310153363653740889730015423853677104650376530024210403677784401510400000000000000
 44  2245954734867083653129728114646584988523823078033534607034732241968744443882259441854440407191853910910613022666753307621536047892489710148076820134385102497387219253255522949455518320319674689257808817535228323035534142179883787922885788489670983680000000000000
 45  201155388100243210607817799869865039092443102241926889302454064146965222893419287368833975781903915033682905868597561700393174545139268522378143716830033387866513009144011344244550301168637779400229787326639972752808910241297634105955549517030287736832000000000000
 46  16244785150762248306103569432379501668219645229722557676622650064260222532447664191300113147543622506773604398247106342028077119649224846506556404381242649569068886405517383789580365343640556097546382581164872864936311216540611560650005075176262415155200000000000000
 47  1186208648867494784370558243195771121889082181632242078928336626017199262438984561953733732875082401501359023368146060769561007284842209068283046132863365225255801100166521161247796129719540578846714886567703380737579102770511484161530551685525748160921600000000000000
 48  78525053920584083148101697856936935524752984255121762662907126761373775210946821449317710778193419439303638595366899483270348475354366083500263696532463352543506134453630296145709716106115005783259695981529500349426941283543789018265042161005273171781222400000000000000
 49  4724097733175469104601907992779086069586225372532054352679417394604405408402578427828185510477210929074976410139159433481434741651712705652218643473810303299450581902229452742259513103524354311677970709307062017832528543135248374755827544746997660705934540800000000000000
 50  258875007436967670133028729849841235324096669016937445746338891430395926416454065028121317574672665297382973577174210543996703860809318395016607607572734225681952698651378538219491555022616880348080328311687848584582892775228943793674850126482649802342400000000000000000000
 51  12949643477779190872288742261447878880872270463864893277458583437797857069351617635962081748974459496741487560716262132692878648874302203054777514499994761270691484747970558111817426112016437372185546492784212615496690503599611661807583341960637945001416641740800000000000000
 52  592517091949613240520464005225314815536948169060603785549368066732349772525265194275670920709507664037174722107861472568616473023894704739035994931297230614873348490420421835059251063846682996565826798245696859639326632699208567598654166650879919508174027725209600000000000000
 53  24845368000500225137936170007224662980237120842707318738914188197930580316572472227403690961714325832693118455262642689411727313526721051024798506827349362030628558201848902293549566951604388229561979601992690498651099799337881118568970456547864005428023159003545600000000000000
 54  956463372298786435343724680125782458750573017646988683966718902484236302367396248709873591070745646140058829279333250163211457360996268848541433317828680490231740166510529310393814908219160676859136481604015377488929053560642317101730181352761358481532247909335040000000000000000
 55  33861060493435096987424404625285459157435722030627443572885970746848191246865925052230251204042673968140657521536542231876928501018469045457840316459876681678753120725118746070701058085833168139766570015279695170754140116703053219433940040771329534928541454836957184000000000000000
 56  1104155027445871833041519996234997287835106362098400132567739542889705004646519620699651613525485686042927445537722978793596199530420650225714433536185728819826718432924838246605593224167464319809020140300345263030237187443535383739795996871409718963022098243954671616000000000000000
 57  33212728801899179636354874314379704580462462590774461520880747261677621770237282739719329466610393667205117261550883300732381182374031503138479772197053803073487400003167370550534097265727603281071958763182766372807658870187437506848241146168929109430190550506352410624000000000000000
 58  922856072934653226997869130447099945773760583133618950082135665951127828647646434157712090034525794965192519560780568822784817470826650925414682830333870323714377654174807948394072514748274353975237775858398581063917930817855452748176194861751970832783073446215402127360000000000000000
 59  23718794354199754521214255820803700731033222548764591951183666418934996706705891454674118968951131437853754317983622685853242010004959489153691647473970928551353117366551547948191102836674238919066479817600807628118564367252920367308030402058921509461834915043437413662720000000000000000
 60  564574424896046338826250488222020668421199842528602034817980049945465431310867623958281610232459937494425533147335219338417152573300732802953823607343544267774232831386404993729759830284414480314152479638670864064862426219554222372776253690730609252960650574197172469760000000000000000000
 61  12460307081415532844440307221486180796174225735743046128386292446550788476024056967040672309653188928455904561833087985847571450388442764643096316540740769528850671138694936725523903321651878726057062699348056801790368566868101120780688291044479279115438687478758153251717120000000000000000
 62  255266705022597707314697188563284413523091690889417965724442555412847962993634319314660634204838205810943699723189639741433970028697681796797663702727077672842474867705118026333029029787297257432613951274168000692121321508372986301446270312771039726737066223166223453205299200000000000000000
 63  4859234499202080792836372585818223040660819484058515567464449759714747807316299953547392458476796602871302007977919331667929556270423317137429644892374468255778653230370840718880663296750129634990955171776692504280676238347075755812262391336774409833135580013057024079167488000000000000000000
 64  86034572031365623904858980212717564028495295637239506387604626212803479430113521414204135530713039090932660166621219861712234446940494057131075580163344984446148472838355788068531816677727499735313247998931411553644593933298776823374597493443130544017176225770051860955974860800000000000000000
 65  1418100081287974086641459655423054617532038764354909218105881659015781881793387711134840400740224184957203599956293822948333802984415740383398342006796895007777985686710025345099402127747090227248420469548495109166353606992909944320056809422065283298227075849228118543138407055360000000000000000
 66  21779202672591754263926478755216099721943660633857614568931743406342086007469591889729072844535076608529040056618301724367037127629536636192651129464176468686683899122317796762091503889870646673486973447729403269864794275065388344017760805218121669888337029144355567142636093440000000000000000000
 67  311908345344061376966478368039313226014869195139191381132010648065286105353329682008798215367436127548295483091770692966124295077376345181752343911735773842885508712819498327580217970604428399823295447963974491772192871088006770964950058508681905955909924058621615267615206277120000000000000000000
 68  4168576680019564339537714528638003340898242709615125256131037319697620158947463608647147663678675233179470739672358395299028899307847752049751658192860953328401649668305095657921783908451175103678540355522877567221601300706999391994090963812969916818624358710757667745907479674880000000000000000000
 69  52026931001255439214092399620376607183473520715168760549948763371933677748433906604699993528781744856906949615964230555083029360760883791343169800095867221635848580963065454739475680128680531587939396788557742401547721915103162842154298528672854264325437968894555808722621887938560000000000000000000
 70  606779331749498502052151583756626977491187959598739968286852764375717760031323818667570223281462650024456440770774538252156336981312736322444263383076056503824292263455483596190433613428913753151816340730701227676582973436815902467379910514245908763682209293343011014476562432000000000000000000000000
 71  6616943347356493029583640429947002520603812033062309848261163894864258127349876452999059011874689414435546693296466944357634794783667698808951562662969619652166389300295213417227308520840611641645882629811798689412347610242980863760503473648577838682445040426331317484851691729715200000000000000000000
 72  67507179718912597826005390003382275869102590367522822845984885830178910466850221108519765383274612523512578991519609654334592855890168991879392241861660598597562724872252307948681830869522308215189589773554114512433326086208523216312508339036318636336640296375123456809739636598374400000000000000000000
 73  644659968858097479188494521437296687748832989831731364457563533059493438627834830781586318875041495824249942604885698316606282263515219079185134954591306816825855789042247133630239087763884793888465144770422005088226708052465186883958054526285984609345075869367941746017987541231206400000000000000000000
 74  5765045844455120618164723523665944083732575099722511490637236478662597389066405886560664119865948322182203322300600176480163192990305105598183234610621921158190251885518728436464222154555778742506450290591909865366173767030811163529819528645086639726166039848629855415309944907366400000000000000000000000
 75  48300373798914746031584334394594991119677474238407478132631553809004109315926420546449891600602239740902229416621143700482519759077949588088304165096075869674072961974087656055520151818526326985543629875125903375537591049547942271473525775865564795905526138265994369285045739885428736000000000000000000000
 76  379262330011764902286783765902016380185823821839754304406857893312394816990934233477203269893500093911007288801102510611717999950433655494163409135457379950926548324159003184191544668526987274430747943145368160285914809902165368589270585796121502214467764749565204544089297494741509734400000000000000000000
 77  2792016234525633387475275090797829332944957524205933682699774276771976587850592550488868642003074374601813700791421398179162168688704964585209060013147224727548961920429735916740076273395450635736288404406407400506200217399398048725267897239139272696874556055878975968695376451319994777600000000000000000000
 78  19275894636497064134234127977551213885011420002004759182435583410729587486332472931270991631436029608611418161410515353830482389181935090916337509760723743269326033983371334755924633149879547593573009172914285698184022341543833742495894043567376194151689508502699909035593691620268048384000000000000000000000
 79  124836272453856233334994716977419420599727860496564273189325299683655998347333591569672937647080774991303190234856287189823392942231451731997963571180734047731138675242102053216495170273537128460537115038738249828824055705186596489647430020495469774926994150524017444711558231347374850048000000000000000000000
 80  758559871688571449850027990408130060553817307869545692116133091129792536975416376855277245339810404077154504553022087664245917602398118554011163263693391874303458395731372557431918429960782282964736267981095895664335109439903778126085970371760650967939209448947414702739746338497363968000000000000000000000000
 81  4325504580846632999956860751361644713210585529040626462855925327179055188542351589786260479978030526791511786209872762766426771679768312898682004200453100189121116564276053030129062980355885198127056992031442834452420651526932418367707232248716253698212145315916751848317972609191559299072000000000000000000000
 82  23149319671942426558391821061409343540489882744693269432865336904409980406846131981755528048817026920605613023416248307765605691886225418370003993973092134838741123478155264735754535827866369472114565584573451847250250710839981747361214199756431352922403657983321450766513673538299358085120000000000000000000000
 83  116287329595723040197925677170802610320186218706944132361371378957767769732951428976124094435023033310880877891342218759663943395761994405610994473477585466151216133322957524385678153557832086834684653508126058255173674938938190198633595787923570574259609329109004979877277876691089437491200000000000000000000000
 84  548325681732949347954734384848909396833710568559380890335652949365383618699261047755765187843986331373726202839492667522347969476187223918448494570205060551376613864855518737172542869904443192329765221313681278081727999189880147564650612675193722477234051164813540063694157322629626388807680000000000000000000000
 85  2426927849030480994492992057146521359268502672280615394466242910837093987435112196967518080418666292796416605262581193632544440824338355036684773773390230858024196602836452528083179736272614152160786883559505910479826906474499469176638992399857369641073112537849305403649451852711818747183104000000000000000000000
 86  10082484152604417896931838550897600531767219699840757857045045921025716861491602679150327378906273483177510128137385368855230259389162758529494245831696602883313213867841723211034273061585719400349770286032428418432643199486195195854967377509634397590687679933734513559644570438268926663065600000000000000000000000
 87  39312494705804041452368770663373695428683893401920387604085787684674694254363809903143983170425025251834368345621911041360753928407630410067945468342646634962085846914319685879343638718462882442771482726985527068161190607223675889445777165778590118905484639370852682861490441761125168893132800000000000000000000000
 88  143841743992643459439535093329490588292277494436811795261746178942036300230302285118988576386560747118037461287723921216331741876034421104254948240453183887479624700506315346499968235288960484768164306502659624781847952506661484867412061255982986737803688601001094465645206520990621379015475200000000000000000000000
 89  493795989751326796276979420841015880452427709465244771113277135586511829416426714426511545531343979109162886826808967770134533519124344969865200404360675248849520789551705233544314115179552788526778301584005239281201976869680984479215160354456626414306502722927209618440274361197080688879206400000000000000000000000
 90  1590056592593164705811850016967354901313781276676025034466773279594750338405030979037613823942026390276317848312754347306666630584408735753714259332740445539567717616463248165146466156253961697520799676549325886839303156380032030706357088430172098587664510101856344987767173822398028840960000000000000000000000000000
 91  4801203504405725046943093557125282315289731595750366471832718101980439886059663519888042925848353860203754514866519017156916066290145873101240515123965735138210316985659510042599426720865093896091884959375370073836626410795510269677084709325187173893000664390548578587112803448518656844103680000000000000000000000000
 92  13589545559341242427510881438230836465469316073825873285418939224032436360537641707119537797118030978989695287785021090795962103765905306630006681129548217931332836846574798074712849795987980182364631715697770055227064497360256785162980318244952603519959658248407513723070944613222397520117760000000000000000000000000
 93  36040846429891296787602380787785718566667546186766828615340138468526834506892658876073509317590555632427434817334246174589423503862364467885018681643284677501314909426193293086951339789874011590794736032481554721472345647108593753754440233297382897173079644569086064523423739644275414804725760000000000000000000000000
 94  89517847053462073242131098440373492117508734475353444036000282235911262678418679759629226164824572112303572421647862993752444787300050931493842845980353917395246505311631240178590633303358894206260698160109854931089860331635110409642889698292747896454222339747144267286806798480256643629056000000000000000000000000000
 95  208117058151914416149074922230744225910453836046913798698672382663049531137120725576721513999443615390883217615765428183420945146345764671280026918872435447513771977025192261233268442660736467684333925638863151060994148792459565217542597009682577579097656153074958199616962267867793806747238400000000000000000000000000
 96  452600547008327456783125647525719123670627091630372041099674738251056462154818406197868292097495879374573996914919741916771054071568199290465488258074462639176679191111060900422759337631059972516320068608280701798791656636662464978525225848352292107353893666812919338741247761445880588979404800000000000000000000000000
 97  920072939848740027946770542904126432299672191200088014114135980186996835267583528715505643078694951293238029592370433923001167089328857364801336291315823644837919521470682155323430216056549616085779058534547911949658685417676599126748258879888493194678848777421557888528740812714360544899891200000000000000000000000000
 98  1746952580246041349995802964560675263995545196405807335419558743084776824108244810994558757705967827328120610839115688215422654318058683439450791171279882196008154472498581574111358042488037105114973926528245626514819325944225642972717965451130791264631276012587526466566840126885823825051648000000000000000000000000000
 99  3095290806725594566680888283951173238602202302746415515688616696917334554615458132299252382883978920870237792357017613081637743950548698009979030228341739273753308005727460032963328928835531919768425348678934726624559369101352941191646742201808242082353088201283878525477573497499517626351616000000000000000000000000000
 100  5112660015099839826653069265370778919513870162208554832714775251976002998637808604829908646937203551132317714446793545193901303914430033574146738682255308371957765177996856127943086075735675520107686244270377871768092820878562341026641140763084207321427046038408910914473189957217959280640000000000000000000000000000000
 101  7863758537525123526327965596444649635298115586625707761520651483838717132952195245143240588052619527013116187568167076844927660482473394923551978520147793465978910366382283767739226995058494737844309240955975807175090289649088617510220262793933568485356133200357845721435069279517914396675276800000000000000000000000000
 102  11248830740904788537211902860756197872664796459504086536505369005831016206365596720472853820618216100673971725165626245059813957071916821974449110345335371790917576222184417143215101784358887154903477069780450419982885019330095791872810543048974710128577734452437948845913379546855892391559168000000000000000000000000000
 103  14944163553404792384466273133094588830019112301917829334006295972864294882370910945068179907517121058158196816200430201549929485419166641200128479402665156576475735679274424688019273350927015029597256727888628571347166279042286528675185687430763188254480901660515240296726655925911931416739840000000000000000000000000000
 104  18409629990609304751907039584345953847854775989051697307644996707056561243639363078401285371772034710078708213687108450193009115773753870621288769992790247885726938509314059448249117135966984282258608109851730325657871397172701837632878956345675067755180249131373356353143794103947728751951872000000000000000000000000000
 105  20992773645692048607297239400981921294471991337052923750430897741778192685868970560352561327909791256119582575348392491342934371842201799865227577256591519007136678077687453434187741011999895633336753814363999787158536509124726408294641187721516317654333082174037205073663510016248618144707379200000000000000000000000000
 106  22115502780255127902229996016813253807925179288430674387925687953842540967126326047871751106093686255994195637157552901821656509559430034508670526050287626933911471704531622490444582728002590605232736743247384934971027096363835573641491076894653006000793216237788310030116172898941713891983360000000000000000000000000000
 107  21476939446655607428125209809740500364509851187955072486606443704941793838586998597112275166956632024210018242223075306360263291386172902875325000249081363449713627489956361418555650650567099771342474441893909567343742838421050592985744273338443322694132483353481696227415159124371525683118080000000000000000000000000000
 108  19178826182123209964208807289510222331148827777046348617578961678919529501915013412171760081363712442703383442296426394300941379647214648924395306134560024681647549292844818178929926080536362591301191507210882516914062328996800480247438004419201322631682015531023940090276806896019662459371520000000000000000000000000000
 109  15704721213200202980570225584719072705782821808485819390588736036587152251847511267194472053045541435955410765097076305902311172378429906892305363001377158210713987913846774505612734560851645743630466835043596686338930760067925137254003688227948770289298770824504419766801955223619205374935040000000000000000000000000000
 110  11754809907534010174286930449499674110133534455885769775305294092514839402753630056989932409571968390408461522579757459736629115226549349085008034455958511153993880464435333068032863818714999164495340291743715119738915720728401382049019071867643044571422536446893634555637451344151629004800000000000000000000000000000000
 111  8013077794173487632394233623643575348944652207986433951544205175432488136447194607755356404245944071209170552125187165250740914683720599598320743927631834464375393884709671745553428683217208822820997645047748371525218301001488663964134983482494737578482524556119302160405304386070306514534400000000000000000000000000000
 112  4954103668907083075768054391771921337567147891834191239766336237228906064914247560014924834747598525830188114908135285038106535478911197520010287225435918157522730418078463838173817143458330986446480735717761708373333307868708241296680763931953262656749049953602360265160467777921330498764800000000000000000000000000000
 113  2764436861621313819298360518948613286672758338281180801071632235723317066721210875535456008790298363916798491321022030194104344607701676250106942365211631448823800659544129524825313694172817617197161795790459750962328333984622475586959317688396125962492132322345588917749673431040640470220800000000000000000000000000000
 114  1384392783193517191334156314193785403839584147575012866217175852589908437674090708135460813310405091190820460410659308147689260092217691250489375471362692819876443658465920631647993305390746129120916826877910410081708721931659856994495352890518847307068664499532054510534995580370561269760000000000000000000000000000000
 115  618025809180396574385861433449725861035317062707571654812009283801089813393382413961371864163857054123844894608506854084802065060030109092985771604356401542524059536256615951861717074330360004207323686312429820930656667889716893171597887213188376992984987546811404020162238625063530135552000000000000000000000000000000
 116  243978689622981347354319725319047337892489064004273858510650429183387013022108861412340956300167123952902739216545551538172019078686025834340201698792090478040430664208967829533292178635966499735125195673424576086388731102004117437936433681657851321244564159622778307483277415942612582400000000000000000000000000000000
 117  84340349761854414204259011190222033744597936118852152984140663531199099745718155259542718256393933812124048240391620277447431954827899135150004376738814445436898213001155720854803942074115265192151981560164886665319170981464018963941769293039745116959125341563210668292717684270406041600000000000000000000000000000000
 118  25221141137559327548993827572371696272386932103519196254009143968429333136839532468818739589248800832867617885190139416911539523259531702591205484359253010599704203088256502437850234759291272468748205817049995592564250879830632806614496014724986679286488460391306604321150944761872384000000000000000000000000000000000
 119  6423930004859377795872220648003711956011234800168704911830578274654216205922494125956568610573324404654221832836806369341400204206104936756472212602000435108112539113699359278703625290824300825902305185382269164870466309273146331912500106859604504539784424905755446105982554559479808000000000000000000000000000000000
 120  1365484689088295232273793288074815944594211592532893434068706914779935728835703636877650849035045422638882608160340821668185414216778561143481650030837732075706405228032067606007541090743814866775052856720995775841751314951289620620872944150349272665844023920131316474900804649615360000000000000000000000000000000000
 121  235550630503129012198378749801167450823604064563607476283762192424958449838843510353163470495183344760854356910968290636684052220939584263240958971509216494502867030076440176026830430189064219254581037252242464894210162242352937922208225683633175502047998265698377360945974823878656000000000000000000000000000000000
 122  31663440986388840728372406274013259887291762511404669840303189935449930256469909537269886768696603619161455672477736444930386721877128026732451490162418226453340357229891025762988075457652096702301828254882816450546972665009597549623262863172336454256754031179685320739398625525760000000000000000000000000000000000
 123  3110078350174925297518110841014995309489758596452559812513966880019908134406575693761769084031427463330303375384789563697680567296548682039222249330325818022976417649923093195891324196438910790333000546662770986762320549715646982394613262921962111988237224174117792432403356057600000000000000000000000000000000000
 124  198454571059283301779665873045650326933822433840875273468261037564882733955541547235424685124747645649553966207809907558296294604024991708237780972429491881756174837516516428056875532112911380688354945891203844112453941471637856226630562854875367462400371325019513716187636695040000000000000000000000000000000000
 125  6171296983908035577922512955355061779490478265245282697529149684275708243004582307579012789040539690521613658849314544716052516073551355056168414755549360452030727205352317311188000417962792612373360252874855023367922567053512690402318148132253362379159934107058426529189734645760000000000000000000000000000000

期待値は約 105.965408586231405593934205706662260751965897939*8 です。

実行時間

Python で雑に実装して手元で実行すると 0.01 秒程度でした *9 。計算時間に関しては元記事もネタっぽいし、リプにもネタっぽいのがいくつかありますね。もしネタじゃなければ競技プログラミングをやれば計算量の把握や高速化が上手になるかもしれません。

まとめ

M=125 人の天皇の誕生日が N=365 日の中から一様かつ独立に選ばれる場合、天皇誕生日として現れる日の日数の期待値は N \big \{ 1-(1 - \displaystyle\frac{1}{N})^{M} \big \} \risingdotseq 105.9654 であることが期待値の線形性から分かる。天皇誕生日の日数がちょうど x 日(x=0,1,\cdots,M)である確率は上の表のとおりである。包除原理を使うと必要な演算回数は O(M^{2}) 回なので雑に実装しても一瞬で計算できる。

追記

もっと速くなるっぽいです

*1:元論文

*2:複数の天皇が同じ誕生日であっても 1 回しか数えない

*3:天皇誕生日と呼ぶ

*4:元の論文に合わせてうるう年は考慮しません

*5:期待値の線形性

*6:O(M^{2}) 時間」と書いていないのは、必要な桁数によっては計算量が変わる可能性があるからです。分母が N^{M} なので愚直に分母・分子を全部持っても O(M\log N) 桁程度なのでそれでも十分高速です。

*7: つまり  193467516637826401287204282638777796402688771379556919280960716666436329486857003133713264939685701792987543567298529410176952152155205156322699366298883013060129569255273307828859761101183838425025060481649298163653070757247047877869025080268759994493278082912126625261637293440482310291628209597547538578510284423828125

*8: 正確には  \displaystyle\frac{20500864448690797060931150186184870216381296397754153967073899862132947733564210189850981922246796493476167240911883967961492788355735440509594330405514329609960056962928170855467471498061974014521953683029491459589382894889749926123099167806930943459680225420916140260807824695676646761910258039961300725974511716860987865}{193467516637826401287204282638777796402688771379556919280960716666436329486857003133713264939685701792987543567298529410176952152155205156322699366298883013060129569255273307828859761101183838425025060481649298163653070757247047877869025080268759994493278082912126625261637293440482310291628209597547538578510284423828125}

*9:高速化しようと思う以前の計算量だったので特に高速化してません