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

#はじめに
この記事は、EDPC の T ~ W 問題の解説です。T ~ W 問題を解いてみてから読まれることを推奨します。

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

S 問題までを解いていない方は、これらの記事も読まれるといいと思います。

• Educational DP Contest (EDPC) A ~ E 問題 解説
• Educational DP Contest (EDPC) F ~ J 問題 解説
• Educational DP Contest (EDPC) K ~ O 問題 解説
• Educational DP Contest (EDPC) P ~ S 問題 解説

##この記事の続き

• Educational DP Contest (EDPC) X ~ Z 問題 解説

#T - Permutation

##問題
不等号 '<'、'>' からなる $N-1$ 文字の文字列 $s$ が与えられます。
$1$ ～ $N$ の順列 $p$ であって、$p_i$ と $p_{i+1}$ の大小関係が $s_i$ と一致するものは何通りあるか、$\mod{10^9+7}$ で求めてください。

##制約

• $2\le N\le 3000$

##解法
$p_0$ ～ $p_{i-1}$ を既に決めていて、次に $p_i$ を決めるという場面のことを考えます。
よく考えると、実は $p_{i-1}$ より大きい数がいくつ残っているかがわかればよく、$p_i$ 以降の決め方は残っている要素一つひとつには依存しないことがわかります。
この考察をもとに DP の漸化式を考えます。

$dp_{i,j}=$ (次に決めるのが $p_i$ で、$p_{i-1}$ より大きい数が $j$ 個残っている状態の場合の数) と定義すると、遷移は次のようになります。

