2023-10-22

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$ つ。移動・スワップした方が良いかどうかは $2$ ～ $3$ 回のクエリで確認できる。

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$ つ移動のみ実装して投げてみた。

正の得点を得ました#AHC025 pic.twitter.com/xr1e4448J1
— きり (@kiri8128) October 14, 2023

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

第 2 提出

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

うぬ？！#AHC025 pic.twitter.com/fgEyGtz2BR
— きり (@kiri8128) October 14, 2023

絶対スコア $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 y$ と $y\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$ 点同士も含む）すべての比較結果について、現在の推定値による結果で矛盾が生じたときに、比較したグループの結果を調整する。
更新前のグループ $L$ と $R$ の重さの和の比率が $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$ 位だったので一応上がっている。

上位勢についていきたい pic.twitter.com/vknaMDzdMV
— きり (@kiri8128) October 15, 2023

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

バグ修正

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

6 位まで戻した pic.twitter.com/Ogd1Plqlhy
— きり (@kiri8128) October 15, 2023

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

3 日目

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

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

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

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

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

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

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

深い探索 1 （貪欲方式）

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

いろいろやると $1$ 位に！

1 位！！#AHC025 pic.twitter.com/91UoqvKOEi
— きり (@kiri8128) October 16, 2023

4 日目

深い探索 2 （二分探索方式）

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

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

いくつか考察

$S$ が $A$ と $B$ の両方の要素を含むとき、最後に調整できないと思うかもしれないが、最初 $S\cap A$ 部分は含めず $S\cap B$ 部分はすべて含めておくことで、 $A$ 側の追加、 $B$ 側の削除が同じ方向になるようにできる。
$2^k$ 個の要素は互いに比較ができる（ $1$ 組の比較は $1$ 回のクエリでできる）。共通部分があればそれらを双方から除いて比較すればよい。
個別要素がソートされている前提では、 $2^k$ 個の要素のソートは実はクエリ回数はそんなにかからない。
例えば $k=3$ （ $2^3=8$ 要素）のとき $1$ 回、 $k=4$ （ $2^k=16$ 要素）のとき $4$ 回以下のクエリでできる。 $k=5$ （ $2^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_3$ と $w_4$ を比較すればよい。

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

とを比較する
- のとき、とを比較する
  - のとき、とを比較する
    - のとき、とを比較する
      - $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_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_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_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_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_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_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$ 点。

プレテスト終了時点 pic.twitter.com/mXWwNEvF92
— きり (@kiri8128) October 22, 2023

最終提出

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

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

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

微調整

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

まとめ・感想

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

End

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

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

2023-04-26

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

この記事は何？

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

ワロタhttps://t.co/kEyQOTwjLI pic.twitter.com/5IwrSro7sx
— 鴨川を徘徊する魔女 (@Kamohai_) April 22, 2023

モチベーション

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

ブログで高速な解法書きましょう
— ねぼこ (@nebocco27) April 24, 2023

問題の定式化（再確認）

$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 。計算時間に関しては元記事もネタっぽいし、リプにもネタっぽいのがいくつかありますね。もしネタじゃなければ競技プログラミングをやれば計算量の把握や高速化が上手になるかもしれません。

これ Python のせいにされてるの何回見てもじわる https://t.co/CUa47KCD92
— きり (@kiri8128) April 25, 2023

まとめ

$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})$ 回なので雑に実装しても一瞬で計算できる。

追記

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

https://t.co/g1WJJg64Z2
— 熨斗袋 (@noshi91) April 25, 2023

*1:元論文

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

*3:天皇誕生日と呼ぶ

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

*5:期待値の線形性

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

*7: つまり $193467516637826401287204282638777796402688771379556919280960716666436329486857003133713264939685701792987543567298529410176952152155205156322699366298883013060129569255273307828859761101183838425025060481649298163653070757247047877869025080268759994493278082912126625261637293440482310291628209597547538578510284423828125$

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

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

2023-02-26

AHC 018

AHC 018 に関する考察・日記です。

Pretest 40.4B で暫定 13 位です。

（Seed 0 の結果）

動画は一番下のツイートリンクを参照 *1

問題ページ

戦略概要

ざっくり言うとこんな感じです。最後にもう少し正確に書きます。

10 マス刻みで 20 × 20 のグリッド（格子点を基地と呼ぶ）を考え、このグリッド上で最小全域木を求めるようなことをする
各基地の評価を「次の攻撃でそこが破壊された場合に、その基地を通って 2 つの連結成分を結ぶために必要な期待コストの最小値」とし、評価が小さいものを優先に攻撃する
ただし期待コストは「移動距離 × 両端の基地を破壊するのにかかったコストの平均」としている *2
結んだあとは、追加点ありのクラスカル法に帰着できる。追加点は貪欲に選ぶ
基地間を結ぶのは、左右の高さが同じなら真ん中から、そうでなければ低い方から順に試す

1 日目～ 2 日目

考察

ビジュアライザを見る感じだと、高い山 *3 が途中にあることがあるので避けるのが大事
山の大きさや尾根の幅は 20 程度のものが多い
つまり幅 10～20 刻みぐらいで山の高さを調べておくとある程度の地形が分かるはず

高さの調べ方

高さを厳密に調べようとすると 1 ずつ壊していく必要があるが、これは効率が悪い。固定コスト（問題文中の $C$ ）の数倍ぐらいが目安になるか。
1 点の高さを完全に調べる必要はなく、ある程度高いと分かったら *4 別の場所を調べる方が良い。
例えば、「幅 20 刻みで格子状に $10 \times 10=100$ 個の点（基地と呼ぶことにします）を選ぶ → 高さを 100 刻みぐらいで低い方から調べる → 全部が連結になったら終了 → 格子点の間の移動コストを、両端の高さの和半として、最小全域木の容量で結ぶ」のような解法がありそう
低い道で行けない場所はもう少し細かくしていく（幅 20 → 10 → 5 みたいに順にせばめる）方法もあるが実装むずそう。
ただし端っこの方など、明らかに使いそうにない場所も高さを調べるのは無駄なのでうまく省きたい
省く方法は、孤立成分から水源または別の家に近付く方向に進めたいが（間に山があって）遠回りするのが良い可能性もあるので難しい。簡便に、孤立成分の隣接する箇所をすべて調べる手もあるかも。
高さを少しずつ上げていくとき、早めに全部が連結になれば嬉しいけど、例えば水源や家自体が高い場所にあるときなどはどうしようもなさそう。
あと水源や家が基地と一致するわけではないので、最寄りの基地まで結ぶ必要がある。これは水源・家から候補の 4 点を結ぶ辺を張っておけば良さそう（実装めんどそう）

はじめての提出

まずは（上の考察はいったん置いといて）適当な水源に縦→横でつないでみよう → 9.1B で 362 位 *5

#AHC018

参加することに意義がある pic.twitter.com/q1zQiGdiia
— きり (@kiri8128) February 19, 2023

連結の管理

各家について、最も近い水源または（まだ連結でない）家に向かって縦→横でつないでみよう → 18.2B で 78 位。

ちなみに Perlin Noise について調べようと思ったけどよくわからなかったので特に性質は使ってません。ランダム生成もできなかったので、 Seed 0～999 までダウンロードして直接読み込みました。

3 日目（2/20）

考察（アドホック）

でも格子状のやつなんかはだれでも思いつきそうだし、上位に入るにはもう少し奇抜な方法を取らないと・・・
格子状じゃなくて基地をアドホックに作れるようにできれば柔軟になりそう。幅を 20 → 10 → 5 みたいにせばめるやつのさらに柔軟バージョン。
その場合全部の基地の間に辺を張るとたいへんなことになるので、ある程度近くで、途中付近にほかの基地がないものに限れば良さそう。「途中付近」の判定は、角度が○○度（例えば 150 度とか 165 度とか）以上みたいにすればできそう。 *6

考察（シャボン膜問題）

もうひとつ考慮するべきことがあって、実はよく考えると最小全域木がそのままでは使えない点。つまりシャボン膜の最小化みたいなことを考えないといけない *7
水源・家については、水源同士を長さゼロの道で結んでおいて、基地のうちいくつかを好きに含めたときの最小全域木でいけそう。基地の選び方は焼きなましとかでできるのかな。あるいは貪欲に「その時点で追加した方が良い基地は追加する」でもそれなりにはなるかも。

戦略（案）

たとえばこんな戦略はどうか *8 。

掘るパワーは、マスごとに徐々に大きくする方式にする *9 。破壊されたマスの「コスト」は、 1 ステップごとに攻撃した場合の破壊までにかかるコストとする。
幅 20 ごとの格子点を基地とする。
水源・家・基地を頂点とする重み付きグラフ G を作成する
水源・基地がある地点は破壊できるまでする（何ステップで破壊できたかは記録する）
その最寄りの 4 点も破壊。水源→最寄りの 4 点には、重みが「長さ × 両端のコストの平均」である辺を張る
ステップ数 $i$ を増やしながら次を行う
G の連結成分のうち家を含み水源を含まないもの Z すべてについて次を行う
Z に属する基地の隣接基地でまだ破壊されていないところをステップ $i$ まで攻撃する。破壊されたらその頂点と隣接基地に辺を張る。重みは頂点のコストの平均。
すべての家がその連結成分内に水源を含むようになったらループを抜ける
基地の数を $B$ とすると、 $W + K + B$ 頂点の変則最小全域木 *10 になる。選ぶ頂点の集合を焼きなましで決める。
最小全域木を貪欲に結ぶ

頑張って実装するとだいぶ改善してそう。出してみると全ケース WA 。。

4 日目（2/21）

一か所間違いを見つけて修正すると 4 ケース WA 。でも相対順位には反映されるらしくて 20.5B ぐらい。

ループのところ、ステップ数を一回増やしたら戻さないようにしていたので、山を越えて平地に出た時もやまの高さで掘っていることに気付いた。

