AtCoder Grand Contest 032 F - One Third

公式解説より面倒なことをしている気もするが知見が得られたので． atcoder.jp

問題概要

円形のピザに中心から外側に向かってランダムに $N$ 回切込みを入れる．
連続するピースのうち合計面積が $\frac{1}{3}$ （ピザ全体を $1$ とする）に最も近いものを選ぶ．
その面積を $x$ とするとき $|x - \frac{1}{3}|$ の期待値を $\mathrm{mod} \ 10 ^ {9} + 7$ で求めよ．

制約

$2 \leq N \leq 10 ^ {6}$

解法

言い換え

ある切れ込みから $\frac{1}{3}$ 離れた二箇所付近は考慮するが自身の周りは考慮しないというのが考えにくい．
そこで公式解説と同様の言い換えを行う．

$\left[ 0, 1 \right]$ 上にランダムに $N - 1$ 点，色をランダムに赤青緑から選び打つ．
$0$ に赤点， $1$ に青点を打つ．
色の異なる二点間の距離の最小値の期待値を求めよ．

この問題が解ければその $\frac{1}{3}$ 倍が答えとなる．

まず，色のことは忘れて…

$N + 1$ 点の位置を昇順に $X _ 0,...,X _ N \ (X _ 0 = 0, X _ N = 1)$ とする．
距離の最小値としては隣り合う二点のみを考えれば十分である．
そこで， $X _ 1 - X _ 0, \dots ,X _ N - X _ {N - 1}$ を昇順に並び替えたものを $Y _ 1, \dots, Y _ N$ とおく．
実は，この $Y _ k$ の分布関数 $F _ k$ や期待値 $E \left[ Y _ k \right]$ は，

$\begin{aligned} F _ k(x) &= 1 - \sum _ {i = 0} ^ {k - 1} \binom{N}{i} \sum _ {j = 0} ^ {i} (-1) ^ {j} \binom{i}{j} \max \left\{1 - (N - i + j) x, 0 \right\} ^ {N - 1} \ (x \geq 0) \\ E \left[ Y _ k \right] &= \frac{1}{N} \sum _ {i = 0} ^ {k - 1} \frac{1}{N - i} \end{aligned}$

と表すことができる．

略証

まず，分布関数 $F _ k$ について（以降， $x \geq 0$ とする），

$\begin{aligned} 1 - F _ k(x) &= P \left[ Y _ k \geq x \right] \\ &= P \left[ |\left\{ j \mid 1 \leq j \leq N, X _ j - X _ {j - 1} \geq x \right\}| \geq N - k + 1 \right] \\ &= \sum _ {i = 0} ^ {k - 1} P \left[ |\left\{ j \mid 1 \leq j \leq N, X _ j - X _ {j - 1} \geq x \right\}| = N - i \right] \end{aligned}$

と変形し，各項を包除原理を用いて計算すると，

$\begin{aligned} 1 - F _ k(x) &= \sum _ {i = 0} ^ {k - 1} \binom{N}{N - i} \sum _ {j = 0} ^ {i} (-1) ^ {j} \binom{i}{j} \max \left\{ 1 - (N - i + j) x, 0 \right\} ^ {N - 1} \end{aligned}$

となる．
これを用いると期待値 $E \left[ Y _ k \right]$ は，

$\begin{aligned} E \left[ Y _ k \right] &= \int _ {0} ^ {\infty} 1 - F _ k(x) dx \\ &= \sum _ {i = 0} ^ {k - 1} \binom{N}{i} \sum _ {j = 0} ^ {i} (-1) ^ {j} \binom{i}{j} \frac{1}{N (N - i + j)} \\ &= \frac{1}{N} \sum _ {i = 0} ^ {k - 1} \frac{1}{N - i} \end{aligned}$

となる（最後の式変形は非自明だ（と思う）が， $i$ に関する帰納法で証明できる）．

（追記）知人の協力によって母関数を考えるとベータ関数の積分公式に帰着されることが判明した．
二項係数が出てくる変な和 - 劣ブログ

仕上げ

$N + 1$ 点によってできた $N$ 個の区間を短い順に見ていき初めて両端の点の色が異なったときの区間の長さ（の期待値）が求めるものとなる．
これは点の位置と色が独立であることから，

$\begin{aligned} \left( \sum _ {k = 1} ^ {N - 1} \left( \frac{1}{3} \right) ^ {k - 1} \frac{2}{3} Y _ k \right) + \left( \frac{1}{3} \right) ^ {N - 1} Y _ N \end{aligned}$

となる．
よって答えを書き下すと，

$\begin{aligned} \frac{1}{3} \left( \left( \sum _ {k = 1} ^ {N - 1} \left( \frac{1}{3} \right) ^ {k - 1} \frac{2}{3} \frac{1}{N} \sum _ {i = 0} ^ {k - 1} \frac{1}{N - i} \right) + \left( \frac{1}{3} \right) ^ {N - 1} \frac{1}{N} \sum _ {i = 0} ^ {N - 1} \frac{1}{N - i} \right) \end{aligned}$

となる．

実装例

https://atcoder.jp/contests/agc032/submissions/4713546