2018-12-31

Typical DP Contest H - ナップザック

解法

基本的な考え方は普段のナップサックと同じで、ある重さになるような荷物の選び方の中での価値の最大値、を求めていきます。
今回、荷物には色が塗られており、 $C$ 種類以下でナップサックに荷物をつめなければなりません。
ということで、次のようなDPを考えます。
$dp[j][k][l][m] =$ 色を $k$ 種類使用して、重さの合計が $j$ になるような荷物の選び方の中での価値の総和の最大値
ここで、 $l,m$ が何を表しているかというと、 $l$ は次に見る荷物 $i$ の色 $c_i$ を $i-1$ までの荷物を調べた段階で使用しているかどうか、そして $m$ は $i$ の荷物をすでに使用したかどうか、です。
$l$ が存在することで、全ての荷物を色の番号順でソートしておけば、同じ色を違う種類と判定することなく調べることができ、 $m$ が存在することで、荷物 $i$ を2つ以上いれる心配がなくなります。
ということで、あらかじめ全ての荷物を、色の番号が若い順にソートしておきます。

さて、荷物 $i$ に注目ときのDPの遷移を考えていきます。
まず、DPテーブルの整理から始めます。というのも、 $i$ 番目の荷物を調べる時も、 $i-1$ 番目の荷物を調べる時も、同じDPテーブルを再利用するためです。
2つのパターンが存在します。荷物 $i$ の色 $c_i$ が、それ以前に登場しているかどうか、です。あらかじめソートをしているので、1つ前の荷物の色と比較して、違ったならば色 $c_i$ は $i$ 番目で初出、等しければそれ以前ですでに使用していることになります。

$c_i$ が $i$ 番目で初出ではない場合 $( c_{i-1} = c_i)$
$i-1$ 番目の荷物について調べた際の、 $m$ 、すなわち $i-1$ 番目の荷物を使用しているかどうか、という情報はもう必要ないので、 $m=0$ にまとめ上げます。ということで、
$dp[j][k][l][0] = max(dp[j][k][l][0],dp[j][k][l][1])$
という処理と、
$dp[j][k][l][1] = 0$
という操作をしてあげます。
$c_i$ が $i$ 番目で初出だった場合 $( c_{i-1} \neq c_i)$
上の操作に加えて、 $l$ のリセットも必要になります。 $i-1$ 番目までの荷物の組み合わせで、色 $c_i$ の荷物を使用することがないからです。
$dp[j][k][0][0] = max(dp[j][k][l][m])$
です。それ以外は0で初期化するので、
$dp[j][k][0][1] = dp[j][k][1][0] = dp[j][k][1][1] = 0$
という処理をしてあげます。

さて、DPテーブルの整理が終わったので、 $i$ 番目の荷物について考えていきます。
$i$ 番目の荷物を使用しておらず、かつ

それまでで色 $c_i$ の荷物を使用していなければ、色の種類数に+1
色 $c_i$ の荷物を使用していれば、色の種類数はそのまま

となるので、DPの遷移は次のようになります。 $i$ を使用した時点で、 $l,m$ はどちらも1になることに注意します。
$dp[j][k][1][1] = max(dp[j][k][1][1] ,dp[j- w_i][k-1][0][0]+v_i,dp[j-w_i][k][1][0]+v_i)$
ということで、この更新を行いつつ、 $dp[j][k][1][1]$ の更新を行うごとに、全体での最大値を更新していけば、この遷移が終えた段階で、更新した最大値が答えとなります。

2018-12-31

Typical DP Contest F - 準急

動的計画法(DP)

問題
 提出コード

解法

$dp[i] =$ 駅 $i$ で止まるような駅 $i$ までのパターン数、のようにしていきたいところですが、連続して何駅止まったか、という情報が必要になるので無理です。
逆転の発想をして、 $dp[i] =$ 駅 $i$ を通過するような駅 $0$ ～ $i-1$ のパターン数、としましょう。
ダミーの駅 $0$ というものが存在し、ここを必ず通過している、と仮定します。初期状態では、 $dp[0] =1$ 、そして $dp[1] = 0$ です。
駅 $i$ で通過するには、駅 $i-1$ を通過している、駅 $i-1$ にはとまるが駅 $i-2$ で通過している、駅 $i-1$ と駅 $i-2$ にはとまるが駅 $i-3$ で通過している…駅 $i-1$ から駅 $i-K+1$ にはとまるが駅 $i-K$ で通過している、というパターンがあります。
結局はこのようになります。
$\displaystyle dp[i] = \sum_{j=min(0,i-K)}^{i-1} dp[j]$
これは、累積和なりを用いることで、簡単に計算することができます。
あとは、答えを求めるだけです。
駅 $N$ にはとまらなければならないので、駅 $N-1$ を通過している、駅 $N-2$ を通過してそれ以降とまる、駅 $N-3$ を通過してそれ以降とまる、…駅 $N-K+1$ を通過してそれ以降とまる、というパターンの総和になります。ここで、駅 $N$ はとまる必要があるので、先ほどと条件が少しことなることに注意してください。
ということで、答えは以下のようになります。
$\displaystyle \sum_{j=N-K+1}^{N-1} dp[j]$
あとは、 $10^{9}+7$ で割った余りをとることに注意しつつ計算していけばよいです。

