LoginSignup
4
4

More than 3 years have passed since last update.

@Series_205

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

Last updated at Posted at 2020-04-03

はじめに

この記事は、Educational DP Contest (EDPC) A ~ E 問題 解説の続きです。
この記事では F ~ J 問題の解説をします。「は？DP？何それ？？」な方は、上の記事を先に読まれることを強く推奨します。

この記事の続き

EDPC F ~ J 問題について

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

F - LCS

問題

$s$ の部分列かつ $t$ の部分列である文字列のうち、最長のものをひとつ求めてください。
(そのような文字列が複数ある場合は、そのうちの一つを出力すればよい)

制約

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

解法

この問題も Knapsack 問題と同様に有名問題で、最長共通部分列問題として知られています。
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}$ それぞれからの遷移を考えると、

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}$ はどこから遷移してきたかを特定し、遷移を逆順にたどります。

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|)$ です。

#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

問題

$N$ 頂点 $M$ 辺の重みなし有向グラフ $G$ が与えられます。
$G$ は有向閉路を含みません。すなわち、$G$ はDAGです。
$G$ の有向パスの長さの最大値を求めてください。

制約

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

解法

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

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

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

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

実装例

計算量は $O(N+M)$ です。

#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;
}

実装例其の二

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

#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

問題

$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)$ です。

#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

問題

$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}$ に遷移します。
この遷移は次のように書けます。

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 にされてしまいます。

#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

問題

$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}$ で表すことにして、漸化式を立ててみます。

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}$ があるので、移項して整理します。

\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)$ です。

#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;
}

続き

4
4
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
4
4