かしのブログ

競技プログラミングとか

第二回アルゴリズム実技検定 M - 食堂

AtCoder PAST DP ダブリング

問題

ある食堂では $i$ 日目、 $i + D$ 日目、 $i + 2D$ 日目 $\cdots$ に料理 $C_i$ が提供される。社員 $i(1\leq i \leq N)$ それぞれについて、以下の条件で食堂に通うとき、 $T_i$ 回目に利用するまでに料理 $K_i$ を食べる回数 $A_i$ を求める。

初めて食堂を利用する日は $F_i$ 日目である。
初めて食堂を利用して以降、料理 $K_i$ が提供される日は必ず食堂を利用する。
初めて食堂を利用して以降、前回の利用から $L$ 日経過しているなら利用する。

考察

各社員について、自分の好きな料理以外はどれも同じとみなすので料理ごとに独立に問題を解くことができる。以下、料理 $x$ と好きな料理が $x$ の社員 $y$ について解く

料理 $x$ が提供される日の集合[tex: \mathcal{D}x]は、 [tex: \mathcal{D}x \triangleq \{ d | d]日目に提供される料理が $x\}$

$|\mathcal{D}_x| = 0$ のとき、解は0。以下、そうでない場合を考える。

解がかなり大きくなる可能性があり、また、メニュー $x$ を食べる回数を決めて二分探索するのも難しい。この問題はダブリングを用いて解く。次のようなDPを考える

${\rm dp1}[d_i][k] \triangleq d_i$ の $2^k$ 回後にメニュー $x$ を食べるまでに全てのメニューを食べる回数
${\rm dp2}[d_i][k] \triangleq d_i$ の $2^k$ 回後にメニュー $x$ を食べる日

と定義する。

${\rm dp1}[d_i][0] = \frac{d_{i+1} - d_i - 1}{L} + 1$ （ただし $d_{i+|\mathcal{D}_x|} = d_i$ ）
${\rm dp1}[d_i][k+1] = {\rm dp1}[d_i][k] + {\rm dp1}[next][k]$
${\rm dp2}[d_i][k+1] = {\rm dp2}[next][k] \ \ (next = {\rm dp2}[d_i][k])$

で更新する。

以下、社員 $y$ についての解を求める。

まず、最初に料理 $x$ を食べる日まで $T_y$ を減らす。その後、その日から $2^p$ 回食べるまでに全てのメニューを食べる回数が、残り日数を超えないか判定しながら、料理 $x$ を食べる回数をカウントする。

実装