掘るパワーは、マスごとに徐々に大きくする方式にする *11 。破壊されたマスの「コスト」は、 1 ステップごとに攻撃した場合の破壊までにかかるコストとする。
幅 20 ごとの格子点を基地とする。
水源・家・基地を頂点とする重み付きグラフ G を作成する
水源・基地がある地点は破壊できるまでする（何ステップで破壊できたかは記録する）
その最寄りの 4 点も破壊。水源→最寄りの 4 点には、重みが「長さ × 両端のコストの平均」である辺を張る
ステップ数上限 step_limit を増やしながら次を行う
G の連結成分のうち家を含み水源を含まないもの Z すべてについて次を行う
Z に属する基地の隣接基地でまだ破壊されていないところをステップ step_limit まで攻撃する。破壊されたらその頂点と隣接基地に辺を張る。重みは頂点のコストの平均。
破壊したらステップ数を $1$ に戻して続行
すべての家がその連結成分内に水源を含むようになったらループを抜ける
基地の数を $B$ とすると、 $W + K + B$ 頂点の変則最小全域木 *12 になる。選ぶ頂点の集合を焼きなましで決める。
最小全域木を貪欲に結ぶ

変則最小全域木は追加頂点なしで雑に実装。あとついでに幅を 10 にした方が良さそうだったのでして出してみた。なぜか WA は増えた（6 WA）けど 26.5G で 43 位。

#AHC018

50 位入れた pic.twitter.com/xZaOcpGwb1
— きり (@kiri8128) February 21, 2023

あとやるべきことは追加頂点ありバージョンと、有効頂点を優先的に追加する方式。

行きたい方向優先評価

未完成連結成分（A とする）から、行きたい連結成分（B とする）に対して、「近付く」マスを優先的に埋めたいです。

A の頂点 v1 から v1 の隣接未開拓マス v2 に掘り進むアクションの評価を、 B および B の頂点 v3 をすべて動かすときの次の値の最小値とします（小さいほど優先度が高い）。

v2 があと一回で掘れたとしたとき、（途中ですでに開拓されたマスを通らずに） v1 → v2 → v3 と進むときのコスト

ただし、v2 から v3 へ進むコストは「（v2 の発掘コストと v3 の発掘コストの和半） × （v2 から v3 への距離）」とします。 v1 から v2 へ進むコストも同様です。

例えば、下記は Seed 1 の途中ですが、右上の 2 つが近いので、近付く方向に進んでいます。左下の家は、ふたつの水源に近いですが、高い山を通らなくて良い右側を優先的に目指しています。

ここまで頑張って実装すると 32.7B で 23 位。

#AHC018
ちょい伸び pic.twitter.com/KA0OvVZmLA
— きり (@kiri8128) February 21, 2023

手元実行の評価について

相対評価スコアなので、テストケースごとのの単純平均を取るとコストが大きいケースを重く評価してしまいます。そこでコストの対数を取ってその合計で評価しました *13 。

対数を使うことは、自分のコストと最高点プレイヤーのコストがほぼ比例すると想定すれば妥当性があります。本問ではケースによって比率が大きく変わることはなさそうなので、指標として十分機能しそうです *14 。

私の場合は、絶対スコア（コスト）を $score$ として、 $\log_2 score - 16$ を指標として使っていました *15 。ただしスコアはケースのパラメータによる影響が大きいので、同じケースで比較しました *16 *17 。例えば最初の 10 ケースで $-0.052$ 、最初の 100 ケースで $0.220$ のようにメモっておいて、そこからどれぐらい変動したかで変更の効果を図ります。

5 日目（2/22）

その後相対スコアは上がったりしたけど 23 位からは上がらず（むしろ放っておくとどんどん下がる）。

ひとつの懸念は現状の方法だと計算量が悪すぎて TLE が危ない *18 。 $C$ が小さいときは小刻みに攻撃するのが無駄が少ないんだけど、 TLE とトレードオフになるのがちょっと困るところ。時間計測しながらどれぐらい刻むかを決める方法もありそうだけど、いいロジックが思いつかない。

手元環境

ここで時間計測と AtCoder のコードテストでの実行環境を導入

まったく同じコードで複数環境での動作をしたい（パラメタ書き換えミスによるペナがもったいないので）ので、それ用にコードを書き換える。

モードの種類は次の通り

手元実行（1 回）
手元実行（複数ケースのループ）
Submission 用
コードテスト用

1. と 2. は実行後にパラメタを与える方式にしている *19 。手元環境課どうかの判定は、 LOCAL という変数を事前に初期化しておく方法にしている *20 。

1. の場合はデバッグ情報や Visualizer に渡す情報を吐き出す *21 。

3. は本番。 4. は時間計測用に AtCoder 環境で流すためのもの。

3. と 4. は 1 行目の入力で判定する *22

時間軽減策

現状では次に攻撃する対象を選ぶ際に

g in G

v in g

next_v in neighvour(g)

dijkstra()

で、攻撃する場所とコストを所持し、 priority queue でコストが低いものから攻撃している。さらに破壊が発生したらコストをすべて再計算している *23 *24 。

この計算量は、基地（水源・家含む）の数を $B$ として $B^2 \log B$ 程度。さらに破壊による更新が最大で $B \times \mathrm{maxstep}$ オーダーで必要になるが、 $\mathrm{max step}$ は $C=1$ のとき $250$ 程度なのでそこそこ重い。

そこで破壊が発生しても、コストがあまり変わらない場合は更新せず続けることにした。具体的には、直近の更新から採用された攻撃のコストの最小値を $cost_{min}$ として、 $cost$ が $cost_{min} * (1 + \alpha)$ 以下の場合は攻撃を続けることにした。 $\alpha$ はとりあえず $0.05$ にしておいた。

すると実行時間が短くなり、なぜか得点も伸びた！？

再提出すると 20 位に！

#AHC018

うおおおお！！（1 枚目に入れた！の意） pic.twitter.com/IUhGL2rxBp
— きり (@kiri8128) February 22, 2023

6 日目（2/23）

新しくグループが結合したらさすがに再計算した方が良い気がしたので実装

→ 手元でも提出でも悪くなったので却下 *25

パラメータ調整もやろうとしたけどあんまり良くならないので却下 *26

あとパラメータ調整以外でできそうなことは、「なかなか破壊できないときは、周辺の基地を増やして細かく探索する」ぐらいしか思いつかない。ただこれは基地が固定でなくなることによって実装やロジックがめんどくさくなりそうなので今のところ敬遠している。そもそも高い山に囲まれた家がある場合などは、やみくもにたくさん探すより一点集中で突っ切る方がコストが低いこともあるし。

水源が 1 つだけの場合、結局 $1+K$ 個の水源と家を結ぶゲームなので、水源と家の関係は対等になる。現状、家側からしか探索してないので、 $W=1$ の場合は水源側からも探索を進めることにした。しかし点数はほぼ変わらず *27 。。

その後 Web 版ビジュアライザを眺めまくってると極端に無駄な動きをしているケースがあった。調べるとバグがあったので修正 *28 。

7 日目（2/24）

そろそろやることがなくなってきた。

最後の結ぶところの効率化

道を決めたあと、基地間を結ぶときの攻撃力をより細かいステップでやると良さそうなのでやってみた。

具体的には、次のようにしました。

① 両端の基地が同じステップまで掘っているとき

真ん中を少しずつ掘る
破壊できた強さで両側に広げていく
破壊できないときは一段階上げて伸ばす（一旦強くしたら戻さない）

② 両端の基地のステップに差があるとき

低い基地に近い方から、まずは低い方の基地を破壊した強さで掘る
破壊できないときは一段階上げてもう片方に伸ばす（一旦強くしたら戻さない）

「一段階」は、① では最後の攻撃の強さ、② ではふたつの基地の高さの差を $h$ 、基地間のマンハッタン距離を $k$ として $\sqrt{\displaystyle\frac{2hC}{k}}$ 程度にしています *29 。

図で表すと次のような感じです。左右の黒部分は高さがこれ以上であることが確定していて、灰色部分のどこかが真の高さであることを示します *30 。黄色が真の高さ、数字は攻撃する強さと順番です。

提出すると 38.6B で 13 位。その後順位変わらず 39.2B までいけた。

#AHC018
39B pic.twitter.com/34Yil4sHgr
— きり (@kiri8128) February 24, 2023

ところでこれ出したときに上位スコアチェックしてみたけど、自分のジャッジが終わる直前（数秒前）と直後（数秒後）で上位陣の得点が動いてて嬉しいね。ほぼ一律 0.02% 程度ずつぐらい下がってるので、きっとどれかのケースで私の結果が私以外の最上位の人を 1% ぐらい上回っているはず *31 。

（ジャッジ確定直前）

（ジャッジ確定直後）

その後バグを見つけて再送信 → 10 位！？

#AHC018

10 位！！！ pic.twitter.com/q8rhgrRgGZ
— きり (@kiri8128) February 24, 2023

通らなくて良い経路

連結成分 G の隣接基地を攻撃するときの評価を計算するとき、 G 内を通らないとしてよかったですが、 G の隣接マスも通らないとして良い場合があります。より正確には 1 ステップで破壊できたマスの隣接部分（下のピンク）は通らないとして良いです *32 。これにより、遠ざかる側を無駄に掘るコストを減らせます。費用対効果を考えて（1 ステップだけじゃなく） 3 ステップ以下のマスの隣接マスは通らないことにしました。

破壊時のリスト差分更新

マスを破壊したときに、そのマスから出る道が最善であることがわりとあるので、ここからスタートする分を入れると良さげ。 → 入れたら 41.1B で 6 位まで来た。

#AHC018

6 位？？？！！！ pic.twitter.com/CmDHOAhOhT
— きり (@kiri8128) February 24, 2023

8 日目（2/25）

保育園イベント *33 → ゆるふわオンサイト → ARC （爆死）

9 日目（2/26）

高い水源

