AtCoder Grand Contest 050-D Shopping 解説 - クマーの競プロ精進日記

注意：以下 AtCoder Grand Contest 050-D Shopping のネタバレを思いっきり含みます. というかネタバレそのものです.

・問題

atcoder.jp

・計算量

公式解説の $O(N^6)$ ではなく $O(N^4)$ の解法です. 6乗を許しているのはわざとなんでしょうか. りんごさんが４乗の解法を見落とすのか？という疑問があります.

・解説
$i :=$ まだ商品を受け取っていない人数

$k :=$ 今から商品を選ぶ人が左から何番目か ( $i$ 人中)

$l :=$ 現在何ターン目か ( $1, 2,\cdots , N$ 番の人が操作を行うことを１ターンとする)

とする。このとき $dp_{i,j,k,l}$ を、 $i$ 人中左から $j$ 番目の人が商品を受け取れる確率として定義する. 特に ${i\lt N-K}$ ならば $dp_{i,j,k,l}= 0$ である.

残りの商品の数が $(K-(N-i))$ 個、今から商品を受け取る人( $i$ 人中 $k$ 番目の人) がまだ調べていない商品の数が $(K-l)$ 個なので、 $k$ 番目の人が商品を即受け取れる確率は $\frac{K-(N-i)}{K-l}$ . 受け取る場合とそうでない場合について、場合分けしてメモ化再帰で回せばよい.

・コード例

atcoder.jp