2018-12-31

Typical DP Contest E - 数

動的計画法(DP) 桁DP

問題
 提出コード

解法

制約をみてもわかるように桁DPです。
$dp[i][j][m]$ とします。 $i$ は、上から $i$ 桁目を決める段階、という意味です。 $j$ は、今作成している数字の桁和を $D$ で割った余りが $j$ であるという意味です。 $m$ は、今作成している数字が $N$ 未満であることが確定しているかどうか、を表します(している場合は1、なければ0です)。初期状態は、 $dp[0][0][0] = 1$ です。
$N$ の桁数を $n$ 、 $N$ の上から $i$ 桁目を $N_i$ と表記することにします。
最終的な答えは、 $dp[n][0][1]+dp[n][0][0]-1$ です。-1は、0を表しています。今回は正整数が条件なので、0を省かなければなりません。
$i-1$ 桁目まで決めた段階での桁和を $D$ で割った余りが $j$ のとき、 $i$ 桁目を $k$ にすることを考えます( $k$ はもちろん0以上9以下です)。
これは、 $dp[i][(j+k)\%D][1]$ と $dp[i][(j+k)\%D][0]$ についてを考えることになります。
ここから先は、 $k$ と $N_i$ の関係によって3つに場合分けされます。順番に見ていきます。

$k \lt N_i$ のとき
$i-1$ 桁目を決める時点で $N$ 未満であることが確定しているかどうかにかかわらず、 $i+1$ 桁目以降でどんな数字を当てはめても $N$ 未満になります。ので、 $m=1$ になります。
ということで、遷移は
$dp[i][(j+k)\%D][1] += dp[i-1][j][0] + dp[i-1][j][1]$
となります。
$k = N_i$ のとき
$N$ 未満が確定しているかどうかは、 $i-1$ 桁目の時点で $N$ 未満であることが確定しているかどうかに依存します。 $i-1$ 桁目の状態をそのまま受け継ぎます。
ということで、遷移は
$dp[i][(j+k)\%D][1] += dp[i][j][1]$
$dp[i][(j+k)\%D][0] += dp[i][j][0]$
となります。
$k \gt N_i$ のとき
$N$ 未満であることが $i-1$ 桁目の時点で決まっていればいいですが、そうでない場合は、 $i$ 桁目で $k$ を選ぶと $N$ を超えてしまうので、問題の条件を満たさなくなります。ということで、 $m=1$ についてのみ考えればよく、遷移は
$dp[i][(j+k)\%D][1] += dp[i][j][1]$
のみとなります。

あとは、これを繰り返してDPを行っていけばよいです。 $10^{9}+7$ で割った余りを求めることに注意しましょう。

2018-12-31

Typical DP Contest D - サイコロ

動的計画法(DP)

問題
 提出コード
復習問題だったのですが、見事MLEを吐きました。

解法

$d_2 =D$ を素因数分解したときに登場する2の個数、とします(3,5も同様です)。
基本的な方針としては、
$dp[i][j][k][l] = i$ 回サイコロを振ったときに、2が $j$ 回、3が $k$ 回、5が $l$ 回登場するような確率
とします。4は2が2回分、6は2と3が1回ずつ分として計算します。
初期状態は、 $dp[0][0][0][0] = 1$ です。
$i+1$ 回目に、1~6のどれを出すか、で遷移を行っていきます。
1から順番に、それぞれ以下のようになります。

$dp[i+1][j][k][l] += dp[i][j][k][l]/6$
$dp[i+1][j+1][k][l] += dp[i][j][k][l]/6$
$dp[i+1][j][k+1][l] += dp[i][j][k][l]/6$
$dp[i+1][j+2][k][l] += dp[i][j][k][l]/6$
$dp[i+1][j][k][l+1] += dp[i][j][k][l]/6$
$dp[i+1][j+1][k+1][l] += dp[i][j][k][l]/6$

答えは、 $D$ を素因数分解したときに2,3,5以外の素因数が含まれていたら0、そうでなければ $j \geqq d_2, k \geqq d_3, l \geqq d_5$ となる $j,k,l$ を選んだ時の $dp[N][j][k][l]$ の総和です。ただし、このままだと途中でMLEやらなんやらを吐きACすることができません(少なくとも自分はそうでした)。そこで、 $i$ 回目で $j,k,l$ がそれぞれ $d_2,d_3,d_5$ にたどり着いた時点で、それ以降は1~6のどの目がでても問題の条件を満たす、ということに着目すると、以下のようにDPを組み替えることができます。

