1. 挨拶
にゃ～ん
2. 趣旨
普段AHC参加記は書かないのですが今回はとてもよい順位を残せたので、界隈に僅かでも貢献したいと思い執筆するに至りました。また終了後にtwitterへ投稿した簡易的な解説が雑に書きすぎたので訂正目的も兼ねます。
最終順位は5位でした。今までの最高がAHC047の61位だったので大幅更新です！
3. 各山1枚ずつ分配(-10 Min.)
初回提出は $A_i$ に $[L, U]$ の範囲からランダムな値を代入して、各山に最適なカードを割り当てる方法を取りました。 $A$ と $B$ を昇順に並べておき、動的計画法を組むことで $O(NM)$ で最適解を得られます。
この方法だと $N$ 個の数が $L$ 以上 $U$ 以下の範囲に一定の密度で分布するため、期待される各山の誤差は $\dfrac{U-L}{2N} = 4.0 \times 10^9$ 程度となります。なぜならおよそ $\dfrac{U-L}{N}$ ごとに $A_i$ が存在するため、各 $B_i$ について直近の $A_i$ までの距離は $\dfrac{U-L}{2N}$ 程度と期待されます。
実際得られた得点は $6.5 \times 10^{10}$ だったので、各山の誤差は $4.2 \times 10^9$ くらいでした。
4. 各山2枚ずつ分配(-180 Min.)
（準備）
$A_i$ に $[L/2, U/2]$ の範囲からランダムな値を代入して適当に組み合わせて $N/2$ 個のセットを作る。
（焼きなまし遷移）
セット間でカードの入れ替えを行う。
セットたちをカードの総和で昇順ソート。 $O(N\log N)$
山とセットを貪欲マッチングする。 $O(N+M)$
というようなことを3時間くらい試しました。初期解を工夫したり、定数倍高速化したり、3枚ごとに分配したり、1部のカードを調整用の小さな値にしたり……色々試しましたが、あまり強くなかったです。
得られた得点は $7.5 \times 10^{10}$ から $7.7 \times 10^{10}$ 程度で、 $8.0 \times 10^{10}$ を超えるビジョンが全く見えませんでした。
焼きなまし法を実装し始めたときは順位表2ページ目くらいにいましたが、この3時間の間にズルズルと200位くらいまで順位を落としました。
上位を見ると $9.0 \times 10^{10}$ 点以上の人が30人くらい現れ始めており、大きく方針を変えないとこのままズルズル下がり続けるなという状況でした。
この焼きなましが弱かったのはマッチング能力の弱さです。2枚組セットをあらかじめ決めてから、山に対してセットを割り当てていました。セット数 $O(N)$ 組なので各山での誤差が $O\left(\dfrac{U-L}{N}\right)$ であるような割り当ての中で良いものを探索しても劇的な改善が得られなかったのだと思います。焼きなまし法はここで棄却しました。
初期解の構成の際に気づいた点として、最適性を少し緩和して
カードが $N-2(i-1)$ 枚あります。$A_1, \cdots, A_{N-2(i-1)}$ と表します。
$|(A_j + A_k) - B_i|$ が最小となるような組 $(j, k)$ を求めなさい。
という問題を $M$ 回解くことにするとだいぶ向き合いやすくなります。この部分問題は尺取り法を用いて $O(N)$ で解けますので、全体として $O(NM)$ で済みます。
尺取り法のやり方
易しめのアルゴの問題です。数列 $A$ はソート済みとします。
各 $j$ に対して $|(A_j + A_k) - B_i|$ が最小になる $k = bestk(j)$ を考えます。 $j$ が大きくなるたびに対応する $bestk(j)$ は小さくなります。なのでポインタを $j = 1$ ポインタ $k = N-2(i-1)$ を右端に置いて初期化して、 $A_j + A_k$ が $B_i$ より小さければ $j \leftarrow j + 1$ 、 $A_j + A_k$ が $B_i$ より大きければ $k \leftarrow k - 1$ をします。
この走査の過程で得た $A_j + A_k$ のうちいずれかが題意を満たす組 $(j, k)$ です。
セットは $O(N^2)$ 組できるので、期待される誤差はお気持ち的に $O\left(\dfrac{U-L}{N^2}\right)$ くらいになるはずです。
実際には↑は過言で、各セットの値（ $A_j + A_k$ ）はサイコロを2個振ったときの分布と同じように $\dfrac{L+U}{2}$ くらいに集中しますし、カードの消費のされ方にも偏りがあると思うので割と悪化します。どんぶり勘定です。
5. 各山4枚ずつ分配(-200 Min.)
$A_i \in [L/4, U/4]$ とします。
カードが $N-4(i-1)$ 枚あります。$A_1, \cdots, A_{N-4(i-1)}$ と表します。
$|(A_j + A_k + A_l + A_m) - B_i|$ が最小となるような組 $(j, k, l, m)$ を求めなさい。
先述の尺取り法をよく見ると事前にあらゆるペア $O(N^2)$ 個について和 $A_j + A_k$ を列挙しておくことによりこの部分問題が $O(N^2)$ で解けることが分かります。誤差はお気持ち的に $O\left(\dfrac{U-L}{N^4}\right)$ となり、劇的に改善するはずです。
半分全列挙です。JOIのダーツを彷彿とさせますね。（ https://www2.ioi-jp.org/joi/2023/2024-ho/2024-ho-pr-t5.pdf ）
この方法で提出すると残念ながら $7.3 \times 10^{10}$ でした。Visualizerを凝視すると両端が極端に悪いです。
先ほどのサイコロ理論で端の方は手薄になりがちな上、大きい数が早期に売り切れてしまっているのだと思います。 $A$ の範囲をちょっと広げて $A_i \in [L/4 \times 0.99, U/4 \times 1.01]$ にしたところ $1.09 \times 10^{11}$ まで上がりました。これで順位表1枚目に躍り出ました。
6. 各山6枚ずつ分配(-240 Min.)
$A_i \in [L/6 \times 0.99, U/6 \times 1.01]$ とします。
先述の方法はカードを6枚にすると $O(N^3 M)$ となり流石に間に合いませんが、 $O(N^3)$ 通りあるカード3枚組のうち時間内で間に合うだけ列挙することで同じようなことができます。
①ペアの列挙を毎回行うのではなく、ペアを列挙した配列は使いまわす。
②カードの3つ組をシフト演算をかませることでuint32_tによって表現
など定数倍高速化により$5 \times 10^6$ 組列挙させても間に合いました。これを提出したところ $1.28 \times 10^{11}$ 点で最終5位となりました。
7. 末文
ダブル暖色人材になりました。はっぴー。ついでにアルゴのHighestより高くなってしまいました。
振り返ってみると迷走してばかりで、最終提出に大きく活きたアイデアはダーツの1点だけだった気がします。相変わらず発想1つで劇的にスコアが変わり、AHCは奥深いなと実感しました。