家があるマスは全部破壊する必要がありますが、水源は必ずしも破壊する必要はありません。特に、水源のうちひとつが高い場所にある場合は、その水源を全部掘るコストが高くついてしまう可能性があります *34 。水源自体も Priority Queue に入れて、順番が来たら攻撃することにしました *35 。

2 基地間の平均の高さ

特に距離が長い場合、高い山がずっと続いている可能性は低いので、単純平均だと若干高めに評価してしまっている可能性がある。高さが指数関数になっていると思ってその積分を使うと点数が少し良かったので採用した。

具体的には、高さ $a$ と高さ $b$ の 2 地点が距離 $d$ だけ離れているとすると、単純平均だと $\displaystyle\frac{a+b}{2} d$ になるが、この方法だと $\displaystyle\frac{b-a}{\log b - \log a}d$ になる。

最終提出

ちょっと早いけど誤提出も怖いのでいったんこれで完成にします *36 ！

#AHC018
若干下がっちゃったけどやむなし。勝負です！！ pic.twitter.com/0ytmEhV0EI
— きり (@kiri8128) February 26, 2023

AHC に取り組むにあたって

いつもそうだけど、いきなり実装に入ると混乱しますね。

まずはやりたいことを明文化して、やりたいことが言語可できたら実装に移るのが個人的にはやりやすいです。

今回はこのブログの下書きを書くことで頭が整理されて、実装にも役立ちました *37 。

主要ケースの得点

最終提出直前の結果なので、最終提出とは少しずれるかも。

Seed 0: Cost = 121,139
Seed 1: Cost = 17,207
Seed 2: Cost = 213,380
Seed 3: Cost = 11,651
Seed 4: Cost = 66,967
Seed 5: Cost = 139,475
Seed 6: Cost = 296,528
Seed 7: Cost = 60,132
Seed 8: Cost = 20,719
Seed 9: Cost = 57,148

Seed 20: Cost = 18,082

最終ロジック

戦略

$20\times 20$ のグリッド（基地と呼ぶ）上で、すべての家を水源と連結にしたいです。より厳密には、水源・家・基地の間に辺を追加していきます。最小全域木を求めるクラスカル法の要領で、近いものから *38 結んでいくと良さそうです。

基地開拓フェイズ

最初にすべての家を破壊するまで攻撃します。その後は、クラスカル法の要領で、「水源と連結でない家を含むグループ（※）」について、最も近い「水源を含むグループ（☆）」またはほかの「水源と連結でない家を含むグループ（☆）」と連結にしたいです *39 。

どの基地を攻撃するのが良いでしょうか。ある ※ の基地 A からその隣接基地 B を攻撃することを考えます。 B から ※ を通らずいずれかの ☆ の基地 C に到達するときに、到達しやすいところを選びたいです。

この攻撃の評価を「A から B への移動コスト＋ B から C への移動コスト」で定義します。移動コストは、「両端マスの高さの調整平均 × 移動距離」です *40 。 $a$ と $b$ の調整平均は、 $\displaystyle\frac{b - a}{\log b - \log a}$ で表されます（詳細は記事中）。

この評価が小さいものから順に攻撃していきます。

水源側からも歩み寄りたいですが、水源側は必ずしもつなげる必要がないので評価に調整を加えます。具体的には、水源側の評価には $\sqrt{W}$ をかけています *41 。

経由地最適化フェイズ

グリッド上で連結になったらこれらを結ぶことを考えます。これは、水源・家に必要な基地を追加してそれらを連結にする *42 ときの辺のコスト合計を最小化する変則最小全域木に帰着できます。追加する基地を貪欲に選びました *43 *44 。

最終結合フェイズ

つなげる道順はすでに決まっているので、あとは基地間を掘るのみです。各マスでの攻撃の強さを決める必要がありますが、両側の基地の高さが同じ場合は真ん中から、異なる場合は低い方からみて、前のマスを破壊できた強さで攻撃する、破壊できなければ一段階上げる、の繰り返しにしました（詳細は記事中の図）。

解法・関連 Tweet

#AHC018 おつでした。
Pretest 40.4B で暫定 13 位です。
20×20 のグリッド上でクラスカル法みたいに連結成分をくっ付けていく感じでやりました。
重みは「次に破壊した場合に隣のグループと連結にできる期待コスト（≒両端点の高さの平均×距離）」です。
画像は Seed 0 の完成図と途中図（結ぶ前） pic.twitter.com/wu1b44qC4P
— きり (@kiri8128) February 26, 2023

推定、一切してません！
— きり (@kiri8128) February 26, 2023

End

*1:うまく上げられなかったので・・

*2:両端は破壊される前提なので、「予測」を行う必要がない

*3: 問題文中の「頑丈さ」を本記事では「高さ」と表現することがあります。また高い場所の周辺を「山」と呼びます。

*4:その周辺は使わない可能性が高いので

*5:この時点ではサンプルコードがあるのに気付いてなかったが、あとで見るとほぼ同じ感じっぽい

*6: より厳密には、基地 A と基地 B の間に辺を張る条件は、「AB 間のマンハッタン距離が 30 以下で、かつ基地 C であって角 ACB が 150 度以上であるようなものが存在しない」のようにする

*7: 今回はマンハッタン距離なので 120 度みたいなのは出てこないが

*8:「アドホック」はいったん忘れて

*9: 1 ステップ目は C + 10 、 2 ステップ目は 2C + 20 、など

*10:基地は選んでも選ばなくてもよい

*11: 1 ステップ目は C + 10 、 2 ステップ目は 2C + 20 、など

*12:基地は選んでも選ばなくてもよい

*13:本当はパラメータごとに調整した方が良いけどざっくりやりたいときは合計評価が欲しくなる

*14:AHC 016 のように特定のケースで上位者と下位者の得点の比率が大きく開くような場合は、そのようなケースの重要度を下げる調整が必要になります

*15:この指標が 0.01 小さくなると、相対スコアが約 0.7% （≒ $\log 2 / 100$ ）程度改善するという目安にできます。

*16:そもそもランダムケースが作れなかったので・・

*17:最初の 10 ケースは特によく比較するので（たくさん一気に流せないので）、若干過学習気味になっている可能性はあります

*18:TLE したのもあるし、 3 s ぐらいで終わるのもある

*19:非負の整数を入力すると seed を表し、負の整数 $x$ を入力すると seed が 0 以上 $x$ 未満のケースをループする

*20:LOCAL が 1 なら手元実行モード、定義されていなければ Submission モードまたはコードテストモード

*21:そのまま全部貼り付けられるように、デバッグ情報にもすべて頭に "#" を付けると楽になった

*22:1 行目に "Code Test" を与えるとコードテスト環境であると判定する。コードテスト時もジャッジは $S_{ij}$ を使って判定している。なおコードテスト時も本番と同様にジャッジを入力から受け取る方式も考えたが、その場合手元で流してからコードテストみたいな二度手間が発生してめんどいので断念した。ジャッジや入出力の違いは時間計測にはあまり影響を与えないはず。

*23:差分計算苦手

*24:厳密には破壊が発生しなくても攻撃により残りの高さが変わると動くが、影響が小さいと信じて無視している

*25:手元は 20 ケース、提出も 50 ケースしかないので誤差程度かもしれないが

*26:手元 20 ケースでずっと見てるので若干過学習になってる可能性はあるが・・・

*27:手元実行でもほぼ変わらず。よくなりそうなら $W \ge 2$ の場合も少しロジック入れようと思ったがやめた

*28:基地を掘るとき、破壊できなかったときの差分更新で 2 で割るところを 2 で 2 回割ってたのを修正。影響はほぼなさそう

*29:一段階を $s$ にすると、毎回の「余り」が約 $s/2$ 程度、無駄に攻撃する回数が約 $h/s$ 程度なので、 $\displaystyle\frac{sk}{2} + \displaystyle\frac{hC}{s}$ を最小化すればよいが、相加相乗平均を使うとこれは $\sqrt{\displaystyle\frac{2hC}{k}}$ のときに最小になることが分かる。地形によって若干変わるがまあ

*30:つまり最後の一撃で灰色部分を攻撃したとも言えます

*31:確定前にもあった可能性はあるが

*32:ピンク内側が高い山になっているときは遠回りした方がコストが低くなることもあるので必ずしもそうは言えないです

*33:楽しいけど朝早いのはつらい

*34: Seed = 20, 74 など

*35:特に Seed 20 で影響が大きく、コスト 23K ぐらいから 17～19K ぐらいまで改善しました。ただし、入力生成の方法から、そもそも水源が高い位置にあることは稀なので、全体への影響はほぼなさそうです。

*36:この直前で半分ぐらい WA で 300 位ぐらいまで落ちちゃってたのは内緒

*37:いつも読んでくださるみなさんのおかげで書くことができたので、読者のみなさんに感謝です

*38:厳密な距離は分からないので、下に述べるように推測しながら

*39:ここでいう「連結」とは、最寄りの基地をたどって一方から他方に行けることを言います

*40:A と C はすでに破壊されているので「高さ」が（最後の攻撃で与えた分の誤差を除いて）分かっています。 B は次の攻撃で破壊されたと仮定した高さを使います。

*41: $W=1$ のときは水源と家に本質的な違いはない（すべてを連結にするしかない）ので調整倍率は $1$ になります。

*42:ただし水源間は初めから連結であるとします

*43:つまり、追加したときの削減効果が一番大きいものを順に追加していきます

*44:焼きなましなどの方法も考えましたが、道がそもそも多くないのでこれで十分な気がしました

2023-02-16

2048iang

この記事は何？

2048iang というゲームについて、戦略などを書きます。

honoka55.github.io

2048iangってどんなゲーム？

ビャン（）という漢字のパーツが湧いてくるので、うまくくっつけてビャンを作るゲームです。完成タイルはこんな感じです。

パーツの組み合わせによっては合体できたりできなかったりするので、順番や組み合わせを考えて作る必要があります。

目標は？

ビャンをひとつ作ったらクリア（"You Win" というメッセージが出る）ですが、その後もゲームを続けることはできます。本記事ではビャンをふたつ作るまでの戦略について書きます。

