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$ 点。