$dp[i+1][j][k][l] += dp[i][j][k][l]/6$
$dp[i+1][min(j+1,d_2)][k][l] += dp[i][j][k][l]/6$
$dp[i+1][j][min(k+1,d_3)][l] += dp[i][j][k][l]/6$
$dp[i+1][min(j+2,d_2)][k][l] += dp[i][j][k][l]/6$
$dp[i+1][j][k][min(l+1,d_5)] += dp[i][j][k][l]/6$
$dp[i+1][min(j+1,d_2)][min(k+1,d_3)][l] += dp[i][j][k][l]/6$

このように組み替えることで、メモリを抑えつつ、また、答えは $dp[N][d_2][d_3][d_5]$ を見るだけでわかるようになります。

2018-12-31

Typical DP Contest C - トーナメント

動的計画法(DP)

問題
 提出コード

解法

はじめに、 $P(x,y) = x$ 番の人が $y$ 番の人に勝つ確率、としておきます。
$dp[i][j] = i$ 番目の人が、第 $j$ ラウンドで勝つ確率、とします。
初期状態は $dp[i][0] = 1$ であり、答えは $dp[i][K]$ をすべて見ればよいです。
簡単に言えば、 $i$ 番目の人が第 $j$ ラウンドで戦う可能性のある相手の集合を $S$ としたときに、
$\displaystyle dp[i][j] = dp[i][j-1] \times \sum_{l \in S}^{} \{P(i,l) \times dp[l][j-1] \}$
となります。
さて、ここからは $i$ が0-indexedであると仮定して話を進めたいと思います(その方が好都合だからです)。
$S$ に含まれる人を探していきます。第 $j$ ラウンドで $i$ 番の人が対戦する可能性のある人は、全部で $2^{j-1}$ 人います。そして、その人達の番号はすべて連番になっています。
ということで、その連番の最初がわかってしまえば、そこから $2^{j-1}$ 人を対象として上の式による計算を行えばいいわけです。
第1ラウンドについて考えてみると、 $i$ 番目の人は、 $i$ が奇数であれば $i-1$ 番目の人と、 $i$ が偶数であれば $i+1$ の人とのみ対戦を行います(0-indexedにしたことに気を付けてください)。
第2ラウンドについて考えてみると、0,1番の人は2,3番の人と、4,5番の人は6,7番の人と対戦を行うことになります。
これを繰り返すと、
第 $j$ ラウンドでは、 $2^{j-1}$ 人ごとにグループ分けをして、若い番号の人がいるグループから順番に0,1,2...と番号を振り、その後0と1、2と3…グループで対戦を行います。
なので、まず $i$ を $2^{j-1}$ で割った値を求めます(これを $x$ とします、切り捨てです)。すると、これがグループ番号となるので、あとは $x$ が偶数なら $x+1$ グループと、奇数なら $x-1$ グループと対戦を行います。
そして、 $x$ グループの先頭は、 $x\times 2^{j-1}$ となります。そこから $2^{j-1}$ 人が、今回 $i$ 番の人が対戦する可能性のある相手になります。
これにより、第 $j$ ラウンドにおける $i$ の対戦相手がわかったので、あとは遷移の式にしたがって計算をしていけば、答えを求めることができます。

2018-12-31

Typical DP Contest B - ゲーム

動的計画法(DP)

問題
 提出コード
いきなり難易度高くないですか…？

解法

左右それぞれの山に積まれている物の合計個数の偶奇によって、どちらのターンかは一意に決まります。
$A+B$ が偶数のとき、左右の合計が奇数であれば、次は後攻、偶数であれば先攻です。
$A+B$ が奇数の場合はこの逆になります。
さて、次のようなDPを考えていきます。

$dp[i][j] =$ 左の山の物の個数が $i$ 個、右が $j$ 個であったとき、ここからお互いが最適に動いた場合に得られる、すぬけ君が選んだ物の価値の合計

こうすることで、答えは $dp[A][B]$ を見ればいいことがわかります。
また、初期状態は、 $dp[0][0] = 0$ です。
さて、左右の山に積まれた物の個数の合計によってターンがどちらかが変わるので、左が $i$ 個、右が $j$ 個の山になっていた場合のそれぞれについて最適な行動を考えてみます。

左が $i$ 個、右が $j$ 個で先攻だったパターン
左から物をとると、その価値は $a_{A-i+1}$ であり、右からとった場合は、 $b_{B-j+1}$ です。
それ以降お互いが最適な行動をした場合のすぬけ君の合計価値は、前者のパターンが $dp[i-1][j]$ 、後者が $dp[i][j-1]$ であるので、この値と、このターンでとった物の価値を合計して、より良い方を選べばよいです。ということで、
$dp[i][j] = max(dp[i-1][j]+a_{A-i+1},dp[i][j-1]+b_{B-j+1})$
左が $i$ 個、右が $j$ 個で後攻だったパターン
このターンでは、左と右どちらを選んでもすぬけ君の合計価値自体は変化がないです。が、すめけ君は、すぬけ君の合計価値ができるだけ小さくなるように行動をするので、
$dp[i][j] = min(dp[i-1][j],dp[i][j-1])$
となります。