はじめに
この記事は、EDPC の K ~ O 問題の解説です。K ~ O 問題を解いてみてから読まれることを推奨します。
また、J 問題までをまだ解いていない方は、下記ページも読んでいただくといいと思います。
なお、この記事は基礎的な DP について理解できている人が読む想定で書いているので、上記の記事と比べて解説や実装例が適当簡潔になっています。
この記事の続き
- Educational DP Contest (EDPC) P ~ S 問題 解説
- Educational DP Contest (EDPC) T ~ W 問題 解説
- Educational DP Contest (EDPC) X ~ Z 問題 解説
K - Stones
問題
二人でゲームをします。
$N$ 要素の正の整数の集合 $A$ が与えられます。
先手と後手は、石の山に対して、交互に次の操作を行います。
- $x\in A$ を選び、山から $x$ 個ちょうどの石を取り除く。
- そのような操作ができない場合、ゲームは終了する。その時点で手番である方が負けとなる。
最初に石が $K$ 個あるとき、先手と後手どちらが勝つか答えなさい。
制約
- $1\le N\le 100$
- $1\le K\le 10^5$
解法
基本的な Game の問題です。
石の個数によって勝敗が左右されそうなので、$dp_i$を「$i$ 個の石が残っているとき、手番の人は勝てるか」とします。
$dp_{i-x}=\mathrm{false}$ の場合、手番の人はその $x$ を選べばいいので、$dp_i=\mathrm{true}$ です。
また、そのような $x$ が無い場合、どう操作しても相手が勝つので $dp_i=\mathrm{false}$ です。
実装例
計算量は $O(NK)$ です。
#include <iostream>
using namespace std;
int N, K, A[109];
bool dp[100009];
int main() {
cin >> N >> K;
for(int i = 0; i < N; i++)
cin >> A[i];
for(int i = 0; i <= K; i++)
for(int j = 0; j < N; j++)
if(i >= A[j]) dp[i] |= !dp[i - A[j]];
cout << (dp[K] ? "First" : "Second") << endl;
return 0;
}
L - Deque
問題
二人でゲームをします。
$N$ 要素の数列 $a$ に対して、数列が空になるまで交互に次の操作を行います。
- $a$ の先頭か末尾を取り除く。取り除いた数を自分の得点に加算する。
先手、後手の最終的な得点をそれぞれ $X,Y$ としたとき、先手は $X-Y$ を最大化しようとし、後手は $X-Y$ を最小化しようとします。
$X-Y$ を求めてください。
制約
- $1\le N\le 3000$
解法
問題文中で太字で示したところを言い換えると、自分の点数 $-$ 相手の点数 (以下、スコア) を最大化するとなります。
残っている区間が決まれば、そこからのスコアの最大値も決まるので、
$dp_{l,r}$ を「区間 $\left[l,r\right]$ が残っているとき、手番の人のスコアの最大値」とします。
DP の遷移は $dp_{l,r}=\max\left(a_l-dp_{l+1,r},a_r-dp_{l,r+1}\right)$ となります。
このような区間を扱う DP は、俗に区間 DP と呼ばれたりします。
実装例
計算量は $O(N^2)$ です。
#include <iostream>
using namespace std;
int N, a[3009];
long long dp[3009][3009];
int main() {
cin >> N;
for(int i = 0; i < N; i++)
cin >> a[i];
// bit = r - l としています。
for(int bit = 0; bit < N; bit++) {
for(int l = 0; l + bit < N; l++) {
int r = l + bit;
dp[l][r] = a[l] - dp[l + 1][r];
if(r) dp[l][r] = min(dp[l][r], a[r] - dp[l][r - 1]);
}
}
cout << dp[0][N - 1] << endl;
return 0;
}
M - Candies
問題
$N$ 人の子供に丁度 $K$ 個の飴を配る方法は何通りあるか$\mod10^9+7$ で求めてください。
ただし、$i$ 人目に配る飴の個数は $0$ 以上 $a_i$ 以下でないといけません。
制約
- $1\le N\le 100$
- $1\le K \le 10^5$
解法
$dp_{i,j}=$ ($i$ 人目までに $j$ 個配る方法) という DP をやればよさそうです。実際に書いてみます。
dp[0][0] = 1;
for(int i = 0; i < N; i++) {
for(int j = 0; j <= K; j++) {
for(int k = 0; k <= a[i] && k <= j; k++) {
dp[i + 1][j] += dp[i][j - k];
dp[i + 1][j] %= mod;
}
}
}
これの計算量は $O(NK^2)$ で残念ながら遅すぎるので、高速化する必要があります。
DP の遷移を数式にしてみると、こうなります。
\displaystyle{dp_{i+1,j}=\sum_{k=\max(0,j-a_i)}^j dp_{i,k}}
いかにも累積和が使えそうな形です。実際に累積和を使うと、遷移を $O(1)$ でできるので、全体で $O(NK)$ となり、間に合います。
実装例
負の整数の mod を取るときは、法を足して正にしてから mod を取ります。
#include <iostream>
using namespace std;
const int mod = 1000000007;
int N, K;
int a[110];
int dp[110][100010];
int main() {
cin >> N >> K;
for(int i = 0; i < N; i++)
cin >> a[i];
dp[0][0] = 1;
for(int i = 0; i < N; i++) {
// 累積和を取る
int sum[100010];
sum[0] = 0;
for(int j = 0; j <= K; j++)
sum[j + 1] = (sum[j] + dp[i][j]) % mod;
for(int j = 0; j <= K; j++)
// 負の mod に気を付ける
dp[i + 1][j] = (sum[j + 1] - sum[max(0, j - a[i])] + mod) % mod;
}
cout << dp[N][K] << endl;
return 0;
}
N - Slimes
問題
$N$ 匹のスライムが並んでいる。
最初、$i$ 匹目の大きさは $a_i$ である。
スライムが $1$ 匹になるまで以下の操作を繰り返し行う
- 隣り合うスライムを選び、合体する。合体後の大きさは合体前の大きさの和になる。合体後の大きさと同じコストがかかる。
かかるコストの最小値を求めてください。
制約
- $2\le N\le 400$
解法
典型的な区間 DP の問題ですね。
$dp_{l,r}=$ ( 区間 $[l,r]$ を $1$ 匹のスライムにするために必要なコストの最小値 ) という DP を行えばいいです。
区間 $[l,r]$ になる直前にどこで切れていたかをすべて試すと遷移が $O(N)$ でできるので、全体で $O(N^3)$ となり、解けます。
実装例
L 問題では区間 DP をループを使って実装したので、ここではメモ化再帰で書きます。
累積和を取らなくても計算量は変わりませんが、実装量等の観点から累積和を取っています。
#include <iostream>
using namespace std;
const long long INF = 1LL << 60;
int N;
long long a[409];
long long dp[409][409];
long long solve(int l, int r) {
if(l == r) return 0;
if(dp[l][r] != 0) return dp[l][r];
long long res = INF;
for(int i = l; i < r; i++)
res = min(res, solve(l, i) + solve(i + 1, r));
res += a[r];
if(l > 0) res -= a[l - 1];
return dp[l][r] = res;
}
int main() {
cin >> N;
for(int i = 0; i < N; i++) {
cin >> a[i];
if(i) a[i] += a[i - 1]; // 累積和を取る
}
cout << solve(0, N - 1) << endl;
return 0;
}
O - Matching
問題
男性と女性が $N$ 人ずついます。
男性 $i$ と女性 $j$ の相性が $0$ か $1$ で与えられ、相性が $0$ の場合はペアになれません。
$N$ 組のペアを作る方法は何通りあるか、$\mathrm{mod}~10^9+7$ で答えなさい。
制約
- $1\le N\le 21$
解法
bitDP と呼ばれる、集合を DP の添え字として持つ手法で解くことができる問題です。
集合を添え字として持つ方法ですが、二進数の $n$ bit めと、$n$ 人目の女性を対応させればいいです。
例えば $\left\{ 0,1,3 \right\}$ という集合は $1011_{\left(2\right)}=11_{\left(10\right)}$ という整数に対応します。
このようにすることで、集合として $S\subset T$ ならば整数として $S\le T$ が成り立つので、for 文で DP を書くことができます。
$dp_{i,S}=$ (男性 $i-1$ までの相手を決め、すでにペアに使った女性の集合が $S$ である場合の数) として、bitDP の遷移を書いてみます。
dp[0][0] = 1;
for(int i = 0; i < N; i++)
for(int S = 0; S < 1 << N; S++)
for(int j = 0; j < N; j++)
if(S >> j & 1 && a[i][j]) {
dp[i + 1][S] += dp[i][S ^ 1 << j];
if(dp[i + 1][S] >= mod) dp[i + 1][S] -= mod;
}
これだと状態数 $O(2^NN)$、遷移 $O(N)$ なので全体で $O(2^NN^2)$ で、間に合いません。
実は、ペアに使った女性と男性の数は常に等しいため、$i$ は $S$ の立っている bit 数から求めることができます。
これを考えると、$i$ のループが要らなくなったので、$O(2^NN)$ で解けます。
実装例
#include <iostream>
using namespace std;
const int mod = 1000000007;
int N;
bool a[21][21];
int dp[1 << 21];
int main() {
cin >> N;
for(int i = 0; i < N; i++)
for(int j = 0; j < N; j++)
cin >> a[i][j];
dp[0] = 1;
for(int S = 1; S < 1 << N; S++) {
int i = __builtin_popcount(S);
for(int j = 0; j < N; j++) {
if(S >> j & 1 && a[i - 1][j] == 1) {
dp[S] += dp[S ^ 1 << j];
dp[S] %= mod;
}
}
}
cout << dp[(1 << N) - 1] << endl;
return 0;
}