#はじめに
この記事は、EDPC の P ~ S 問題の解説です。P ~ S 問題を解いてみてから読まれることを推奨します。
O 問題までを解いていない方は、これらの記事も読まれるといいと思います。
- Educational DP Contest (EDPC) A ~ E 問題 解説
- Educational DP Contest (EDPC) F ~ J 問題 解説
- Educational DP Contest (EDPC) K ~ O 問題 解説
##この記事の続き
#P - Independent Set
##問題
$N$ 頂点の木の各頂点を白黒に塗り分ける方法が何通りあるか、$\mod{10^9+7}$ で求めてください。
ただし、黒で塗った頂点は隣り合ってはいけません。
##制約
- $1\le N\le 10^5$
##解法
適当な頂点を根として、根付き木として考えます。
根付き木の各頂点について、その頂点の子についての情報から DP テーブルの値を更新していく DP は木 DP と呼ばれています。
頂点 $u$ を頂点とする部分木について、この問題と同じ問題を解くことを考えます。
$u$ に塗る色で場合分けをして考えてみます。
- $u$ を白で塗る場合、$u$ の子は白黒どちらも塗ることができます。
- $u$ を黒で塗る場合、$u$ の子は白で塗らなければなりません。
このことから、$u$ を白で塗った時の題意を満たす通り数 $w_u$ と、黒で塗った時の通り数 $b_u$ を DP としてテーブルに保存しておけば解けます。
##実装例
「メモ化再帰」と言っても木上の DFS で各頂点にアクセスするのは $1$ 回だけなので、実質ただの再帰みたいなところはあります。(DP テーブル無しでも実装することができます。ぜひ挑戦してみましょう。)
計算量は $O(N)$ です。
#include <iostream>
#include <vector>
using namespace std;
const int mod = 1000000007;
int N;
vector<int> G[100009];
long long white[100009], black[100009];
void dfs(int u, int p) {
black[u] = 1;
white[u] = 1;
for(int v : G[u]) {
if(v == p) continue; // 親に帰る辺は無視
dfs(v, u);
black[u] *= white[v];
black[u] %= mod;
white[u] *= white[v] + black[v];
white[u] %= mod;
}
}
int main() {
cin >> N;
for(int i = 0; i < N - 1; i++) {
int x, y;
cin >> x >> y;
x--;
y--; // 0-indexed にする
G[x].push_back(y);
G[y].push_back(x);
}
dfs(0, -1);
cout << (black[0] + white[0]) % mod << endl;
return 0;
}
この問題は LIS (最長増加部分列問題) の応用問題です。基本的な LIS の問題を置いておきます。
- JOI2007 春合宿 - Building $($ $O(N^2)$ が通ります$)$
- AOJ DPL_1_D 最長増加部分列 $($ $O(N^2)$ は通りません$)$
##問題
$N$ 本の花が並んでいます。
左から $i$ 番目の花の高さは $h_i$ で美しさは $a_i$ です。
何本かの花を取り除き、次の条件が成り立つようにします。
- 残った花を左から見ると、高さが単調増加である
残った花の美しさの総和の最大値を求めてください。
##制約
- $1\le N\le 2\times10^5$
- $1\le h_i\le N$
- $h_i$ は全て相異なる
##解法
左の花から順に、残すかどうかを決めていくことを考えます。
花を残すことができるかは直前に残した花の高さに依存するので、
$dp_{i,j}=$ ($i$個の花を見て、最後に残した花の高さが $j$ である状態の、美しさの総和の最大値)
とすると解けそうですが、計算量が $O(N^2)$ で、時間もメモリも足りません。
メモリが足りない問題
$dp_{i,j}$ と $dp_{i+1,j}$ の差分について考えると、変化しているのは $dp_{i+1,h_i}$ だけであることがわかります。
一次元配列を使いまわすことで、メモリの問題は解決されました。
時間計算量の問題
遷移を数式で書いてみると、$dp_{h_i}=a_i+\max(dp_j)\{j<h_i\}$であり、区間の最大値を高速に求める必要があります。
区間に対する高速な操作と言えば、そう、Segment Tree です。
一点更新区間 max の Segment Tree を使えば、この遷移が $O(\log{N})$ 時間で可能なので、全体で $O(N\log{N})$ 時間となり、時間計算量の問題も、解決できました。
##実装例
この問題の場合は Segment Tree ではなく BIT でも実装可能です。BIT のほうが実装が簡単で定数倍も軽いので、BIT で事足りる場面では BIT を使った方がいいと思います。
#include <iostream>
using namespace std;
int N;
int h[200009];
int a[200009];
// BIT (1-indexed)
long long bit[200009];
void update(int a, long long k) {
for(; a <= N; a += a & -a)
bit[a] = max(bit[a], k);
}
long long query(int a) {
long long res = 0;
for(; a > 0; a -= a & -a)
res = max(res, bit[a]);
return res;
}
int main() {
cin >> N;
for(int i = 0; i < N; i++)
cin >> h[i];
for(int i = 0; i < N; i++)
cin >> a[i];
for(int i = 0; i < N; i++)
update(h[i], query(h[i]) + a[i]);
cout << query(N) << endl;
return 0;
}
#R - Walk
##問題
$N$ 頂点の単純有向グラフ $G$ が与えられます。
$G$ の長さ $K$ の有向パスの数を $\mod 10^9+7$ で求めてください。
##制約
- $1\le N \le 50$
- $1\le K\le 10^{18}$
##解法
$dp_{l,i,j}=$ ($i$ から$j$ までの、長さ $l$ の有向パスの個数) という DP をすることを考えます。
この DP の遷移を考えると、$dp_{l,i,j}=\sum_kdp_{l-1,i,k}\times a_{k,j}$ となります。
この DP をこのまま実装すると、計算量が $O(N^3K)$ で、当然 TLE します。
この遷移式を睨んでいると、行列の掛け算ととても似ていることに気が付きます。(これは多分相当気づきにくいので、知らないで解けたらすごいと思います。)
$dp_{l,i,j}$ を $(i,j)$ 成分とする行列 $DP_l$ とみなすと、遷移式は $DP_l=DP_{l-1}\times A$ となります。
$DP_0$ は明らかに単位行列なので、$DP_l=A^l$ であることがわかります。
これは繰り返し自乗法を用いて $O(N^3\log{K})$ で計算できるので、この問題も $O(N^3\log{K})$ で解くことができます。
##実装例
#include <iostream>
#include <vector>
using namespace std;
using matrix = vector<vector<long long>>;
const int mod = 1000000007;
int N;
long long K;
matrix A;
// 行列の掛け算
matrix mul(matrix &a, matrix &b) {
matrix res(N, vector<long long>(N, 0));
for(int i = 0; i < N; i++)
for(int j = 0; j < N; j++)
for(int k = 0; k < N; k++)
(res[i][j] += a[i][k] * b[k][j]) %= mod;
return res;
}
// 行列累乗
matrix pow(matrix m, long long k) {
matrix res(N, vector<long long>(N, 0));
for(int i = 0; i < N; i++)
res[i][i] = 1; // 単位行列にする
while(k > 0) {
if(k & 1) res = mul(res, m);
m = mul(m, m);
k >>= 1;
}
return res;
}
int main() {
cin >> N >> K;
A.assign(N, vector<long long>(N));
for(int i = 0; i < N; i++)
for(int j = 0; j < N; j++)
cin >> A[i][j];
A = pow(A, K);
long long res = 0;
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
res += A[i][j];
res %= mod;
}
}
cout << res << endl;
return 0;
}
#S - Digit Sum
##問題
$1$ 以上 $K$ 以下の整数で、十進法での桁和が $D$ の倍数であるものの個数を、$\mod{10^9+7}$ で答えてください。
##制約
- $1\le K<10^{10000}$
- $1\le D\le 100$
##解法
桁 DP と呼ばれる、典型的な問題の一つです。
$dp_{i,j,d}=$ (上から $i$ 桁決めて、$K$ より小さいことが確定してるかの bool 値が $j$ で、桁和$\mod{D}$ が $d$ である数)
という DP を考えます。
「唐突にそんなの思いつかない」と思うかもしれませんが、桁 DP は大体この形なので、本質は $d$ の取り方だけです。
(たまに下の桁から決める場合や、$j$ のようなものを複数持たないといけない問題もありますが、逆に言えばその程度です。)
遷移は、よく考えると実装例のようになります。(手を抜くな)
##実装例
$K$ は整数型では大きすぎて受け取れないので、文字列として受け取りましょう。
計算量は $O(D\log{K})$ です。
#include <iostream>
#include <string>
using namespace std;
const int mod = 1000000007;
// K の桁数
int N;
int D;
// K の上から n 桁目 (0-indexed)
int K[10009];
int dp[10009][2][109];
int main() {
string s;
cin >> s;
N = s.size();
for(int i = 0; i < N; i++)
K[i] = s[i] - '0';
cin >> D;
dp[0][0][0] = 1;
for(int i = 0; i < N; i++) {
for(int d = 0; d < D; d++) {
// j = 1 -> j = 1
for(int k = 0; k <= 9; k++) {
dp[i + 1][1][(d + k) % D] += dp[i][1][d];
dp[i + 1][1][(d + k) % D] %= mod;
}
// j = 0 -> j = 1
for(int k = 0; k < K[i]; k++) {
dp[i + 1][1][(d + k) % D] += dp[i][0][d];
dp[i + 1][1][(d + k) % D] %= mod;
}
// j = 0 -> j = 0
dp[i + 1][0][(d + K[i]) % D] += dp[i][0][d];
dp[i + 1][0][(d + K[i]) % D] %= mod;
}
}
// 0 が含まれているので、1 引く
int res = (dp[N][0][0] + dp[N][1][0] - 1 + mod) % mod;
cout << res << endl;
return 0;
}
#続き