はじめに
こんにちは！L_Gravityという者です！
EDPCという動的計画法（アルゴリズムの一種）の学習コンテストをたまたま見つけましたので、学習しながらノートをとっている状態です。つまり、めちゃくちゃ雑 ということです。雑な代わりに、最低限の解説が一か所にまとまっていることを利用して、ヒントや解き方ライブラリとして利用してください。（まぁコードも不親切ではある）
あと競プロはは強くなくても楽しめていいですねぇ・・・
ただしこの記事は、少しはDPに慣れている方が読むことを推奨します。（解説が雑なので）
多分中盤と終盤もやるのですが、実力的に瞬殺できるのが前半までな気がしてる
解答&解説集
A 普通のDP
解法
はい。
コード（C++）
ll N;
ll H[100009];
ll dp[100009];
int main() {
fastio;
cin >> N;
rep(i, N)cin >> H[i];
dp[1] = 0;
dp[2] = abs(H[1] - H[2]);
for (int i = 3; i <= N;i++) dp[i] = min(dp[i - 1] + abs(H[i] - H[i - 1]),
dp[i - 2] + abs(H[i] - H[i - 2]));
cout << dp[N] << endl;
}
B 配る漸化式
解法
はい。
コード（C++）
ll N, K;
ll H[100009];
ll dp[100009];
int main() {
fastio;
cin >> N >> K;
rep(i, N)cin >> H[i];
rep(i, N)dp[i] = 100000000009;
dp[1] = 0;
rep(i, N) {
rep(j, K) {
if (i + j <= N) {
dp[i + j] = min(dp[i] + abs(H[i + j] - H[i]), dp[i + j]);
}
}
}
cout << dp[N] << endl;
}
C 選択肢DP
解法
$dp$ 配列を $dp[100009][3];$ とし、一番最後に選んでたやつをメモる
だいたいこれ系が出てきたら、保存すべき情報を考える！
コード（C++）
ll N;
ll a[100009];
ll b[100009];
ll c[100009];
ll dp[100009][3];
int main() {
fastio;
cin >> N;
rep(i, N)cin >> a[i] >> b[i] >> c[i];
rep(i, N) {
dp[i][0] = max(dp[i - 1][1], dp[i - 1][2]) + a[i];
dp[i][1] = max(dp[i - 1][0], dp[i - 1][2]) + b[i];
dp[i][2] = max(dp[i - 1][1], dp[i - 1][0]) + c[i];
}
cout << max(dp[N][2], max(dp[N][0], dp[N][1])) << endl;
}
Dナップザック①
解法
はい
コード（C++）
ll N, W;
ll w[109];
ll v[109];
ll dp[109][100009];
int main() {
fastio;
cin >> N >> W;
rep(i, N)cin >> w[i] >> v[i];
rep(i, N) {
rep(j, W) {
if (j - w[i] >= 0) {
dp[i][j] = max(dp[i - 1][j - w[i]] + v[i], dp[i - 1][j]);
}
else dp[i][j] = dp[i - 1][j];
}
}
ll K = 0;
rep(i, W) K = max(K, dp[N][i]);
cout << K << endl;
}
Eナップザック②
解法
普通にデータの持ち方を変える
DPの初期化に注意
コード（C++）
ll N, W;
ll w[109];
ll v[109];
ll dp[109][100009];
int main() {
fastio;
cin >> N >> W;
rep(i, N)cin >> w[i] >> v[i];
rez(i, N + 1) {
rez(j, 100009) dp[i][j] = 10000000000000000;
}
dp[0][0] = 0;
rez(i, N + 1) dp[i][0] = 0;
rep(i, N) {
rep(j, 100009) {
if (j - v[i] >= 0) {
dp[i][j] = min(dp[i - 1][j - v[i]] + w[i], dp[i - 1][j]);
}
else dp[i][j] = dp[i - 1][j];
}
}
ll K = 0;
rep(i, 100008) {
if (dp[N][i] <= W) K = i;
}
cout << K << endl;
}
F LCS＆復元
解法
普通にLCS⇒逆から復元
基本的にDPの復元は逆から！！（whileの終了条件に注意）
コード（C++）
string S, T;
ll dp[3009][3009];
int main() {
fastio;
cin >> S >> T;
rep(i, size(S)) {
rep(j, size(T)) {
dp[i][j] = -1145141919810;
}
}
rep(i, size(S)) {
rep(j, size(T)) {
if (S[i - 1] == T[j - 1]) {
dp[i][j] = max(max(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1] + 1);
}
else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
//復元
ll I = size(S);
ll J = size(T);
vector<char>C;
while (true) {
if ((S[I - 1] == T[J - 1]) && dp[I][J] - 1 == dp[I - 1][J - 1]) {
C.pb(S[I - 1]);
I--; J--;
}
else if (dp[I][J] == dp[I - 1][J]) I--;
else if (dp[I][J] == dp[I][J - 1]) J--;
if (I == 0 || J == 0) {
reverse(all(C));
rez(i, size(C))cout << C[i];
cout << endl;
return 0;
}
}
}
G DAG上のDP
解法①トポロジカルソート
普通にトポロジカルソートしながらBFSのように解く
解法②メモ化再帰
メモ化再帰ができる。体感DFSみたいな感じ
DP の更新順序が非自明な場合はメモ化再帰が使える！！
コード（C++）
ll N, M;
ll x[100009];
ll y[100009];
ll dp[100009];
set<ll>GS[100009];
set<ll>RGS[100009];
int main() {
fastio;
cin >> N >> M;
rep(i, M) {
cin >> x[i] >> y[i];
GS[x[i]].insert(y[i]);
RGS[y[i]].insert(x[i]); //トポロジカルソートするので逆
}
queue<ll>Q;
//出次数0
rep(i, N) {
if (size(GS[i]) == 0) {
Q.push(i);
dp[i] = 0;
}
}
//出次数0から処理ぃ
while (!Q.empty()) {
while (!RGS[Q.front()].empty()) {
ll k = *RGS[Q.front()].begin();
RGS[Q.front()].erase(k);
dp[k] = max(dp[Q.front()] + 1, dp[k]);
GS[k].erase(Q.front());
if (size(GS[k]) == 0) Q.push(k);
}
Q.pop();
}
//---トポロジカルソートおわり---
ll Ans = -1;
rep(i, N) Ans = max(Ans, dp[i]);
cout << Ans << endl;
}
H 場合の数のDP
解法
受験算数でおなじみの、両方の端を考えてやるやつ
普通にGより簡単だと思う
漸化式にすると、
$dp[i][j] = dp[i - 1][j] + dp[i][j - 1]$
場合の数に関する問題もDPが使える！！
コード（C++）
ll H, W;
char A[1009][1009];
ll dp[1009][1009];
int main() {
fastio;
cin >> H >> W;
rep(i, H) {
rep(j, W) cin >> A[i][j];
}
dp[1][1] = 1;
rep(i, H) {
rep(j, W) {
if (i == 1 && j == 1) continue;
if (A[i][j] == '.') dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % 1000000007;
}
}
cout << dp[H][W] << endl;
}
I 確率DP
解法
これも受験数学でおなじみな気がする。
$dp[3000][3000]$ は、 $dp[コイン投げた回数][当たり]$
今回は配る漸化式で、
$dp[i + 1][j + 1] += dp[i][j] × P[i + 1]$ //表
$dp[i + 1][j] += dp[i][j] × (1.0 - P[i + 1])$ //裏
確率に関する問題もDPが使える！！
コード（C++）
ll N;
double P[3000];
double dp[3000][3000];
int main() {
fastio;
cin >> N;
rep(i, N)cin >> P[i];
dp[0][0] = 1;
rez(i, N) {
rez(j, i + 1) {
dp[i + 1][j] += dp[i][j] * (1.0 - P[i + 1]);
dp[i + 1][j + 1] += dp[i][j] * P[i + 1];
}
}
double P = 0;
rep(i, N) {
if (i > (N - i)) P += dp[N][i];
}
cout << P << endl;
}
J 期待値DP（超強化版）
解法
今までの問題セットはお遊びだったと言っても過言ではないレベルの問題。簡単なABC-Fにあってもおかしくない？
考察ステップ１ 区別しない
問題の性質から、別に今回は各皿を区別しなくてもいいんじゃね？となる. つまり, 寿司が $n$ 個の皿が $i$ 枚ってのを考えればいい.
そこで, DP配列を,
$dp[i][j][k] = （[1枚の皿の枚数][2枚][3枚]の状態から寿司をなくすまでの操作回数の期待値）$
とする.
考察ステップ２ 漸化式を立てる
それぞれへの遷移確立は皿の枚数によって導かれるので,いったん漸化式を立てると,
$$ {{\rm dp[i][j][k] = (dp[i][j][k] × \frac{N-i-j-k}{N} + dp[i-1][j][k] × \frac{i}{N} + dp[i+1][j-1][k] × \frac{j}{N} + dp[i][j+1][k-1] × \frac{k}{N}) + 1}
} $$
ここで, $dp[i][j][k]$ がダブってるのでこれを変形して,
$$ {{\rm dp[i][j][k] \
= (dp[i-1][j][k] × \frac{i}{N} + dp[i+1][j-1][k] × \frac{j}{N} + dp[i][j+1][k-1] × \frac{k}{N} + 1) × \frac{N}{i+j+k} \
= (dp[i-1][j][k] × i + dp[i+1][j-1][k] × j + dp[i][j+1][k-1] × k + N) × \frac{1}{i+j+k}}
}$$
あとはこれを実装するだけ
時には式変形でゴリ押すことはある！！
コード（C++）
ll N;
ll A[309];
// 一枚, 二枚, 三枚
double dp[309][309][309];
ll G[4];
double DP(ll i, ll j, ll k) {
if (dp[i][j][k] != -1) return dp[i][j][k];
double Res = 0.0;
if (i > 0) Res += (DP(i - 1, j, k) * i) / N;
if (j > 0) Res += (DP(i + 1, j - 1, k) * j) / N;
if (k > 0) Res += (DP(i, j + 1, k - 1) * k) / N;
Res += 1;
Res = Res * N / (i + j + k);
return dp[i][j][k] = Res;
}
int main() {
fastio;
cin >> N;
rep(i, N) {
cin >> A[i];
G[A[i]]++;
}
rez(i, N + 1) {
rez(j, N + 1) {
rez(k, N + 1) dp[i][j][k] = -1;
}
}
dp[0][0][0] = 0.0;
cout << DP(G[1], G[2], G[3]) << endl;
}
最後に
序盤編は以上です！ぱっと見まだ簡単な問題が多いですね。 J 以外は瞬殺教室だった気がしてます。（Gはちょっと難しかったかもと思ってる...）
ということで、以後後半を解いていくのですが、難易度の上がり方的に全然死にそうだわ。
ご閲覧頂きありがとうございました！