#はじめに
この記事は、Educational DP Contest (EDPC) A ~ E 問題 解説の続きです。
この記事では F ~ J 問題の解説をします。「は？DP？何それ？？」な方は、上の記事を先に読まれることを強く推奨します。
##この記事の続き
- Educational DP Contest (EDPC) K ~ O 問題 解説
- Educational DP Contest (EDPC) P ~ S 問題 解説
- Educational DP Contest (EDPC) T ~ W 問題 解説
- Educational DP Contest (EDPC) X ~ Z 問題 解説
##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;
}
#続き