はじめに

この記事は、EDPC の P ~ S 問題の解説です。P ~ S 問題を解いてみてから読まれることを推奨します。

Educational DP Contest / DP まとめコンテスト - AtCoder

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

Q - Flowers

この問題は 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;
}

続き

Educational DP Contest (EDPC) T ~ W 問題解説

Educational DP Contest (EDPC) P ~ S 問題 解説