筆者は執筆時点では、ビャンをふたつ作って 7900 点ぐらいまでいけました。

用語

パーツ

ビャンを構成する極小要素。「幺」「言」「長」「馬」「月」「刂」「穴」「心」「辶」の 9 種類ある。

タイル

パーツまたはパーツを組み合わせた漢字がかかれたマス

結合

パーツ・タイル同士をくっ付けること。「合体」も同じ意味で使う。

赤マス

「幺言幺長馬長」の 4 種類 6 つのパーツからなるマス（下の画像）。これができると出現確率などが変わる。

同時付け

赤マス以降で複数パーツを同時に付けること

ビャンの作り方

ビャンをひとつ作る方法です。

前半の戦略

赤マスを作るまでを前半と呼びます。

赤マス出現までは、赤マスに必要な「幺」「言」「長」「馬」の 4 種類しか湧いてきません *1 。

レア度

序盤で重要なのは「幺」と「長」を集めることです。

「幺」と「長」は 2 つずつ必要なのでレア度が高いです *2 。この 2 種類がある程度きれいに出てくれると赤マスは作りやすいでしょう。

合体の組み合わせ

赤マスを作るには 3 種類の方法があります。

① 「幺言幺」と「長馬長」

② 「言幺馬長」と「幺長」

③ 「幺幺長長」と「言馬」

基本的には①を目指すのがおすすめです。パーツを 2 種類ずつに完全に分けて作れるのと、それぞれの 3 個についてはどの 2 つからでも合体できるので作りやすいです。

配置の工夫

「幺」と「言」、「長」と「馬」をそれぞれ近付けるのがポイントです。できたものを角に集めて、その片側を「幺言」ゾーン、逆側を「長馬」ゾーンにすると無駄がなくなります。

画像のような状態にしておくと、「幺」または「言」が出たら下方向に、「長」または「馬」が出たら左方向に動かすと分離をキープできます。

2 種類合体の種類

序盤に出てくる 4 つのパーツ「幺」「言」「長」「馬」からなるペアのうち「幺馬」だけは合体できません。分離する際にこれが使えることがありますね。例えば下の画像では左右・上下のどちらに動かすのもほぼ等価に見えますが、左右だと長と幺が合体してしまうので（上の①の戦略に従うと）上下に動かすのが良いです *3 。

不要タイル処理

ビャンを目指すだけなら序盤であまり困ることはないですが、不要タイルがあふれることがあります。

特に序盤で余りがちな「言」と「馬」は、同種タイル合体でたくさん消費することができます。「言」は 4 つまで、「馬」は 3 つまで合体できます。

序盤で無駄タイルがたくさんできてしまうと苦しいので、なるべく余りタイルの数を増やさないように工夫しましょう。

リセマラ

このゲームは戦略要素も大きいですが、運要素も多いので、ある程度成功確率が低そうだったらリセットしてやり直す手もあります *4 。

後半の戦略

赤マスができた後は、次のステップがあります。

「月」と「刂」をくっ付ける（この 2 つは順不同）
「穴」と「心」をくっ付ける（この 2 つは順不同）
「辶」をくっ付ける

「月」「刂」フェイズ

赤マスができたあとは、後半に必要な 5 種類のパーツの出現確率が上がります。「月」と「刂」が出る確率は合わせて約 1/3 です。出てきたときに赤マスとくっ付けられる位置に来てほしいので、なるべく赤マスの隣接を広くあけておくのがポイントです。

ただ特に「月」は結合しやすい（ほかのすべてのタイルと合体する）ので、不要タイルと結合して逃さないように注意しましょう。

「穴」「心」フェイズ

「月」「刂」フェイズとほぼ一緒ですが、タイルがあふれて盤面が狭くなっている可能性が高いので、スペースをうまく確保することを意識しましょう。

また離れたマスに配置されてしまった場合は、うまくタイルをずらすことで結合できることもあります。

「辶」フェイズ

スペースを確保して、「辶」が湧くことを祈りましょう。

同時付け

上では 3 つのフェイズがあるように書きましたが、同時に本体に合体させるワザを使うと実はもう少し自由度が高いです。

例えば「月」と「刂」で「刖」にしておくと赤マスから一気にふたつ付けられたりします。

「赤マス＋刂」に「穴月」を同時につけるような、フェイズをまたぐ同時付けも可能です。

ちなみに「月」「刂」「穴」「心」の 4 つはどの 2 つも合体できて、いずれも活用チャンスがあります *5 。

このうち「刂穴」は「幺」と合体すると 3 パーツタイルになってしまってビャン生成に使えなくなってしまうので注意です *6 。

「辶」は「穴」と「心」が同時チャンスですが、残念ながら「辶」と「穴」は合体できません。つまり「辶心」のみ活用チャンスがあります。

ビャンビャンの作り方

ビャンをふたつ作る方法です。

前半の戦略

赤マスふたつを作る

上述のとおり、赤マスが出るまでは、赤マスの構成要素である 4 種類のタイルだけが出現しますが、赤マスがひとつでもできればその後はこの 4 マスの出現確率は激減します。

なので最終的にビャンをふたつ作ることを想定すると、序盤で赤マスを（ほぼ）同時にふたつ作っておくことが重要です。

下の図はひとつ赤マスをひとつ作ったところですが、直後にもうひとつ赤マスを作れる状態をキープしてます。

構成要素が足りない状態でひとつ目の赤マスを作ってしまうと、その後は赤マスに必要なマスがほぼ出現しない *7 上に、赤マスの成長もケアしないといけないのでかなりきつくなります。

レア度

「幺」「長」は序盤で 4 つずつ集める必要があるので、ビャンひとつの場合に比べてもレア度が高くなります。

他の組み合わせ

① 「幺言幺」と「長馬長」

② 「言幺馬長」と「幺長」

③ 「幺幺長長」と「言馬」

のうち②や③を使って赤マスができることもありますが、きれいにいくことは稀です（下記はたまたまうまくいった回 *8 ）。

ちなみに一番上の図で左にしてしまうと「馬長」と「長」が先にくっついてしまうので右にする必要があります。

後半の戦略

考えることはビャンひとつを狙うときとほぼ同じですが、ふたつ作ることで盤面がより圧迫されます。広くスペースを確保することを考えましょう。同時付けも有効です。

またどれとどれが合体する・合体しないかを把握して、不要タイルを処理したり意図しない合体を避けるのが大事です。

ビャンビャン麺の作り方

調理方法は残念ながらこの記事のスコープ外です。ビャンビャン麺が食べたくなったら、ググって調べるか中華料理屋さんに行って注文してください。

チートシート

各パーツの出現確率および 2 つのパーツについて、合体できるかどうかの判定をまとめたシートです。同じもの同士（対角線のピンクセル）はいくつまで合体できるかを示しています。緑マスは、さらに 1 パーツ加えて 3 パーツタイルを作れるものを示しています。

3 ～ 4 パーツで作れるタイルは次のとおりです（6 パーツ以上のタイルは通常のビャンの構成で出てくるものしかないので割愛します）。

3 パーツタイルは、序盤で出てくる左ふたつを除くとビャンの生成には活用できません。必要な単体パーツが意図せず吸収されてしまうこともあるので注意です。特にハマりやすいのは、序盤で準備していた *9 「幺言」が「刂」と合体してしまうパターンなどです。ただ不要タイルを回収する際に使える可能性はあります。

4 マスパターンについては、どちらもビャンの生成に活用できる可能性はありますが、前述のとおり「幺言幺」「長馬長」に比べると安定性が下がります。

各パーツの性質

「幺」

序盤のレアタイルのひとつ。結合力は弱く、「馬」および終盤の 3 つ（「穴」「心」「辶」）とは結合できない。同種結合は 2 まで。なので、前半で「幺言幺」を作る途中段階で「幺幺」を作っていたとして、意図せず「幺×3」になってしまうようなことはない。

後述の「刂」と同様、終盤で出てくる 3 パーツタイル（「心幺刂」「幺言刂」「穴幺刂」「馬幺刂」） 4 つのすべてに登場する。不要タイル処理には便利だが、必要なタイルを吸収されてしまうリスクもある。

「言」

序盤ではレア度が低い。結合力は高く、ほかのすべてのタイルと結合できる。序盤で余りがちだが、同種 4 つまで結合できので処理に困ったら同種結合を使う手もある。

「長」

序盤のレアタイルのひとつ。序盤では「幺」とほぼ同じ *10 働きをするが、結合できないタイルがない分、扱いが難しい。つまり「幺」は「馬」と結合できない分だけ場所調整がしやすい。

「馬」

「言」と同様、序盤ではレア度が低く余りがち。「幺」と結合できないのがポイント。

「月」

結合力が高く、「言」と同様、他のすべてのタイルと結合でき、同種も 4 つまで結合できる。

「刂」

月と似たポジションだが、結合力が少し弱い（「長」「馬」と結合できない）。

「幺」と並んで、序盤のふたつを除く 3 パーツタイル（「心幺刂」「幺言刂」「穴幺刂」「馬幺刂」） 4 つのすべてに登場する。

結合の組み合わせによっては見た目が変わる（「刀」の形になる）場合があるので注意。

「穴」

「心」と似たポジションだが、「辶」と合体できない分だけ自由度が低い（同時付けができない）。

その他の後半タイル（「月」「刂」「心」）とは結合でき、いずれも同時付けに活用できる。

「心」

「辶」と合体できるのと同種 3 個まで合体できる以外は「穴」と同様。「辶心」の同時付けは便利だが、後述の通り得点的には損になる。

結合の組み合わせによっては見た目が変わる（「忄」の形になる）場合があるので注意。

「辶」

最後の砦。

同種結合できない唯一のパーツで、中盤あたりでたくさん出現すると困ることがある。

得点について

得点計算

得点は、合体後の各マスについて、構成するパーツ数を $x$ とすると $2^{x}$ の得点が加算されます。ひとつずつ付加していくと、ビャン（11 パーツ）の完成時までには合計で約 $4000$ 点を得ることができます。

