Educational DP Contest (EDPC) K ~ O 問題 解説

#はじめに
この記事は、EDPC の K ~ O 問題の解説です。K ~ O 問題を解いてみてから読まれることを推奨します。

- [Educational DP Contest / DP まとめコンテスト - AtCoder](https://atcoder.jp/contests/dp)

また、J 問題までをまだ解いていない方は、下記ページも読んでいただくといいと思います。

- [Educational DP Contest (EDPC) A ~ E 問題 解説](https://qiita.com/Series_205/private/496ef5d97830763dc8e7)
- [Educational DP Contest (EDPC) F ~ J 問題 解説](https://qiita.com/Series_205/private/15191c982f68ad7b98ab)

なお、この記事は基礎的な DP について理解できている人が読む想定で書いているので、上記の記事と比べて解説や実装例が~~適当~~簡潔になっています。

##この記事の続き

- [Educational DP Contest (EDPC) P ~ S 問題 解説](https://qiita.com/Series_205/private/6bad5c32a1fce8dc2914)
- [Educational DP Contest (EDPC) T ~ W 問題 解説](https://qiita.com/Series_205/private/7d2c57b45179006d0bc6)
- [Educational DP Contest (EDPC) X ~ Z 問題 解説](https://qiita.com/Series_205/private/05bd22a4e78527cb29dc)


#[K - Stones](https://atcoder.jp/contests/dp/tasks/dp_k)
##問題
二人でゲームをします。
$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)$ です。

```c++
#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](https://atcoder.jp/contests/dp/tasks/dp_l)
##問題
二人でゲームをします。
$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)$ です。

```c++
#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](https://atcoder.jp/contests/dp/tasks/dp_m)
##問題
$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 をやればよさそうです。実際に書いてみます。

```c++
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 の遷移を数式にしてみると、こうなります。

```math
\displaystyle{dp_{i+1,j}=\sum_{k=\max(0,j-a_i)}^j dp_{i,k}}
```

いかにも累積和が使えそうな形です。実際に累積和を使うと、遷移を $O(1)$ でできるので、全体で $O(NK)$ となり、間に合います。

##実装例
負の整数の mod を取るときは、法を足して正にしてから mod を取ります。

```c++
#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](https://atcoder.jp/contests/dp/tasks/dp_n)
##問題
$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 をループを使って実装したので、ここではメモ化再帰で書きます。
累積和を取らなくても計算量は変わりませんが、実装量等の観点から累積和を取っています。

```c++
#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](https://atcoder.jp/contests/dp/tasks/dp_o)
##問題
男性と女性が $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 の遷移を書いてみます。

```c++
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)$ で解けます。

##実装例

```c++
#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;
}
```

#続き

- [Educational DP Contest (EDPC) P ~ S 問題 解説](https://qiita.com/Series_205/private/6bad5c32a1fce8dc2914)