AHC012お疲れ様でした。98,254,833点で11位です。

今回も解説を書きます。

問題概要
方針
解法
日記
感想

問題概要

AtCoder 10周年おめでとう🎂

イチゴの数がいい感じになるようにケーキを切り分けてね。

atcoder.jp

方針

斜めに切るのは難しすぎるので、縦横にグリッド状に切っていくことにしました。

切る位置を少しずつ変えていくだけの比較的素直な焼きなましを行って、よい切り方を探索していきます。

解法

初期解の生成

縦横の分割数 $m$ は、 $k^2\ge \sum_{d=1}^{10}a_d$ となるような $k$ を求めて、そこからちょっと余裕を持たせた $m=k+3$ としました。 $3$ という数字に深い根拠はなく、適当にいろいろ試して良かった数字を採用しています。*1

この分割数で縦横方向に等間隔に切りました。

解の持ち方

差分計算を行うことを考え、以下のデータを持つことにしました。

縦方向に切断する $x$ 座標の配列
横方向に切断する $y$ 座標の配列
各イチゴがどのピースに存在するか管理する2次元配列
$n\ (0\le n\le N)$ 個のイチゴが載っているピースの個数を管理する配列

切断数は初期解のものから固定としたので、各配列の長さは固定です。

焼きなまし中に差分計算を行って高速化するため、各イチゴがどのピースに存在するかについて管理していきます。イチゴがちょうど切断線上に来るケースがあるためややこしいのですが、縦 $(2m-1)\ \times$ 横 $(2m-1)$ の2次元グリッドを考え、左（下）から $l$ 番目のピースの番号を $2l$ 、左（下）から $l$ 番目の切断線の番号を $2l+1$ と定め、2次元グリッドの左から $i$ 、下から $j$ 番目のピース（または切断線上）に含まれるイチゴの座標の集合を $S[i][j]$ としました。*2

初期解を生成した後に、各イチゴの $x,y$ 座標それぞれについて二分探索を行うことで、 $O(N\log m)$ でこのグリッドを初期化することができます。

焼きなまし

「ランダムな切断線を選び、 $\pm100$ の範囲（ただし隣り合う線を跨がない範囲）で座標をずらす」という近傍のみを使って焼きなましました。この時影響のあるイチゴは切断線上とその左右（または上下）にあるものだけなので、そこだけ差分計算を行うことで高速に更新していくことができます。手元だと3秒でだいたい220万回くらい（AtCoderのコードテスト上では160万回くらい）回っていました。

評価関数

焼きなましを行う際、評価関数が $\min(f,g)$ のような形だと評価値が平坦となる領域が多くなり、解がブラウン運動をするだけでうまく焼けないことが多いです。*3 そこで生のスコア $S$ に加えて、「目的のピース数 $a$ と現在の解のピース数 $b$ について、 $a_d$ と $b_{d'}$ との間にコスト $(d-d')^2$ の辺を張ってマッチングを行ったときの総コスト $C$ 」を考慮しました。

これは最小費用流で解くと死ぬほど遅い*4 のですが、辺が交差しないように貪欲に割り当てるのが最適なので、以下のような処理にすることで高速に求めることができました。

a = 目的のピース数の配列
b = 現在の解のピース数の配列

# 適当にinfで埋める
b[11] = 100000

# 総コスト
C = 0
j = 1

for i in range(1, 11):
    while a[i] > 0:
        while b[j] == 0:
            j += 1
        
        count = min(a[i], b[j])
        a[i] -= count
        b[j] -= count
        C += (i - j) * (i - j) * count

このようにして総コスト $C$ を求めた上で、 $S-1000C(1-t)$ を焼きなましの評価関数としました。ここで、 $t\ (0\le t\le 1)$ は焼きなましの進行状態を表す変数で、焼きなまし開始時点を0、焼きなまし終了時点を1としています。「序盤はざっくりピース数を寄せて、終盤は生のスコアを最大化したい」みたいなお気持ちです。