より正確には、赤マス作成時に「幺言幺」と「長馬長」から作るときは $4056$ 点、そうでないときは $4060$ 点です。

同時付け

上述の「同時付け」は自由度を上げる意味では有効ですが、得点は下がってしまうことに注意です。特に終盤に近いところで同時付けをすると得点の減り幅が大きくなります。具体的な減り幅は次の通りです：

「月」「刂」を同時に付けると $124$ 点
「月」「穴」、「月」「心」、「刂」「穴」、「刂」「心」、のいずれかを同時に付けると $252$ 点
「穴」「心」を同時に付けると $508$ 点
「心」「辶」を同時に付けると $1020$ 点

なのでビャンをひとつだけ作る場合の最低得点は $2784$ 点、最高得点は $4060$ 点です。

FAQ

ビャン 1 個もできないんだけどどうすればいい？

1 時間とかやってできなければさすがにやり方が悪そう。この記事をよく読んで頑張ってね。

ビャン 2 個むずくない？どれぐらいでできる？

簡単とは言わないけど、数十分とか 1 時間とかやると 1 回ぐらいはできるかなという感じ。

そもそも赤マス 2 つ同時がむずくない？

前半は反射＆リセマラゲーになりがち。赤 2 マス達成までの時間の期待値の最小化みたいなのを考えてやるとわりとすぐできる。

リセマラどれぐらいする？

基本的にビャン 2 個を作るまでの時間の期待値を下げたいと思っているので、序盤での無駄マスは致命的になりがちです。なので序盤での出現が不利な方に偏って成功確率が低くなってきたら早めにリセットします。例えば最初の方（4～5 マス湧いたぐらい）で「言」または「馬」が 3 つ出たらリセットで良いと思います。

スマホ・PC どっちでやってる？

暇つぶしとか子供を寝かせながらとかでやることが多いので基本スマホです。この記事を書くとき、スクショのために PC で少しやりました。

チートシートどうやって作った？見ながらやってる？

最初はやりながらメモして作ってたけど、コードを見つけたのでそこで一応確認しました。レアケース（「馬幺刂」とか）が抜けてた以外はほぼ手作りので合ってた。

いちいち見るのはめんどいのと主要部分は覚えてるので、ゲーム中は見ることはないです。

日常生活で変わったことある？

子供（4 歳）と漢字の部首の話をしているときに「しんにょうが付く漢字はどんなのがあるかなー？」って問題出したら最初の回答が「ビャン」だった。

End

*1:優しいルールですね

*2:実は出現確率も「言」「馬」より若干低い（「言」「馬」はそれぞれ 27%、「幺」と「長」はそれぞれ 23% ）

*3:長馬を作りやすいように上にするのがベストです

*4:この記事ではリセットしてやり直すことを「リセマラ」と呼んでいます

*5:ビャンを作るパーツとして使える可能性がある、という意味です

*6:終盤で気付かず合体しがちです

*7:「幺」「言」がそれぞれ 6% 、「長」「馬」がそれぞれ 4%

*8:いつもの①のつもりだったけど、進み方の関係で途中で切り替えた

*9:あるいは準備が間に合わず残っていた

*10:「幺」「言」と「長」「馬」のペアがほぼ対称的

2022-12-23

マルチディスプレイ・PC切り換え環境構築

環境構築（ディスプレイなど）

ディスプレイ関係の環境構築についてやったことなどを書きます。

仕事用と私用でPCが異なるので、切り替えをスムーズに行うこと
デュアル（トリプル）ディスプレイの設定

あたりが主なトピックです。

PC・モニター（マルチディスプレイ）まわりの環境構築について
— きり (@kiri8128) December 22, 2022

思ったより「書け」が多くて嬉しい。

前提・用途

PC の切り替えの最適化

私は平日の昼は仕事をしています *1 。一方、夜や土日は競プロをしていることが多いです *2 。

仕事はリモートワークで会社支給のノート PC を使っています。一方、競プロは私用 PC で行っています *3 。

デスクやモニターは仕事用・競プロ用で同じものを使っているので、切り替えをする必要があります。切り替えが発生するのは、仕事モードと競プロモードが入れ替わるときで、平日は少なくとも一日 2 回 *4 ありますが、昼休みに少し競プロをやったり、夜も仕事で急ぎの案件があれば対応することもあるので、実際はもっと多いです *5 。なので切り替えをスムーズにしたいというニーズが高まりつつありました。

こちらのアンケートによると、 PC は違うけど同じモニターを使用している方はわりと多そうです。手で抜き差ししている方も多そうなので、そういう方にはこの記事が参考になるかもです。

「PC は違うがモニターは共通」の方、切り替えはどうしてますか？
— きり (@kiri8128) December 20, 2022

デュアルモニターの憧れ

これまではモニター 1 つ（と会社ノート PC の画面）を使ってましたが、広いデスクを入手したのでこの機会にデュアル *6 ディスプレイにデビューしたいという憧れがありました。

ブラックフライデーで買った PC デスク、思ったより 5 倍でかくて笑ってる pic.twitter.com/PlYMdIpaAy
— きり (@kiri8128) December 4, 2022

登場人物

仕事用ノート PC（13.3インチ）
私用デスクトップ PC
モニター（27インチ）
HDMI 分配器（後述）
HDMI 切替器（後述）
USB 切替器（後述）

モニターは DVI 接続もできますが *7 、本記事では HDMI を使う前提です。

仕事用 PC は画面は小さいので作業スペースとしてはあまり使ってないですが、カメラ・マイクが内臓されていて、リモート会議などではそちらの機能を使うことが多いです *8 。

環境（Before）

改造前の環境はだいたいこんな感じ。

仕事時：ノートPCとモニターのデュアルデスクトップ

競プロ時：モニターのみ

モニターの切替器と入力（キーボード・マウス）の切替器があって、ボタンを押すと切り替わるようになっています *9 。

切替器はこちらを使っています：

HDMI の切替器

USB の切替器

切替器は押すだけで切り替えられるのでわりと快適です。

接続端子

会社 PC には HDMI がひとつと USB C *10 がひとつずつあります。

私用 PC には HDMI がひとつと DP *11 がひとつあります。

夢のデュアルモニターへ！

このセクションではデュアルモニターをするための試行錯誤について書きます。結果だけ知りたい人はスキップしても良いかもです。

モニターの購入！

まずはモニターがないと始まりません。 HDMI が使える 27 インチモニターを適当に購入しました *12 *13 。

HDMI 分配器

デュアルモニターするには HDMI を複数出力にすれば良いですね。 Amazon で分配器なるものがあるので買ってみよう！（買ってみた！）

HDMI 分配器

実はこれはワナでした。 HDMI の出力を複数に分けることはできるが、同じ信号を複数のデバイスに送っているだけなので、同じ画面が 2 つのモニターに表示されます。

ぐぬぬー

たしかにこんなに分ける必要ある？とは思ったんだけど、同じ画面でも多すぎじゃない？

憧れのマルチディスプレイ、思ってたのと違う pic.twitter.com/rDmiAhUooV
— きり (@kiri8128) December 2, 2022

Type C ハブ

会社 PC 、私用 PC ともに Type C が使えるので、「入：Type C、出：HDMI 2 つ」みたいな変換器を購入してみました。

Type C ハブ

切り替えとかはあとで考えるとして、まずは会社 PC でやってみるとうまくいきました！ノート PC 、デスクトップ 2 つのトリプルディスプレイです！やったぜ！

ちなみに会社 PC ではリモートデスクトップ接続しているんですが、そちらの設定にも戸惑ったのであとで書きます。

さて私用 PC でも同じことをやろうとしましたがうまくいきませんでした。 Type C にはいろんなパターンがあるらしくて、私の PC の Type C は画像出力に対応していないみたいです。。

このへんはくまくまに教えてもらいました *14 。

興味ありです！
— くっまっくっま (@kumakumaaaaa__) December 12, 2022

DP ポートの使用

私用 PC の Type C は残念ながら使えないということで諦めかけていましたが、よく見てみると私用 PC には HDMI ポートの他に DP（Display ポート）というなぞの穴があったので、 DP と HDMI のダブルでいけるんじゃないかという話になりました *15 。

あまり考えずオス・オスを買ってみました。これで DP とモニターを直接接続することができます！が、これだと切り換えの抜き差しを手でやらないといけなくなって大変じゃない？になってオス・メスを買い直したりしました *16 。

DP to HDMI （オス・オス）

DP to HDMI （オス・メス）

マルチディスプレイ時のリモートデスクトップ接続

上の項で書いたリモートデスクトップでのマルチディスプレイの設定についてです。リモートデスクトップは、これまでモニター側で全画面表示していたのですが、モニターが複数になると困ることがあります。普通にやると「リモートデスクトップですべてのモニターを使用する」か「ひとつだけのモニターを使用する」しか選べません。私の場合は、みっつのモニターのうちふたつのモニターをリモートデスクトップで使用したかったので困りました。

具体的には、会社のノート PC の画面はローカル使用、残りのふたつのモニターはリモートデスクトップに接続、というのが理想です *17 。

この問題については、この記事 ↓ ですべて解決しました *18 。

qiita.com

インターネット接続

会社 PC の方がリモートデスクトップの関係などで重くなりがちなので、会社 PC を有線接続、私用 PC を wifi 接続で繋いでいました。 wifi の調子が悪い場合などは LAN ケーブルを私用 PC に差し替えたりもしていましたが、毎回差し替えるのはやや手間でした。

これには簡単な解決策があって、 LAN ケーブルをもう一本購入してどちらも有線にするという方法で解決しました。

最終結果

主な配線はこんな感じになりました。

【仕事モード時】

トリプルディスプレイ（仕事用ノート PC ＋モニター 2 台）

【競プロモード時】

デュアルディスプレイ（モニター 2 台）

