2019/3/28に行われた部内コンテストの解説です。
テーマは「DP」

コンテストのリンク(https://onlinejudge.u-aizu.ac.jp/beta/room.html#YNUCPC_045)

A問題

概要

カエルは前方に $L$ 進む、または $1$ 進むのいずれかの行動を行える。ちょうど $D$ 進むのに最低何回跳ぶ必要があるか求めよ。

解説

この問題では貪欲が可能です。なるべく $L$ で進むのがいいので $D/L + D%L$ が答えです。

B問題

解説

直前にどの服を着たかのみが問題なので、これを状態にもってDPを行うことができます。

$dp[i][j]=$ $i$ 日目に服 $j$ を来た時の派手さの総和の最大値

とおくと次のように状態と遷移の関係を表せます。

漸化式

$$ dp[i+1][j] = \max_{0 \le k < N} ( dp[i][k] + \mathrm{abs} (C[j]-C[k]) ) $$

初期化

$$ dp[0][i] = 0 \ \ (i=0,1,2,…N-1) $$

求める値

$$ \max_{0 \le k < N} dp[D][i] $$

ただし遷移条件は $A[k] \le T[i] \le B[k]$ かつ $A[j] \le T[i+1] \le B[j]$ です。

計算量は $O(DN^2)$ になります。

C問題

解説

どのパスタを何日連続で食べているかのみが問題なので、これを状態にもってDPを行うことができます。

$dp[i][j][k]=$ $i$ 日目でパスタ $j$ を $k$ 日連続して食べている通り

とします。

遷移は

• 前日と異なるパスタを食べ、連続日数を $1$ にする
• 前日と同じパスタを食べ、連続日数を $+1$ する

が考えられます。

漸化式

$$ dp[i+1][j][1] = \sum_{k \neq j} \sum_{l = 1}^{2} dp[i][k][l] \\ ~ dp[i+1][j][l+1] = dp[i][j][l] $$

初期化

$$ dp[0][i][1] = 1 \ \ (i=0,1,2) $$

求める値

$$ \sum_{i = 0}^{2} \sum_{j = 1}^{2} dp[N][i][j] $$

ただし、予定に反するような遷移は行わないように注意してください。

計算量はパスタの種類を $M$、連続で食べられる上限日数を $L$ として $O(N M^2 L)$ になります。

D問題

解説

足し算では順序を変えても結果は変わらないので、重複なく数えるために昇順(あるいは降順)に整数を使うことを仮定します。すると次にどの整数を使えるかは直前に使った整数をみれば判断できるようになります。

$dp[i][j][k]=$ $i$ 個の $j$ 未満の整数を使い総和が $k$ になるようにする通り

とします。

$dp[i+1][j+1][k+j]$ への遷移としては

• $i$ 個の $j$ 未満の整数で総和を $k$ にしてから $i+1$個目に $j$ を加える
• $i+1$ 個の $j$ 未満の整数で総和を $k+j$ にする

が考えられます。まとめると、

漸化式

$$ dp[i+1][j+1][k+j] = dp[i][j][k] + dp[i+1][j][k+j] $$

初期化

$$ dp[0][i][0] = 1 \ \ (i = 0,1,2,…) $$

求める値

$$ dp[N][101][S] $$

計算量は使う整数の上限を $M$ として $O(NMS)$ になります。

E問題

解説

$dp[i][j] =$ $t$ の $i$ 文字目まで使って $b$ の $j$ 文字目までつくる通り

とします。

$t[i] = b[j]$ であれば $dp[i][j]$ に対して $t$ の $i$ 文字目を使えば $b$ のつくれる長さが $1$ 増えるので $dp[i+1][j+1]$ は $dp[i][j]$ 通り増えます。また、$t$ の $i$ 文字目までですでに $b$ の $j+1$ 文字目までつくっている通りを考慮して $dp[i][j+1]$ を加えます。まとめると、

漸化式

$$ dp[i+1][j+1] = \left \{ \begin{array}{l} dp[i][j+1] + dp[i][j] & (t[i]=b[j]) \\ ~ dp[i][j+1] & (t[i] \neq b[j]) \end{array} \right. $$

初期化

$$ dp[0][0] = 1 $$

求める値

$$ dp[|t|][|b|] $$

計算量は $O(|t||b|)$ になります。

F問題

解説

饅頭の大きさはすべて同じなので違いは価値のみです。なので饅頭を $X$ 個選ぶときの価値を最大化したいときは貪欲に価値の大きいものからとっていけばよいです。これは前処理としてソートしてから累積和をとっておくことで高速に求められるようになります。

問題は箱の選び方です。容量と値段がバラバラなので貪欲は通りません。同じ容量分を買うならなるべく値段は少ないほうがよいのでこれをDPします。具体的にDPにのせる情報は次のようになります。

• どの箱まで考慮したか
• 容量の総和

$dp[i][j] =$ $i$ 番目の箱まで見て容量が $j$ になるようにしたときの最小コスト

とします。遷移上で注意すべきことは $j$ が $M$ 以上になった場合は $M$ 直すようにすることです。

漸化式

$$ dp[i+1][j+C_i] = \min (dp[i][j]+E_i , dp[i][j+C_i]) $$

初期化

$$ dp[0][0] = 0 $$

求める値

$$ \max_{0 \le i \le M} \left( \sum_{k = 0}^{i} P_k - dp[N][i] \right) $$

計算量は $O(M \log M + NM)$ になります。

by NOSS