dp_{i+1,j} = \left\{
\begin{array}{ll}
\sum_{k=j+1}^{N-1-i} dp_{i,k} & (s_i = \; "<") \\
\sum_{k=0}^{j}       dp_{i,k} & (s_i = \; ">")
\end{array}
\right.

この DP は M 問題と同様に、累積和を使うことで $O(N^2)$ で実装できます。

##実装例

#include <iostream>
#include <string>
using namespace std;

const int mod = 1000000007;

int N;
string s;

long long dp[3009][3009];

int main() {
    cin >> N >> s;

    for(int j = 0; j < N; j++)
        dp[0][j] = 1;

    for(int i = 0; i < N - 1; i++) {
        // 累積和
        int sum[3009];
        sum[0] = 0;
        for(int j = 0; j < N - i; j++)
            sum[j + 1] = (sum[j] + dp[i][j]) % mod;

        if(s[i] == '<') {
            for(int j = 0; j < N - i; j++)
                // 負の mod に気を付ける
                dp[i + 1][j] = (sum[N - i] - sum[j + 1] + mod) % mod;
        }
        if(s[i] == '>') {
            for(int j = 0; j < N - i; j++)
                dp[i + 1][j] = sum[j + 1];
        }
    }

    cout << dp[N - 1][0] << endl;

    return 0;
}

#U - Grouping
##問題
$N$ 羽のウサギをグループ分けします。
ウサギ $i,j$ が同じグループに属するとき、$a_{i,j}$ 点を得ます。
点数の最大値を求めてください。

##制約

• $1\le N\le 16$

##解法
bitDP で解けそうですね。
$dp_S=$ (集合 $S$ をいくつかのグループに分けたときの点数の最大値) とします。
集合 $S$ による点数を $f(S)$ とすると、$dp_S=\max(f(S),dp_T+dp_{S\setminus T})$ と書けます。
$S$ の部分集合 $T$ を列挙するには、次のようにすればいいです。

for(int T = S; T > 0; T = T - 1 & S) 

これで $S$ の部分集合を列挙できることは、for文の動きを追えば容易に確かめられます。
$1$ を引くことは、一番下の立っているビットを $0$ にして、それより下のビットをすべて $1$ にすることと同じであると考えると分かりやすいです。

計算量解析
各集合 $S$ について、その部分集合の数に比例した計算時間がかかります。
$S$ の要素数を $|S|$ とすると、部分集合の数は $O(2^{|S|})$ なので、$\sum 2^{|S|}$を求めればいいです。

\begin{align}
\sum 2^{|S|} &=\sum_k 2^k\times \tbinom{N}{k} \\
&=(2+1)^N=3^N
\end{align}

より、この解法の計算量は $O(3^N)$ であることがわかりました。これは十分高速です。

##実装例

#include <iostream>
using namespace std;

int N;
int a[20][20];

long long dp[1 << 16];

int main() {
    cin >> N;
    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
            cin >> a[i][j];

    for(int S = 1; S < 1 << N; S++) {
        for(int i = 0; i < N; i++)
            for(int j = 0; j < i; j++)
                if(S >> i & S >> j & 1) dp[S] += a[i][j];

        for(int T = S; T > 0; T = T - 1 & S) {
            if(T == S) continue; // S 自身は除く
            dp[S] = max(dp[S], dp[T] + dp[S ^ T]);
        }
    }

    cout << dp[(1 << N) - 1] << endl;

    return 0;
}

#V - Subtree

##問題
$N$ 頂点の木の頂点を白黒に塗り分けます。
黒い頂点同士のパスは黒い頂点のみで構成されるようにします。
各頂点 $v$ について、次の質問に$\mod{M}$ で答えてください。

• $v$ を黒く塗る塗り分け方は何通りあるか

##制約

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

##解法

この解説は自分で読んでも分かりにくいと感じるので、今後書き換える可能性がそこそこあります。

ある特定の頂点 $v$ に対しては、下のような木 DP を行うことで $O(N)$ で解くことができます。

void dfs(int v, int p) {
    dp[v] = 1;
    for(int u : G[v]) {
        if(u != p) {
            dfs(u, v);
            // u が白の場合が 1 通り
            dp[v] *= dp[u] + 1;
            dp[v] %= M;
        }
    }
}

これと同じことを各頂点にすると、計算量が $O(N^2)$ となり、TLE します。

$v$ の子の中から適当に $u$ を選び、$u$ を根とした根付き木について、この問題を解くことを考えます。
いま、すでに $dp_u$ には $v$ 以外の $u$ の隣の頂点からの情報が集約されています。なので、$v$ から $u$ への情報を得ることができれば、$u$ についてこの問題を解くことができそうです。この考え方は 全方位木 DP (ReRooting) と呼ばれています。
$v$ から $u$ への情報は、$dp_v/$($u$ から $v$ への情報) で求められそうですが、($u$ から $v$ への情報) が$\mod{M}$ で $0$ の時に困ります。
$v$ から $u$ への情報を求めるには、$u$ 以外から $v$ に入ってくる情報をすべて集約 (この問題の場合は、掛け算) すればいいです。
いちいち掛け算していると最悪計算量が $O(N^2)$ になってしまいますが (ウニグラフ) 、累積和と同じ要領で積を前と後ろから累積したものを前計算しておけば、計算量を $O(N)$ で済ませることができます。

個人的に、この問題は正直全方位木 DP を初めて実装する人にはあまり向いていないと思います。(ABC160Fなど、可換群を用いる問題のほうが難易度は低いです)

##実装例
DFS を $2$ 回やる感じで実装するといいと思います。

#include <iostream>
#include <vector>
using namespace std;

int N, M;
vector<int> G[100009];
long long dp[100009];

void dfs1(int v, int p) {
    dp[v] = 1;
    for(int u : G[v]) {
        if(u != p) {
            dfs1(u, v);
            dp[v] *= dp[u] + 1;
            dp[v] %= M;
        }
    }
}

void dfs2(int v, int p, long long dp_p = 0) {
    int n = G[v].size();
    // 積を累積しておく配列
    vector<long long> mul1(n), mul2(n);
    for(int i = 0; i < n; i++) {
        int u = G[v][i];
        if(u == p) {
            mul1[i] = mul2[i] = (dp_p + 1) % M;
            dp[v] *= dp_p + 1;
            dp[v] %= M;
        } else
            mul1[i] = mul2[i] = (dp[u] + 1) % M;
    }
    for(int i = 0; i + 1 < n; i++) {
        mul1[i + 1] *= mul1[i];
        mul1[i + 1] %= M;
    }
    for(int i = n - 1; i - 1 >= 0; i--) {
        mul2[i - 1] *= mul2[i];
        mul2[i - 1] %= M;
    }

    for(int i = 0; i < n; i++) {
        int u = G[v][i];
        if(u != p) {
            long long a = (i ? mul1[i - 1] : 1);
            long long b = (i + 1 < n ? mul2[i + 1] : 1);
            dfs2(u, v, a * b % M);
        }
    }
}

int main() {
    cin >> N >> M;
    for(int i = 0; i < N - 1; i++) {
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        G[x].push_back(y);
        G[y].push_back(x);
    }

    dfs1(0, -1);
    dfs2(0, -1);

    for(int i = 0; i < N; i++)
        cout << dp[i] << endl;

    return 0;
}

#W - Intervals

##問題
長さ $N$ の '0' '1' で構成された文字列 $s$ に対して、スコアを次のように計算します。

• 各 $i$ について、$l_i$ 文字目から $r_i$ 文字目までに '1' が含まれるなら、スコアに $a_i$ 点を加算する。

文字列のスコアの最大値を求めてください。

##制約

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

##解法

$i$ 番目の区間に対する操作は、$r_i$ 文字目まで決めたときに最後に '1' にした index が $l_i$ 以上なら $a_i$ を足すことと同値です。

$dp_{i,j}=$ ($i$ 文字決めて、最後に '1' にした index が $j$ であるときのスコアの最大値)
この DP の遷移を考えると、次のように分けることができます。

• $dp_i$ に $dp_{i-1}$ をコピーする
• $dp_{i,i}=\max(dp_{i-1,j})$
• $[l,i]$ となるすべての区間について、$dp_{i,j}\{l\le j\le i\}$ に $a$ を足す。

区間の最大値の計算と区間への add が高速でできるデータ構造 (遅延セグ木や、Starry Sky Tree) を使えば、遷移が $O(\log{N})$ でできます。

##実装例
$l,r$ は 1-indexed の閉区間で扱っています。
Starry Sky Tree をよく知らないので、遅延セグ木で実装しています。
(どちらもいつか変更するかもしれないです)

計算量は $O(N\log N)$ です。

#include <iostream>
#include <vector>
using namespace std;

const int sz = 1 << 18;

// Lazy Segment Tree
long long data[sz << 1], lazy[sz << 1];
void eval(int k) {
    data[k] += lazy[k];
    if(k < sz) {
        lazy[k << 1] += lazy[k];
        lazy[k << 1 | 1] += lazy[k];
    }
    lazy[k] = 0;
}
void add(int a, int b, long long x, int k = 1, int l = 0, int r = sz) {
    eval(k);
    if(b <= l || r <= a) return;
    if(a <= l && r <= b) {
        lazy[k] += x;
        eval(k);
    } else {
        add(a, b, x, k << 1, l, l + r >> 1);
        add(a, b, x, k << 1 | 1, l + r >> 1, r);
        data[k] = max(data[k << 1], data[k << 1 | 1]);
    }
}
long long getmax(int a, int b, int k = 1, int l = 0, int r = sz) {
    if(b <= l || r <= a) return -1LL << 60;
    eval(k);
    if(a <= l && r <= b) return data[k];
    long long vl = getmax(a, b, k << 1, l, l + r >> 1);
    long long vr = getmax(a, b, k << 1 | 1, l + r >> 1, r);
    return max(vl, vr);
}

int N, M;

vector<pair<int, int>> P[200009];

int main() {
    cin >> N >> M;
    for(int i = 0; i < M; i++) {
        int l, r, a;
        cin >> l >> r >> a;
        P[r].push_back(make_pair(l, a));
    }

    for(int i = 1; i <= N; i++) {
        add(i, i + 1, getmax(0, i));
        for(auto p : P[i]) {
            int l = p.first;
            int a = p.second;
            add(l, i + 1, a);
        }
    }

    cout << getmax(0, N + 1) << endl;

    return 0;
}

#続き

• Educational DP Contest (EDPC) X ~ Z 問題 解説