切り換えはもちろんすべてワンプッシュ！切替器 3 つのボタンを押すと完全に切り替わります。場合によってはふたつのモニターのうちひとつを仕事用 PC、ひとつを私用 PC に接続するというような方法も可能です *19 。

最終結果全体画像

画像だとこんな感じです。右のモニターが集中作業用、左のモニターは閲覧など用にしています。

モニター画面はこんな感じです。

左：AtCoder Problems / AtCoder の問題ページ

右：コーディング環境（Jupyter Notebook） / デバッグ環境（paiza io）

切替器周辺画像

こんな感じです。

右のふたつが HDMI の切替器。左のが USB （マウス・キーボード）の切替器です。どれも丸いボタンを押すだけで切り替えができます。（画像では微妙に見づらいですが）光っているランプを見るとどこに接続しているか一目瞭然です。私の場合は 1 が仕事用、 2 が私用と決めています。

FAQ

Q: 画像だとモニターふたつの高さ合ってなくない？買うのミスった？

A: 左側のは可動式なので合わせることはできます。最初は合わせてたんですが、右画面で集中、左画面は遠めに見ることが多いので、左画面を少し上にする方がやりやすいことに気付いてこのようにしています。

End

*1:社会人なので当然ですね

*2:疲れているときや家庭の関係で時間が取れないときはできてないこともあります

*3:私用 PC は主に競プロ用なので、この記事内では「私用」と「競プロ用」はほぼ同じ意味だと思ってください

*4:夜、仕事が終わった時に競プロモードになる、朝仕事を始めるときに仕事モードになる

*5:自分の業務は終わったけど待ち案件があるときなどは、一旦仕事 PC から離れて連絡が来たら戻るなど柔軟に対応しています

*6:仕事 PC を合わせるとトリプル

*7:以前は DVI を使っていました

*8:ちなみに普段の会議では顔出ししないことが多いですが、たまに顔出しすることもあります

*9:なので仕事モードから私用モードにするにはふたつのボタンを押す必要があります

*10:Type C

*11:Display Port

*12:27 インチにこだわりがあるわけではないですが、既存のモニターと大きさが異なると見づらいかなと思って合わせました

*13:ちなみに購入したのはこちらです

https://www.amazon.co.jp/gp/product/B08HH3BQMF/ref=ppx_yo_dt_b_search_asin_title?ie=UTF8&psc=1

*14:ありがとう！

*15:くまくまとの話です

*16:この時点ではいろいろ試行錯誤だったので仕方ないですが、早い段階で最終的な配線の絵を描いていれば良かったなと思います。ちなみにその後の試行錯誤で HDMI のオス・オスを 3 本とオス・メスを 2 本購入しました

*17:ノート PC は画面が小さいので作業にはあまり使わないですが、会議やチャットなどで使用することがあります

*18:めちゃくちゃ感謝です！

*19:どちらも集中できないのでおすすめはしません

2022-12-22

ネストすごろく

ネストすごろくの解法について書きます。

下記の問題のネタバレを含みます。

[問] 下記のネストすごろくをクリアできる確率はいくらでしょうか？

ネストすごろく：ゲームが始まると、下記のように START のマスにいる状態になります。サイコロを振り、出た目の数だけ右に進みます。GOAL に達するとクリアです。(GOAL を超えて進む目が出たとしてもクリアです) (つづく) pic.twitter.com/MRBKwbixNj
— 冬koteitan夏たこみぱん (@koteitan) December 19, 2022

解法

ネタバレ注意

↓

解の存在について

$n$ 回目までにゴールする確率の極限が求めるものです。この確率は $n$ について単調増加かつ有界 *1 なので収束します。

解の候補について

求める成功確率（クリアできる確率）を $p$ とします。

以下、マスを順に 0 ～ 6 で表します（スタートが 0 、ゴールが 6 、途中のネストマスは 1 ～ 5）。

$i=0,\ 1,\ \cdots, 6$ について、マス $i$ （ネストマスの場合はネストから出た状態）からスタートした場合の成功確率を $f(i)$ とします。遷移を考えることにより、 $i=0,\cdots,5$ について $f(i)=\displaystyle\frac{(i+1)+p\sum_{j=i+1}^{5}f(j)}{6}$ が成立することが分かります。 $i$ が大きい方から順に計算すると $f(0)=\displaystyle\frac{1}{6}(p^5+29p^4+330p^3+1800p^2+4320p+1296)$ が得られ、これが $p$ と一致することから方程式が立てられます。整理すると

$(p-1)(p^4+30p^3+360p^2+2160p-1296)=0$

となります。 $0\le p\le 1$ の範囲では 1 および約 0.54768 の 2 つの解があるので、 $p$ はこれらのうちどちらかであることが分かります。

確率が1より小さい証明

準備

次の定理を使います。

定理：期待値がマイナスのゲーム *2 がいくつかあり、これらの得点の変動は有界であるとする。このとき、これらから好きなゲームを選んで行うことを繰り返すとき、得点を 1 以上増加させる確率は 1 より真に小さい *3

例えば、「サイコロを振って 1 または 2 が出れば 1 円もらう、3 以上が出れば 1 円払う」というゲームや「コインを投げて表なら 1 円もらう、裏なら 2 円払う」というゲームはいずれも期待値がマイナスです。所持金がマイナスになることも許容します。

初期状態 0 円から始めた場合、これらのゲームをどう組み合わせて行っても（可算無限回行っても）所持金が 1 円に達する確率を 1 にする戦略は存在しません。

期待値がちょうどゼロのゲームがある場合や、得点の変動が有界でない場合は反例があります。後者は、例えば $k$ （ $k=0,\ 1,\ \cdots$ ）回目に「サイコロを振って 1 が出れば $2^k$ 円もらう、それ以外なら $2^k$ 円払う」というゲームを 1 が出るまで行うと、各回での期待値はマイナスですが、確率 1 で所持金を 1 円増やすことができます。

定理の証明は割愛しますが、大数の（弱）法則と同様、チェビシェフの不等式等で示せます *4 。

ポテンシャル

突然ですが、マス $i$ （ネストマスの場合はネストから出た状態）のポテンシャル $pot_i$ を次のように定めます：

$pot_0=0$

$pot_1=0.3$

$pot_2=0.5$

$pot_3=0.7$

$pot_4=0.9$

$pot_5=1$

$pot_6=1$

ネスト状態にある場合は、ミニゲームのゴールが出た場所のポテンシャルに一致するように平行移動します。

たとえばマス 3 におけるミニゲームでは、元のゲームのポテンシャルに比べて全体的に 0.3 ずつ小さいポテンシャルになります。ネストが深い場合も同様に定義します。

このとき、各回におけるポテンシャル変動の期待値はマイナスです *5 *6 。よって上の定理からゴールに到達する確率は 1 より真に小さいことが分かります。

結論

以上から、ネストすごろくの成功確率は約 54.768% *7 であることが分かりました。

*1:確率なので 1 以下ですね

*2:特定の確率分布に従って得点が変動するゲーム

*3:本記事の範囲では、ゲームの種類および各ゲームの変動の種類は有限と仮定しても十分です。実際はゲームは無限にあっても大丈夫ですが、ゲームすべてを通じて変動が有界であることを仮定します（分散が有限ぐらいに緩められると思います）。

*4:ちゃんとやってないけどたぶん

*5:マス 0 から 4 の 5 パターンについて計算すると確かめられます

*6:マス 5 にいるとき（ネストから出た状態）は実質的にゴールしていると考えて無視します

*7:より正確には、 4 次方程式 $p^4+30p^3+360p^2+2160p-1296=0$ の正の解で、小数第 1000 位まで表示すると

$0.$ $5476837398566348538736915801471324872612952714823182913593871402694409989796377859075776900592190090$
$7606628198757054202034841930401212693633129460497867415040652203593348049137412286287904981602164178$
$0074491636281270850171363239681027441333751735874335614378030526283173576994991677145761104432778040$
$1498785549851854640803863049248525968572673545755110584749755149364414177872186419846303003124901740$
$2909054773953566596880260180847720332530298336454138928172492921930709106741764479394382694239244334$
$5859312174957337998139020368180187291778962090546826046694311992081826406104809621834699748530017824$
$0462246592001653680980186338469828376003790433809361391964464569095074251243465819389325956527811889$
$4689890884930076431733399729386771423473996769295413967839956579425794282565146960533283171160527864$
$2945889127078776391556378883187294533903541995122330844548537361049716208897048934509499098799572796$
$3787671852593955870619346419721880296707752268723625616369763173405496767805022340197182179821251090$

2022-11-20

AHC 016

本稿について

AHC016 Graphorean の考察（主に理論面）について書いています。最尤推定（ ※ 追記：あとで調べたら事前分布を仮定するものはベイズ推定と呼ぶのが正しいようです *1）に類する方法で復元をします。正規分布近似によるグラフを構築した際の誤判定率の計算方法についても記載しています。

残念ながらこれをフルに活用した解法を提出するところまでいけませんでしたが、理論面の参考になればと思います。

方針

本問は

構築フェイズ
復元フェイズ

に分けることができます。

復元フェイズについては最尤推定（後述）が理論的に最善であることが証明できます。

本稿では、厳密な最尤推定の代わりに、特徴量をいくつか用いて連続関数の対数尤度の最大化に帰着する方法を紹介します。

構築フェイズは、（復元フェイズで最尤推定を用いる前提で）期待得点の最大化をすれば良いです。グラフを選択した段階で理論的には期待得点が決まりますが、これを現実的に計算することはできるでしょうか？

実は、特徴量を表す確率変数を独立正規分布で近似すると、構築したふたつのグラフについて誤判定を起こす確率が計算できます *2 。ここから期待得点を簡易的に予測することができます。あとは焼きなまし等で期待得点が最大となるグラフのセットを構築すれば良さそうです。

実はこの方法には問題（後述）があるのですが、途中までは理論として面白いと思うので紹介します。

最尤推定

最尤推定とは

