Educational DP Contest (EDPC) F ~ J 問題 解説

#はじめに
この記事は、[Educational DP Contest (EDPC) A ~ E 問題 解説](https://qiita.com/Series_205/private/496ef5d97830763dc8e7)の続きです。
この記事では F ~ J 問題の解説をします。「は？DP？何それ？？」な方は、上の記事を先に読まれることを強く推奨します。

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

##この記事の続き

- [Educational DP Contest (EDPC) K ~ O 問題 解説](https://qiita.com/Series_205/private/618b6ad1a22e7401a606)
- [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)

##EDPC F ~ J 問題について
E 問題までは DP の典型中の典型といった感じで、基本的な DP がそろっていました。
F ~ J 問題は、文字列や確率など、いろいろな問題で DP が活用できることを学べるエリアになっています。(E までより難易度は高いと思います)
おおまかに難易度順で問題が並んでいると、解く側にとってはとてもありがたいですね。

#[F - LCS](https://atcoder.jp/contests/dp/tasks/dp_f)
##問題
$s$ の部分列かつ $t$ の部分列である文字列のうち、最長のものをひとつ求めてください。
(そのような文字列が複数ある場合は、そのうちの一つを出力すればよい)

##制約

- $s,t$ は英小文字からなる文字列
- $1\le |s|,|t|\le 3000$

##解法
この問題も Knapsack 問題と同様に有名問題で、[最長共通部分列問題](https://ja.wikipedia.org/wiki/%E6%9C%80%E9%95%B7%E5%85%B1%E9%80%9A%E9%83%A8%E5%88%86%E5%88%97%E5%95%8F%E9%A1%8C)として知られています。
LCS は Longest-common subsequence の頭文字で、要するに最長共通部分列です。

一発で LCS を求めることは難しいので、取り敢えず LCS の長さを求め、DP テーブルから LCS を復元する方針を取ります。

###DP パート

$dp_{i,j}=$ $s$ の $i-1$ 文字目、$t$ の $j-1$ 文字目までの LCS の長さ　という DP を考えます。

$dp_{i,j-1},dp_{i-1,j},dp_{i-1,j-1}$ それぞれからの遷移を考えると、

```c++
dp[i][j] = max(dp[i][j], dp[i - 1][j]);
dp[i][j] = max(dp[i][j], dp[i][j - 1]);
if(s[i - 1] == t[j - 1]) dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
```

となります。

###復元パート

LCS の復元にはいくつか方法があると思いますが、ここでは、DP テーブル上で DP の遷移を巻き戻して復元する方法を取ります。
$dp_{|s|,|t|}$ からはじめて、$dp_{i,j}$ はどこから遷移してきたかを特定し、遷移を逆順にたどります。

```c++
int i = s.size();
int j = t.size();
string res;
while(i > 0 && j > 0) {
    if(dp[i][j] == dp[i - 1][j])
        i--;
    else if(dp[i][j] == dp[i][j - 1])
        j--;
    else {
        i--;
        j--;
        res.push_back(s[i]);
    }
}
reverse(res.begin(), res.end());
```

##実装例
計算量は $O(|s|\times|t|)$ です。

```c++
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;

string s, t;
int dp[3009][3009];

int main() {
    cin >> s >> t;

    for(int i = 1; i <= s.size(); i++) {
        for(int j = 1; j <= t.size(); j++) {
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            if(s[i - 1] == t[j - 1])
                dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
        }
    }

    int i = s.size();
    int j = t.size();
    string res;
    while(i > 0 && j > 0) {
        if(dp[i][j] == dp[i - 1][j])
            i--;
        else if(dp[i][j] == dp[i][j - 1])
            j--;
        else {
            i--;
            j--;
            res.push_back(s[i]);
        }
    }
    reverse(res.begin(), res.end());

    cout << res << endl;

    return 0;
}
```

#[G - Longest Path](https://atcoder.jp/contests/dp/tasks/dp_g)
##問題
$N$ 頂点 $M$ 辺の重みなし有向グラフ $G$ が与えられます。
$G$ は有向閉路を含みません。すなわち、$G$ は[DAG](https://ja.wikipedia.org/wiki/%E6%9C%89%E5%90%91%E9%9D%9E%E5%B7%A1%E5%9B%9E%E3%82%B0%E3%83%A9%E3%83%95)です。
$G$ の有向パスの長さの最大値を求めてください。

##制約

- $2\le N\le 10^5$
- $1\le M\le 10^5$

##解法
文字列の DP に続いて、グラフに対する DP です。

$dp_i=$ $i$ を始点とする有向パスの長さの最大値　として DP すればよさそうです。

一見楽勝に見えますが、よく考えると、DP をどういう順番で更新していけばいいのかわからなくないですか？ちなみに僕はわかります 。(わからないで解説してたら、やばいので)

このように DP を更新する順番がわからない場合、メモ化再帰がとっても役に立ちます。(実際に書いてみると分かります)

##実装例
計算量は $O(N+M)$ です。

```c++
#include <iostream>
#include <vector>
using namespace std;

int N, M, dp[100009];
vector<int> G[100009];

int solve(int u) {
    if(dp[u] == -1) {
        dp[u] = 0;
        for(int v : G[u])
            dp[u] = max(dp[u], solve(v) + 1);
    }
    return dp[u];
}

int main() {
    cin >> N >> M;
    for(int i = 0; i < M; i++) {
        int x, y;
        cin >> x >> y;
        x--;
        y--; // 0-indexed にする
        G[x].push_back(y);
    }

    for(int i = 0; i < N; i++)
        dp[i] = -1;

    int res = -1;
    for(int i = 0; i < N; i++)
        res = max(res, solve(i));

    cout << res << endl;

    return 0;
}
```

##実装例其の二
「俺は再帰関数なんて書きたくない！」という方、ご安心ください。トポロジカルソートすれば、再帰関数を書くことなく実装できます。
メモ化再帰のほうが楽だと思うので、基本的にはメモ化再帰をお勧めします。

```c++
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int N, M, dp[100009], in[100009];
vector<int> G[100009];

int main() {
    cin >> N >> M;
    for(int i = 0; i < M; i++) {
        int x, y;
        cin >> x >> y;
        x--;
        y--; // 0-indexed にする
        G[x].push_back(y);
        in[y]++;
    }

    queue<int> que;
    for(int i = 0; i < N; i++)
        if(in[i] == 0) que.push(i);

    while(!que.empty()) {
        int u = que.front();
        que.pop();
        for(int v : G[u])
            if(--in[v] == 0) {
                que.push(v);
                dp[v] = dp[u] + 1;
            }
    }

    int res = 0;
    for(int i = 0; i < N; i++)
        res = max(res, dp[i]);

    cout << res << endl;

    return 0;
}
```


#[H - Grid 1](https://atcoder.jp/contests/dp/tasks/dp_h)
##問題
$H$ 行 $W$ 列のグリッドが与えられる。
右か下への移動のみで、壁のマスを通らずに $(0,0)$ から $(H-1,W-1)$ まで行く方法は何通りあるかを、$10^9+7$ で割ったあまりを求めてください。

##制約

- $2\le H,W \le 1000$

##解法
グリッド上の数え上げの問題ですが、これも DP で解くことができます。

$dp_{i,j}=$ $(i,j)$に到達する通り数　で DP ができそうです。

数え上げ DP に関しては、初期化を $dp_{i,j}=0$、初期状態の値 (この問題では $dp_{0,0}$ ) $=1$ として、
遷移は $+$ 演算を用いることが理解できていればいいと思います。

##実装例
計算量は $O(HW)$ です。

```c++
#include <iostream>
using namespace std;

const int mod = 1000000007;

int H, W;
int ok[1009][1009];
int dp[1009][1009];

int main() {
    cin >> H >> W;
    for(int i = 0; i < H; i++)
        for(int j = 0; j < W; j++) {
            char c;
            cin >> c;
            ok[i][j] = (c == '.'); // 壁なら 0, そうでないなら 1
        }

    dp[0][0] = 1;
    for(int i = 0; i < H; i++) {
        for(int j = !i; j < W; j++) {
            if(i) dp[i][j] += dp[i - 1][j];
            if(j) dp[i][j] += dp[i][j - 1];
            dp[i][j] *= ok[i][j];
            dp[i][j] %= mod;
        }
    }

    cout << dp[H - 1][W - 1] << endl;

    return 0;
}
```

#[I - Coins](https://atcoder.jp/contests/dp/tasks/dp_i)
##問題
$N$ 枚のコインがあります。
$i$ 番目のコインを投げると、確率 $p_i$ で表が、確率 $1-p_i$ で裏が出ます。
$N$ 枚全てのコインを投げて、表の個数が裏の個数を上回る確率を求めてください。

##制約

- $N$ は奇数である
- $1\le N\le 2999$
- $0<p_i<1$

##解法
$N$ 枚のコインを投げ終わった時に、表が $j$ 枚である確率がわかれば、$j>\frac{N}{2}$ の範囲でそれを足したものが答えです。

このことから、「次に投げるのが $i$ 番目で、表が $j$ 枚の確率」という DP で解けそうです。
$dp_{i,j}$ からは、確率 $p_{i}$ で $dp_{i+1,j+1}$ に、確率 $1-p_{i}$ で $dp_{i+1,j}$ に遷移します。
この遷移は次のように書けます。

```C++
dp[i + 1][j + 1] += dp[i][j] * p[i];
dp[i + 1][j] += dp[i][j] * (1 - p[i]);
```

##実装例
計算量は $O(N^2)$ です。
小数は、十分な精度で出力しましょう。誤差が $10^{-9}$ より大きいと WA にされてしまいます。

```c++
#include <iomanip>
#include <iostream>
using namespace std;

int N;
double p[3009];
double dp[3009][3009];

int main() {
    cin >> N;
    for(int i = 0; i < N; i++)
        cin >> p[i];

    dp[0][0] = 1;

    for(int i = 0; i < N; i++) {
        // j > i となることはないので、このような条件式にしている。
        // j <= N でも構わない。
        for(int j = 0; j <= i; j++) {
            dp[i + 1][j + 1] += dp[i][j] * p[i];
            dp[i + 1][j] += dp[i][j] * (1 - p[i]);
        }
    }

    double res = 0;
    for(int j = (N + 1) / 2; j <= N; j++)
        res += dp[N][j];

    cout << fixed << setprecision(10) << res << endl;

    return 0;
}
```

#[J - Sushi](https://atcoder.jp/contests/dp/tasks/dp_j)
##問題
$N$ 枚の皿があり、最初 $i$ 番目の皿には $a_i$ 個の寿司があります。
全ての皿から寿司がなくなるまで、以下の操作を繰り返します。

- 皿を等確率で選ぶ。皿 $i$ に寿司がある場合は皿 $i$ の寿司を $1$ 個食べる。

操作回数の期待値を求めてください。

##制約

- $1\le N\le 300$
- $1\le a_i\le 3$

##解法
これを DP で解こうとしたとき、「皿 $0$ に $a$ 個、皿 $1$ に $b$ 個、...... 皿 $N-1$ に $z$ 個寿司がある状態」という DP を考えてしまうと、状態数が $O(4^N)$ となります。間に合うわけがありません。

$a_i$ が小さいことに注目して、「残り $i$ 個の皿が $c_i$ 枚」という形で考えると、DP の状態数が $O(N^3)$ となり、間に合いそうです。($c_0$ は $N,c_1,c_2,c_3$ から計算できるので、添え字に持つ必要はありません。)

上記の状態から食べ終わるまでの操作回数の期待値を $dp_{c_1,c_2,c_3}$ で表すことにして、漸化式を立ててみます。

```math
dp_{c_1,c_2,c_3}=1+\frac{c_0}{N}dp_{c_1,c_2,c_3}+\frac{c_1}{N}dp_{c_1-1,c_2,c_3}+\frac{c_2}{N}dp_{c_1+1,c_2-1,c_3}+\frac{c_3}{N}dp_{c_1,c_2+1,c_3-1}
```

右辺に $dp_{c_1,c_2,c_3}$ があるので、移項して整理します。

```math
\begin{align}
dp_{c_1,c_2,c_3}&=\left(\frac{N}{N-c_0}\right)\left( 1+\frac{c_1}{N}dp_{c_1-1,c_2,c_3}+\frac{c_2}{N}dp_{c_1+1,c_2-1,c_3}+\frac{c_3}{N}dp_{c_1,c_2+1,c_3-1} \right)\\
&=\frac{N+c_1dp_{c_1-1,c_2,c_3}+c_2dp_{c_1+1,c_2-1,c_3}+c_3dp_{c_1,c_2+1,c_3-1}}{c_1+c_2+c_3}
\end{align}
```

##実装例
この遷移は複雑でループで書くのは難しいので、メモ化再帰で書きます。
計算量は状態数と同じで $O(N^3)$ です。

```c++
#include <iomanip>
#include <iostream>
using namespace std;

int N;
int c[4];

double dp[310][310][310];

double solve(int c1, int c2, int c3) {
    if(c1 == 0 && c2 == 0 && c3 == 0) return 0;
    if(dp[c1][c2][c3] > 0) return dp[c1][c2][c3];

    double res = N;
    if(c1 >= 1) res += solve(c1 - 1, c2, c3) * c1;
    if(c2 >= 1) res += solve(c1 + 1, c2 - 1, c3) * c2;
    if(c3 >= 1) res += solve(c1, c2 + 1, c3 - 1) * c3;
    res /= c1 + c2 + c3;
    return dp[c1][c2][c3] = res;
}

int main() {
    cin >> N;
    for(int i = 0; i < N; i++) {
        int a;
        cin >> a;
        c[a]++;
    }

    cout << fixed << setprecision(10) << solve(c[1], c[2], c[3]) << endl;

    return 0;
}
```

#続き

- [Educational DP Contest (EDPC) K ~ O 問題 解説](https://qiita.com/Series_205/private/618b6ad1a22e7401a606)