挨拶
にゃ～ん
概要
公式解説とは別の視点で解く解法。結局同じような式が立つのだけれどこっちの方がだいぶ考えやすかった。
AGC068
— SSRS (@SSRS_cp) September 29, 2024
A: 選んだ人がいるところに白、その正反対に黒を置くと、白と黒がある距離以下になってはいけない → 色は後で決めることにする L の偶奇で場合分けなど
B: 最初 0*N, 1*N を置いておく 2 つのキューがあり、0 0 で 1 つのキューを回転させながら 0 1 で同時に取り出す問題になる
丁寧に書こうと思ってます。AGC-A だからupsolveしたいけど難しいよ～って人の助けになれば幸い。
問題の言い換え
①人 $0$ は必ず選ぶとしてよいです。求める場合の数のうちの $\frac{N}{L}$ が人 $0$ を選んでおり、残りは人 $0$ を選んでいません。人 $0$ を必ず選ぶと思い込んで計算して最後に $\frac{L}{N}$ 倍すればいいです。
②まず人数が偶数人のときを考えます。奇数人のときは少しだけ複雑になります。
人 $i$ を選ぶことを赤く塗ることで表すことにします。それと同時にその反対の位置にある人を青く塗ります。
すると
$$
(コスト) = (赤同士の距離の最大値) = L/2 - (赤と青の距離の最小値)
$$
となります。
だいぶ見通しが立ちやすくなります。円環上の距離の最大値を求めようとすると全点対を考える羽目になり厳しいですが、最小値を求めるのであれば隣同士だけ注目すればよいです。すごい……
隣り合う赤と青の距離がどれも $D$ 以上となるような場合の数 $F(D)$ を求めにいきます。
$$
Ans = \sum_{D = 0}^{L/2} \left(\frac{L}{2} - D\right)(F(D) - F(D + 1))
$$
などとすれば答えが出ます。
L: 偶数のとき
$N$ 人を赤色に塗り、それらと対称の位置にいる $N$ 人を青色に塗ることを考えると、どのように塗っても必ず人 $0$ から人 $\frac{L}{2} - 1$ のうち丁度 $N$ 人が色を塗られていることに気づきます。
この範囲の人たちの色を適切に決めてあげれば、対称性により人 $\frac{L}{2}$ から人 $L - 1$ もその塗り方に従います。
さて色を塗られた人たちを $p_0 = 0, p_1, p_2, \cdots, p_N = \frac{L}{2} - 1, \cdots, p_{2N - 1}$ としましょう。
(i) 人 $p_i$ と人 $p_{i + 1}$ が同じ色で塗られる場合、間の距離は $1,2,3,\cdots$ が許されます。FPSで表すと $\frac{x}{1-x}$です。
(ii) 人 $p_i$ と人 $p_{i + 1}$ が異なる色で塗られる場合、間の距離は $D,D+1,D+2,\cdots$ が許されます。FPSで表すと $\frac{x^D}{1-x}$です。
ここで人 $p_0$ と人 $p_N$ は異なる色である必要があります。つまり人 $p_0$ から人 $p_N$ の間に(ii)は奇数回発生する必要があります。
(i)が選ばれる回数を $N-M$ 回、(ii)が選ばれる回数を $M$ 回とすると
$$
f(D)\xleftarrow{+}\binom{N}{M}\left[x^{\frac{L}{2}}\right]\left(\frac{x}{1-x}\right)^{N-M}\left(\frac{x^D}{1-x}\right)^{M}
$$
$$
=\binom{N}{M}\left[x^{\frac{L}{2}-DM -(N-M)}\right]\left(\frac{1}{1-x}\right)^{N}
$$
$$
=\binom{N}{M}\binom{(N-1) + (\frac{L}{2}-DM -(N-M))}{(\frac{L}{2}-DM -(N-M))}
$$
となります。なんと二項係数の積を計算するだけの問題になります。
これを $D=1,2,\cdots$ と$M=1,3,5,\cdots$ にかけてループを回しますが $-DM$ という項を見ればわかる通り調和級数のあれで $O(L\log L)$ です。
Q. $D = 0$ のとき、つまり赤い人の対称な位置に青い人と赤い人が共存できる場合について。(ii)のFPSは異なる色同士の距離が $0,1,2,\cdots$ となるので一見よさそうですが正しくない結果を得ます。なぜでしょう。理由はいろいろあります。
L: 奇数のとき
$L$ が偶数のときの議論が腑に落ちていれば大したことはありません。人同士の間に新たに人を挟んでしまいましょう。 $2L$ 人から $2N$ 人に色を塗ります。
この際に赤く塗る $N$ 人は偶数番目の人から選ぶ必要があり、青く塗る $N$ 人は奇数番目の人から選ぶ必要があることに注意します。
赤と青の距離は必ず奇数です。同じ色同士の距離は必ず偶数です。
赤と青の距離がいずれも $D$ 以上である場合の数 $G(D)$ を求めまれば
$$
Ans = \sum_{D = 1,3,\cdots, L} \left(\frac{L}{2} - \frac{D}{2} \right)(G(D) - G(D + 2))
$$
となります。
(i) 人 $p_i$ と人 $p_{i + 1}$ が同じ色で塗られる場合、間の距離は $2,4,6,\cdots$ が許されます。FPSで表すと $\frac{x^2}{1-x^2}$です。
(ii) 人 $p_i$ と人 $p_{i + 1}$ が異なる色で塗られる場合、間の距離は $D,D+2,D+4,\cdots$ が許されます。FPSで表すと $\frac{x^D}{1-x^2}$です。
として同様です。
終わり
解けるか～～！！(# ﾟДﾟ)