最尤推定とは、本問の例では反転・並び替え後の結果（ $H_k$ ）を見て、 $1$ から $M$ のグラフのうち、それを選んだ場合に $H_k$ になる条件付き確率 *3 が最大のものを選ぶ方法です *4 。

なお復元フェイズでは最尤推定による選択が理論的に最善となることが証明できます *5 。これは、（通常の最尤推定では事前分布が不明であることが多いが）本問では事前分布として $1$ から $M$ までのグラフが等確率で選ばれることが与えられているので、各グラフが正しい確率は尤度に厳密に比例することから従います。

特徴量

実際に、各グラフから条件付き確率を計算することは、グラフの頂点数 $n$ *6 がよほど小さくないと現実的でないです。このためいくつか特徴量を使って判定しました。特徴量としては以下を採用しました。

全体の辺の本数。
各頂点 $i$ を固定したときの、 $i$ と隣接する辺の本数。
各頂点 $i$ を固定したときの、 $(j, k)$ の組であって $i$ から $j$ 、 $i$ から $k$ 、 $j$ から $k$ のいずれにも辺が存在するものの個数
各頂点 $i$ を固定したときの、 $(j, k)$ の組であって $i$ から $j$ 、 $i$ から $k$ 、 $j$ から $k$ のいずれにも辺が存在しないものの個数

最初のものはスカラー、それ以外はいずれも $n$ 元ベクトルになります。

なお、グラフは $n \times n$ 行列で表されているとして考えていた *7 *8 ので、この考え方だと例えば 2. は行ごとの 1 のマスの個数と言い換えられます。

3. と 4. は、 $i$ を含む 3 点からなるクリーク・反クリークの個数とも言い換えられます。

判定の方法

行ごとの 1 のマスの個数の遷移行列は、愚直に DP で prob(from, to) を全パターン計算できます *9。実装上はこれの対数を持っておくとよいです。

3 点クリークは実際に計算するのは難しいので、期待値と分散のみを計算することにしました。あとは中心極限定理を信じて正規分布を仮定すれば良いです。期待値は 3 点を固定して独立に計算してから合計すればよい（期待値の線形性）ので簡単です。分散は少し工夫が必要ですが、「共分散」の概念を知っていれば計算できると思います。

頂点の対応

ひとつ問題なのは、シャッフル前後でどの頂点とどの頂点が対応するかが分からないところです *10。

簡単のため、頂点ごとの特徴量をソートして、大小順にぴったり対応すると考えました。 *11 。

期待値・分散・共分散について（復習）

確率変数 $X$ および $Y$ について、 $E(X)$ を $X$ の期待値、 $V(X)$ を $X$ の分散、 $\mathrm{Cov}(X, Y)$ を $X$ と $Y$ の共分散とします。

共分散は

$\mathrm{Cov}(X, Y) = E(XY) - E(X)E(Y)$

で定義されます。

このとき、次の性質が成立します。

$\mathrm{Cov}(X, X) = V(X)$

$X$ と $Y$ が独立のとき $\mathrm{Cov}(X, Y) = 0$

$V(X+Y) = V(X) + 2\mathrm{Cov}(X, Y) + V(Y)$

$\mathrm{Cov}(X + Y, Z) = \mathrm{Cov}(X, Z) + \mathrm{Cov}(Y, Z)$

$V(aX) = a^2V(X)$

これを繰り返し使うと、多数の確率変数の和である確率変数について、それぞれの分散と任意の 2 つの共分散が分かっていれば、その合計の期待値・分散を求めることができます *12。

各特徴量の期待値・分散の計算

反転率（問題文中の eps）を $p$ 、反転しない確率を $q=1-p$ とします。

1. 全体の本数

全体の辺の本数については、最初の辺の本数を $c$ とすると

平均 $p * c + q * (\displaystyle\frac{n(n-1)}{2} -c)$

分散 $(\displaystyle\frac{n(n-1)}{2})pq$

の二項分布に従います。計算上は正規分布に近似します *13 。

2. 各頂点から出ている辺の本数

各頂点から出ている辺の本数は、最初の該当の本数を $c$ とすると

平均 $pn + q(n - 1 - c)$

分散 $(n-1)pq$

です。

これも二項分布に従うので正規分布で近似できそうですが、少し気になる点があります。それは各頂点から出ている辺の本数を全部合計すると、辺を 2 回ずつカウントしていることになるため、独立性が担保されなくなります。

全く同じものを 2 回合計すると平均は 2 倍、分散は 4 倍になるので、分散を最大 2 倍ぐらい過小評価している可能性があります *14 。

3. 各頂点を含む 3 点クリークの個数

各頂点（ $i$ とする）に隣接する 3 点クリークの個数は、3 辺の組ごとに遷移確率が次の表で定まります。期待値はここから直接計算できます。

from\to	0	1	2	3
0	q^3	3p*q^2	3p^2*q	p^3
1	p*q^2	q^3 + 2p^2*q	2p*q^2 + p^3	p^2*q
2	p^2*q	2p*q^2 + p^3	q^3 + 2p^2*q	p*q^2
3	p^3	3p^2*q	3p*q^2	q^3

分散はちょっとややこしいですが、共分散の考え方を使うと計算できます。つまり、 3 頂点の組すべてについて期待値と分散が求まっていて、 2 つの「3 頂点の組」に対して共分散が求まっていれば全体の期待値と分散が求まります。

分散については、 $i,j,k$ の組が 3 点クリークになる場合に 1 、それ以外の場合に 0 を取る確率変数を $X$ とすると、 $V(X) = E(X)(1 - E(X))$ なので上の表から求まります。

頂点 $i$ を固定するとき、 $i,j,k$ の組と $i,l,m$ の組は相関がないので共分散はゼロです *15 。 $i,j,k$ と $i,j,l$ の組については $i,j$ 間の辺が共通なので相関があります。

上の公式に当てはめて頑張って計算すると共分散を求めることができます。

例えば、 $i,j,k,l$ の 4 点について、任意の 2 点間に最初辺があるとして、

$i,j,k$ の組が 3 点クリークになる場合に 1 、それ以外の場合に 0 を取る確率変数 $X$ と $i,j,l$ の組が 3 点クリークになる場合に 1 、それ以外の場合に 0 を取る確率変数 $Y$ の共分散 $\mathrm{Cov}(X, Y)$ を求めてみます。上の定義を思い出すと

$\mathrm{Cov}(X, Y) = E(XY) - E(X)E(Y) = q^5 - q^3q^3=q^5(1-q)=pq^5$ と計算できます。

なお、上記の $X,\ Y$ および

$i,k,l$ の組が 3 点クリークになる場合に 1 、それ以外の場合に 0 を取る確率変数 $Z$

について、 $\mathrm{Cov}(X, Y)+\mathrm{Cov}(X, Z)+\mathrm{Cov}(Y, Z)$ をまとめて考えると考察・実装がラクになります。

結果を言ってしまうと、この結果は $i,j,k,l$ 間の 6 個の候補にある辺の本数と場所によって、次のように決まります。

6 本の辺がある場合： $3pq^5$

5 本の辺がある場合： $2p^2q^4+pq^5$

4 本の辺がある場合で、それらがサイズ 4 のループをなす場合： $pq^5+2p^3q^3$

4 本の辺がある場合で、それらのうち 3 つがループをなす場合： $p^3q^3+2p^2q^4$

3 本の辺がある場合で、それらが直線状に並んでいる場合： $p^4q^2+p^3q^3+p^2q^4$

3 本の辺がある場合で、それらが長さ 3 のループをなすまたは 1 点から 3 本出ている場合： $3p^3q^3$

2 本の辺がある場合で、それらがつながっている場合： $p^3q^3 + 2p^4q^2$

2 本の辺がある場合で、それらが離れている場合： $p^5q + 2p^3q^3$

1 本の辺がある場合： $2p^4q^2+p^5q$

0 本の辺がある場合： $3p^5q$

反クリークについても同様です。

計算量が気になるかもしれませんが、グラフ盤面を予め固定しておけばパラメトリックな方法で $O(1)$ で計算できる場合もあります。受け取ったグラフのカウントは bit 演算でグラフごとに $O(N^3/w)$ などでできるので十分高速です。

盤面候補の選出

いくつか候補を出して、なるべくお互いが「近くならない」（誤判定する確率が低い）ように選びたいです。

下記の 4 パターンを使いました。

Type 0（左上）：一部のノードのみ全結合 *16

Type 1（左下）：Type 0 の逆 *17

Type 2（右上）：差が一定以内のものを結合 *18

Type 3（右下）：3 段タイプ *19

誤判定率

最尤推定による判定では、各初期グラフ $g=1,2,\cdots, M$ について各特徴量 $i=1,2,\cdots, 3n+1$ による尤度の積を計算して、その合計が最大となる $g$ を選ぶという方法でした。

ここではすべての分布を正規分布で近似して、対数尤度の和の最大化と考えます。正規分布の確率密度関数は $f(x)=\displaystyle\frac{1}{2\pi\sigma ^2}e^{-(x - \mu)^2/2}$ で表されることを思い出しましょう。

平均 $\mu$ 、分散 $\sigma ^2$ の正規分布を $N(\mu, \sigma ^2)$ で表します。確率変数 $X$ がこの分布に従うことを $X \sim N(\mu, \sigma ^2)$ のように書きます。

各特徴量 $i$ の分布を $X_i \sim N(\mu_i, \sigma_i ^2)$ とすると、 $X_i=x$ における対数尤度は $-\displaystyle\frac{(x-\mu_i)^2}{2\sigma_i ^2} - \displaystyle\frac{1}{2}\log 2\pi \sigma_i ^2$ で表されます。復元フェイズではこの和が最大の $i$ を選ぶのが最善です。

次にこれが誤判定を起こす確率を計算 *20 します。

誤判定をするというのは $g$ 番目のグラフについて、 $g$ 番目のグラフの特徴量に基づく対数尤度の合計よりもあるほかのグラフ（ $g'$ とします）の特徴量に基づく対数尤度の合計の方が大きくなることです。まず $g$ と $g'$ を固定して、 $g$ を $g'$ であると誤判定する確率を計算します。

グラフ $g$ の $i$ 番目の特徴量の確率変数を $X_{g,i} \sim N(\mu_{g,i}, \sigma_{g,i} ^2)$ とすると、次の式が成立する確率を求めれば良いです。

$\displaystyle\sum_i \left( -\displaystyle\frac{(X_{g,i}-\mu_{g,i})^2}{2\sigma_{g,i} ^2} - \displaystyle\frac{1}{2}\log 2\pi \sigma_{g,i} ^2 \right) \lt \displaystyle\sum_i \left( -\displaystyle\frac{(X_{g,i}-\mu_{g',i})^2}{2\sigma_{g',i} ^2} - \displaystyle\frac{1}{2}\log 2\pi \sigma_{g',i} ^2 \right)$

$\displaystyle\sum_i \left(\displaystyle\frac{(X_{g,i}-\mu_{g,i})^2}{\sigma_{g,i} ^2} + \log \sigma_{g,i} ^2 \right) \gt \displaystyle\sum_i \left(\displaystyle\frac{(X_{g,i}-\mu_{g',i})^2}{\sigma_{g',i} ^2} + \log \sigma_{g',i} ^2 \right)$

右辺はパラメータが $g$ ではなく $g'$ に基づいていますが、確率変数は $g$ に基づく $X_{g,i}$ であることに注意してください。

ここで $Z_{g,i}= \displaystyle\frac{X_{g,i}-\mu_{g,i}}{\sigma_{g,i}}$ とおくと、これは標準正規分布に従う（ $Z_{g,i} \sim N(0, 1)$ ）ので、 $E(Z_{g,i})=0,\ E(Z_{g,i}^2)=V(Z_{g,i})=1$ が成立します。

これを使って上式をさらに変形すると

$\displaystyle\sum_i \left(\displaystyle\frac{(X_{g,i}-\mu_{g,i})^2}{\sigma_{g,i} ^2} + \log \sigma_{g,i} ^2 \right) \gt \displaystyle\sum_i \left(\Big(\displaystyle\frac{X_{g,i}-\mu_{g,i}}{\sigma_{g,i}}\displaystyle\frac{\sigma_{g,i}}{\sigma_{g',i}} + \displaystyle\frac{\mu_{g,i} - \mu_{g',i}}{\sigma_{g',i}}\Big)^2 + \log \sigma_{g',i} ^2 \right)$

$\displaystyle\sum_i \left(Z_{g,i}^2 + \log \sigma_{g,i} ^2 \right) \gt \displaystyle\sum_i \left(\Big(\displaystyle\frac{\sigma_{g,i}}{\sigma_{g',i}}Z + \displaystyle\frac{\mu_{g,i} - \mu_{g',i}}{\sigma_{g',i}}\Big)^2 + \log \sigma_{g',i} ^2 \right)$

$\displaystyle\sum_i \left(\Big(\displaystyle\frac{\sigma_{g,i} ^2}{\sigma_{g',i} ^2}-1\Big) Z_{g,i}^2 + \displaystyle\frac{2\sigma_{g,i}(\mu_{g,i} - \mu_{g',i})}{\sigma_{g',i} ^2} Z_{g,i} + \Big(\displaystyle\frac{\mu_{g,i}-\mu_{g',i}}{\sigma_{g',i}}\Big)^2+ \log \displaystyle\frac{\sigma_{g',i} ^2}{\sigma_{g,i} ^2} \right) \lt 0$

よってこの左辺を $A$ とおくと、この期待値 $e$ と分散 $\sigma^2$ は

$e=E(A) = \displaystyle\sum_i \left(\Big(\displaystyle\frac{\sigma_{g,i} ^2}{\sigma_{g',i} ^2}-1\Big) + \Big(\displaystyle\frac{\mu_{g,i}-\mu_{g',i}}{\sigma_{g',i}}\Big)^2+ \log \displaystyle\frac{\sigma_{g',i} ^2}{\sigma_{g,i} ^2} \right)$

$\sigma ^2=V(A) = \displaystyle\sum_{i} \left(2\Big(\displaystyle\frac{\sigma_{g,i} ^2}{\sigma_{g',i} ^2}-1\Big)^2 + \displaystyle\frac{4\sigma_{g,i}^2(\mu_{g,i} - \mu_{g',i})^2}{\sigma_{g',i} ^4} \right)$

と計算できます。これも正規分布だと思うと、求める誤判定率は $P(A \lt 0) = 1 - F(\displaystyle\frac{e}{\sigma})$ （ただし $F$ は正規分布の累積分布関数）となります。

問題点

紹介した方法にはいくつか問題点があります。

二項分布などに従う特徴量を正規分布で近似している
誤判定率の計算において、対数尤度の確率変数を正規分布で近似している
行ごとの特徴量をソートして使っている

実験してみると 1. と 2. の問題はあまり大きくないことが分かります。一方、条件によっては 3. の問題がかなり大きいようです。実際、場合によっては本稿の方法で計算した誤判定率がかなり小さい *21 場合でも、正規分布を仮定して実験するとほとんどの場合で誤判定をする *22 こともありました。順序統計量（ソート後の確率変数）が満たす性質に近い分布を選びがちになる場合があるということかなと思います。

ソートして使う以外の方法としては、「〇〇以下である特徴量の個数」のような確率変数を新たに特徴量とすれば、これはソートによる影響を受けないのでもう少し良い判定ができそうです *23 。

参加記

実はコンテスト中、一瞬 5 位ぐらいまでは上がってその時点では解法ガチャに成功したかと思っていました（この時点では最尤推定ぐらいしかしていません。しかもいろいろミスってました）。

5 位！#AHC016 pic.twitter.com/7q3yRKwBdc
— きり (@kiri8128) November 13, 2022

その後、誤判定率の推定、それによる焼きなまし法、順序統計量による期待値・分散の補正などいろんなアイデアを思いついて試しましたがことごとく悪くなるという結果になってしまいました *24 。

ソートによるノイズが大きいことに気付いたのが最終日で、それ以降はちょっと時間的に何もできないという結果でした。

結果的に、 5 位時点のコードほぼそのままみたいなものが最終提出になりました *25 。

誤判定率については、正規分布に従う乱数で数回試すみたいな判定の方がましだったかもしれません *26 。

ローカルでたくさん回して最善方法を埋め込む手も強そうな気がしました。こんなこともあるので AWS とかで分散コンピューティングとかのモチベーションが少し上がりました。

ビジュアライザ

Matrixが見やすかったので使っていました。

デバッグ窓には、実際の値、盤面ごとの（期待値・標準偏差）の組などを表示していました。このケースでは真ん中が正しいんですが、左を選んでしまいました。

緑枠部分の上から 3 行目を見ると、実際の値（29）が $N(111.2, 21.7 ^2)$ から来たか $N(4.7, 4.7 ^2)$ から来たかで判定ができるはず *27 なんですが、微妙な位置にいて判定をミスってしまったパターンです。

反省

思ったとおりの結果が出ないときに、コードベースのエラーチェックしかできてなかったので、仮説が正しい検証を逐一入れていればもう少し早めに起動修正できたかもしれません。

次回以降は分散コンピューティングを含め、作業環境をもう少し整えたうえで臨めればと思います。

End

*1:この後も何度か出てきますがベイズ推定と思ってください

*2:中心極限定理から、たくさんの確率変数の合計は正規分布に近付くという意味では正当性がありそうですが、自由度が小さい場合の裾野の厚さの問題と、独立性が必ずしも言えないことによる問題があります。

*3:連続分布の場合は密度関数

*4:一般的には最尤推定というと（連続）パラメータを推定する際に用いるため、本問のように $M$ 個からひとつを選ぶという趣旨とは異なることが多いですが、条件付き確率（密度）の最大化という意味で共通しているので本記事では「最尤推定」と呼んでいます。

*5:厳密な判定が現実的にできるかどうかは別として

*6:問題文では大文字で $N$ となっていましたが、後述の正規分布の記号と紛らわしいので小文字で記載しています

*7: $i$ 行 $j$ 列が $1$ なら頂点 $i$ と頂点 $j$ の間に辺がある、 $0$ なら辺がない。

*8:この意味でグラフを盤面と言ったりします

*9: $O(n^3)$ DP など

*10:全体の辺の本数は頂点によらないので大丈夫ですが、その他の特徴量はすべて問題になります

*11:より正確にするには順序統計量を考慮するなどが必要ですが、ちょっと大変そうです。逆転が起きない前提で、同じパラメータの頂点の組合せ数を考慮する方法もありそうです

*12: たとえば $V(X+Y+Z) = V(X) + V(Y) + V(Z) + 2\mathrm{Cov}(X, Y) + 2\mathrm{Cov}(X, Z) + 2\mathrm{Cov}(Y, Z)$

*13:二項分布は $p,q$ が極端に小さくなくて $n$ がある程度大きければ正規分布に近くなります

*14:もちろん、完全に連動するわけではないので通常は2 倍よりはだいぶ小さいはずです

*15:異なる文字は異なる頂点を表していると思ってください

*16:反クリークの判定が強い

*17:クリークが強い

*18:平均が同じものの中でクリークの期待値が最も小さくなる

*19:2 段目の階段の境目付近のクリーク判定が強い

*20:厳密な計算ではないので推定と言った方が良いかもしれません

*21:10^-6 オーダーとか

*22:10 万回やって全ケースとか

*23:これはこれで独立性が弱くなりますが、偏差が最大の特徴量を使うなどでカバーできるかもです

*24:手元実行環境はいまいちなのですが、 1 ケース流しただけでだめさ加減が分かるぐらいひどいので提出までいけなかったものもたくさんあります

*25:プレテスト時点で 58 位・・

*26:ただ実行時間的には PyPy コードテストでパラメータによっては 1-2 回しか回せなさそうだったのでもう少し工夫が必要そうでした

*27:この 2 盤面の差が最も顕著に表れる部分という意味で