2024-04-15

EDPC (Educational DP Contest) V - Subtree

EDPCとTDPC 全方位木DP 全方位木DP:逆元がない場合 DP 木木DP 【問題集】木DPのステップアップグラフそのまま覚えたいシンプル設定の中堅以上の典型問題 AtCoder 数え上げ問題色に関する問題各kに対して

全方位木 DP の練習問題！！　 $M$ が素数とは限らないので「左右から累積和」が必要なタイプの全方位木 DP。

問題へのリンク

問題概要

正の整数 $M$ と、頂点数 $N$ の木 $G$ が与えられる。この木の各頂点を「黒色」または「白色」に塗る。

各頂点 $v$ について、以下の条件をみたす場合の数を $M$ で割った余りを求めよ。

頂点 $v$ は黒色である
黒色の頂点は連結である

制約

$1 \le N \le 10^{5}$
$2 \le M \le 10^{9}$

解法：全方位木 DP

この問題に対して、各頂点 $v$ を根とした木 DP をしてしまうと、 $O(N^{2})$ の計算量となってしまいます。このようなとき、全方位木 DP がしばしば有効です。

ここでは、通常の「根を 1 つ決めたときの木 DP」を全方位木 DP へと機械的に拡張する方法を示します。

まず、「頂点 0 を黒色にする場合」についての問題を解くとき、次のような木 DP ができます。

`dp[v]：頂点 $v$ 根とする根付き木において、頂点 $v$ を黒色に塗った上で黒色頂点全体が連結になっているような塗り方の数に、1 を足した値

とします。ここで「1 を足す」とは、「すべての頂点が白色である場合」を加えることを意味しています。このとき、次のような木 DP ができます。

long long rec(int v, int p) {
    long long res = 1;
    for (auto v2 : G[v]) {
        if (v2 == p) continue;
        res = res * rec(v2, v) % M;
    }
    return (res + 1) % M;
}

この再帰関数 rec() を用いて、rec(0, -1) - 1 が答えとなります。

木 DP を抽象化

ここで、上記のような木 DP の抽象化を考えます。次の 4 つのものを定めれば抽象化できそうです。

Monoid：dp の型
- 今回は long long 型
IDENTITY：下記の関数 MERGE() についての Monoid の単位元
- 今回は 1
MERGE(Monoid a, Monoid b)：部分木と部分木の情報を統合する部分を表す関数
- 今回は a * b % M を返す
ADDNODE(int v, Monoid a)：部分木に関して統合した情報 a に対して、最後に頂点 v に関する情報を統合する関数
- 今回は (a + 1) % M を返す

このように抽象化すると、上の木 DP は次のように書き直せます。

Monoid rec(int v, int p) {
    Monoid res = IDENTITY;
    for (auto v2 : G[v]) {
        if (v2 == p) continue;
        res = MERGE(res, rec(v2, v));
    }
    return ADDNODE(v, res);
}

全方位木 DP

この抽象化をもとに、全方位木 DP を考えます。通常の木 DP は、根を 1 つ決めた上で、各頂点を根とする部分木 ( $N$ 個あります) に関する問題を、 $O(N)$ の計算量で順次解いていくものでした。

これに対して全方位木 DP は、木の各辺を除去して得られる部分木 ( $2(N-1)$ 個あります) に関する問題を、全体 $O(N)$ の計算量で順次解いていくものです。

この $2(N-1)$ 個の部分木に関する問題が解けているとき、もとの木でどの頂点を根とした場合についても、その子頂点を根とする部分木の情報がすべて得られる状態となっています。これをもとにして、「その頂点を根としたときの問題の解」をならし $O(1)$ の計算量で求めることができます。

全方位木 DP の詳細については、次の記事に詳しく書かれています。

ei1333.hateblo.jp

ここでは、抽象化した全方位木 DP の実装を示します。

// re-rooting
template<class Monoid> struct ReRooting {
    using Graph = vector<vector<int>>;
    using MergeFunc = function<Monoid(Monoid, Monoid)>;
    using AddNodeFunc = function<Monoid(int, Monoid)>;
    
    // core member
    Graph G;
    Monoid IDENTITY;
    MergeFunc MERGE;
    AddNodeFunc ADDNODE;
    
    // inner data
    vector<vector<Monoid>> dp;
    
    // constructor
    ReRooting() {}
    ReRooting(const Graph &g, const Monoid &identity,
              const MergeFunc &merge, const AddNodeFunc &addnode) {
        G = g;
        IDENTITY = identity;
        MERGE = merge;
        ADDNODE = addnode;
        build();
    }
    
    // re-looting dp
    Monoid rec(int v, int p) {
        Monoid res = IDENTITY;
        dp[v].assign(G[v].size(), IDENTITY);
        for (int i = 0; i < G[v].size(); ++i) {
            int v2 = G[v][i];
            if (v2 == p) continue;
            dp[v][i] = rec(v2, v);
            res = MERGE(res, dp[v][i]);
        }
        return ADDNODE(v, res);
    }
    void rerec(int v, int p, Monoid pval) {
        for (int i = 0; i < G[v].size(); ++i) {
            int v2 = G[v][i];
            if (v2 == p) {
                dp[v][i] = pval;
                continue;
            }
        }
        vector<Monoid> left(G[v].size() + 1, IDENTITY);
        vector<Monoid> right(G[v].size() + 1, IDENTITY);
        for (int i = 0; i < G[v].size(); ++i) {
            left[i + 1] = MERGE(left[i], dp[v][i]);
            right[i + 1] = MERGE(right[i], dp[v][(int)G[v].size() - i - 1]);
        }
        for (int i = 0; i < G[v].size(); ++i) {
            int v2 = G[v][i];
            if (v2 == p) continue;
            Monoid pval2 = MERGE(left[i], right[(int)G[v].size() - i - 1]);
            rerec(v2, v, ADDNODE(v, pval2));
        }
    }
    void build() {
        dp.assign(G.size(), vector<Monoid>());
        int root = 0, nullparent = -1;
        rec(root, nullparent);
        rerec(root, nullparent, IDENTITY);
    }
    
    // getter
    Monoid get(int v) {
        Monoid res = IDENTITY;
        for (int i = 0; i < G[v].size(); ++i) {
            res = MERGE(res, dp[v][i]);
        }
        return ADDNODE(v, res);
    }
    
    // dump
    friend constexpr ostream& operator << (ostream &os, const ReRooting<Monoid> &rr) {
        for (int v = 0; v < rr.G.size(); ++v) {
            for (int i = 0; i < rr.G[v].size(); ++i) {
                os << v << " -> " << rr.G[v][i] << ": " << rr.dp[v][i] << endl;
            }
        }
        return os;
    }
};

まとめ

今回の問題に戻ると、木 DP を次のように定義して、全方位木 DP に投げればよいです。全体として計算量は $O(N)$ となります。

// 木 DP で更新する情報の型
using Monoid = long long;

// 木 DP の更新演算に関する単位元
Monoid identity = 1;

// 木 DP の更新演算
auto merge = [&](Monoid a, Monoid b) -> Monoid { return a * b % M; };

// 木 DP において頂点 v の各部分木の更新をしたあとの頂点 v 自身による更新
auto addnode = [&](int v, Monoid a) -> Monoid { return (a + 1) % M; };

// 全方位木 DP の実施
ReRooting<Monoid> rr(G, identity, merge, addnode);

コード

#include <bits/stdc++.h>
using namespace std;


// re-rooting
template<class Monoid> struct ReRooting {
    using Graph = vector<vector<int>>;
    using MergeFunc = function<Monoid(Monoid, Monoid)>;
    using AddNodeFunc = function<Monoid(int, Monoid)>;
    
    // core member
    Graph G;
    Monoid IDENTITY;
    MergeFunc MERGE;
    AddNodeFunc ADDNODE;
    
    // inner data
    vector<vector<Monoid>> dp;
    
    // constructor
    ReRooting() {}
    ReRooting(const Graph &g, const Monoid &identity,
              const MergeFunc &merge, const AddNodeFunc &addnode) {
        G = g;
        IDENTITY = identity;
        MERGE = merge;
        ADDNODE = addnode;
        build();
    }
    
    // re-looting dp
    Monoid rec(int v, int p) {
        Monoid res = IDENTITY;
        dp[v].assign(G[v].size(), IDENTITY);
        for (int i = 0; i < G[v].size(); ++i) {
            int v2 = G[v][i];
            if (v2 == p) continue;
            dp[v][i] = rec(v2, v);
            res = MERGE(res, dp[v][i]);
        }
        return ADDNODE(v, res);
    }
    void rerec(int v, int p, Monoid pval) {
        for (int i = 0; i < G[v].size(); ++i) {
            int v2 = G[v][i];
            if (v2 == p) {
                dp[v][i] = pval;
                continue;
            }
        }
        vector<Monoid> left(G[v].size() + 1, IDENTITY);
        vector<Monoid> right(G[v].size() + 1, IDENTITY);
        for (int i = 0; i < G[v].size(); ++i) {
            left[i + 1] = MERGE(left[i], dp[v][i]);
            right[i + 1] = MERGE(right[i], dp[v][(int)G[v].size() - i - 1]);
        }
        for (int i = 0; i < G[v].size(); ++i) {
            int v2 = G[v][i];
            if (v2 == p) continue;
            Monoid pval2 = MERGE(left[i], right[(int)G[v].size() - i - 1]);
            rerec(v2, v, ADDNODE(v, pval2));
        }
    }
    void build() {
        dp.assign(G.size(), vector<Monoid>());
        int root = 0, nullparent = -1;
        rec(root, nullparent);
        rerec(root, nullparent, IDENTITY);
    }
    
    // getter
    Monoid get(int v) {
        Monoid res = IDENTITY;
        for (int i = 0; i < G[v].size(); ++i) {
            res = MERGE(res, dp[v][i]);
        }
        return ADDNODE(v, res);
    }
    
    // dump
    friend constexpr ostream& operator << (ostream &os, const ReRooting<Monoid> &rr) {
        for (int v = 0; v < rr.G.size(); ++v) {
            for (int i = 0; i < rr.G[v].size(); ++i) {
                os << v << " -> " << rr.G[v][i] << ": " << rr.dp[v][i] << endl;
            }
        }
        return os;
    }
};


int main() {
    int N, M;
    cin >> N >> M;
    
    using Graph = vector<vector<int>>;
    Graph G(N);
    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);
    }
    
    using Monoid = long long;
    Monoid identity = 1;
    auto merge = [&](Monoid a, Monoid b) -> Monoid { return a * b % M; };
    auto addnode = [&](int v, Monoid a) -> Monoid { return (a + 1) % M; };
    ReRooting<Monoid> rr(G, identity, merge, addnode);
    
    //cout << rr << endl;
    
    for (int v = 0; v < N; ++v) {
        cout << (rr.get(v) + M - 1) % M << endl;
    }
}

2024-04-06

AtCoder ABC 227 A - Last Card (灰色, 100 点)

算数と数学:条件を筋よく整理する算数と数学易しい算数と数学テク:2週目以降のものの添字を演算子「%」で求める算数と数学:植木算算数と数学:文字式繰り返し回数を割り算で求める for文整数のfor文

これは難しいですね。何も考えずに for 文で求めるのが比較的楽でしょうか。

問題へのリンク

問題概要

$1, 2, \dots, N$ と番号のついた $N$ 人に、 $K$ 枚のカードを配っていく。

人 $A$ から始めて、人 $A,A+1,A+2,…,N,1,2,…$ の順に 1 枚ずつカードを配るとき、最後のカードは誰に配られるでしょうか？

解法 1：演算子「%」を使用する

上の並びは、「 $A$ から順に 1 ずつ増やしていき、 $N+1$ になった瞬間に $1$ にリセットする」というようになっています。

ここで、もし仮にリセットがないものとした場合には、答えは $A + K - 1$ になります (植木算をしています)。ここが分かりにくいと感じた場合には、具体的な $K$ の値で確かめてみましょう。

$1$ 番目： $A$
$2$ 番目： $A + 1$
$3$ 番目： $A + 2$
$\dots$

この並びをみていると、一般に $K$ 番目は $A$ に $K-1$ を足したものであることがわかります。よって、 $K$ 番目の値は $A + K - 1$ となります。

リセットつき

ここまで来れば、リセットが存在する場合も容易に求められます。基本的には、 $A + K - 1$ を $N$ で引いていき、 $N$ 以下の値になれば、それが答えです。

たとえば、 $A + K - 1 = 94$ で $N = 10$ であれば、答えは $4$ です。 $A + K - 1 = 100$ で $N = 10$ であれば、答えは $10$ です。

$A + K - 1$ を $N$ で割ってみましょう。

割り切れないときは、その余りが答え
割り切れるときは、 $N$ が答え

と考えれば良いです。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, K, A;
    cin >> N >> K >> A;
    
    int no_reset = A + K - 1;
    if (no_reset % N > 0)
        cout << no_reset % N << endl;
    else
        cout << N << endl;
}

解法 (2)

何も考えずに for 文で書いてもよいでしょう。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, K, A;
    cin >> N >> K >> A;
    
    int res = A;
    for (int i = 0; i < K - 1; ++i) {
        ++res;
        if (res == N+1) res = 1;
    }
    cout << res << endl;
}

2024-04-06

AtCoder ABC 226 A - Round decimals (灰色, 100 点)

AtCoder AtCoder100点 ABC-A 灰色diff 誤差構文解析易しい構文解析文字列

色んな方法がありそう！

問題へのリンク

問題概要

0 以上 100 未満の小数第三位までで表すことのできる実数 $X$ が、小数第三位まで入力されます。

$X$ を小数第一位で四捨五入した結果として得られる整数を出力してください。

考えたこと

C++ で解く場合、入力は cin を用いるよりも、scanf() を用いると楽だと思われます。scanf() を用いると、次のように「整数部分」と「小数部分」を分けて入力を受け取れます。

int a, b;
scanf("%d.%d", &a, &b);

その後は、整数 b の先頭が 5 以上の場合は a に 1 を足せば良いでしょう。具体的には、整数型b を文字列に変換したものは to_string(b) と表せるので、その先頭の文字を見ることで判定できます。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int a, b;
    scanf("%d.%d", &a, &b);
    if (to_string(b)[0] >= '5') ++a;
    cout << a << endl;
}

2024-04-06

AtCoder ABC 225 A - Distinct Strings (灰色, 100 点)

算数と数学易しい算数と数学数え上げ問題易しい数え上げ問題 3個の値を扱う問題文字列場合分け算数と数学:条件を筋よく整理する算数と数学:場合をもれなく列挙する順列順列の数え上げ種類数 AtCoder AtCoder100点 ABC-A 灰色diff

これ結構難しいと思う！　数学 IA の「場合の数」をやると、よく出て来るやつですね。

問題へのリンク

問題概要

英小文字のみからなる長さ 3 の文字列 $S$ が与えられます。

$S$ の各文字を並び替えて得られる文字列は、何種類ありますか？

解法

「3 個のものを並び替える場合の数」は、数学 IA だとよく出て来るやつですね。実は次の 3 パターンがあります。

のように、すべて同じものを並び替える方法
- 1 通りです
やのように、2 種類のもので構成される場合に、それを並び替える方法
- 3 通りです
のように、3 種類のもので構成されるとき、それを並び替える方法
- 6 通りです

たとえば、 $(a, a, b)$ を並び替える方法は、

$(a, a, b), (a, b, a), (b, a, a)$

の 3 通りあります。 $(a, b, c)$ を並び替える方法は、

$(a, b, c), (a, c, b), (b, a, c), (b, c, a), (c, a, b), (c, b, a)$

6 通りあります。

問題に戻って

上記のことを踏まえると、今回の問題は次のことを判別する問題だと言えます。

文字列 $S$ が 1 種類の文字で成り立つとき：1 通り
文字列 $S$ が 2 種類の文字で成り立つとき：3 通り
文字列 $S$ が 3 種類の文字で成り立つとき：6 通り

判別の手順としては、「1 種類」「3 種類」を判別するのが楽なので、「2 種類」を判別する部分は else 文に押し付けるのが楽ですね。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    string S;
    cin >> S;
    if (S[0] == S[1] && S[1] == S[2])
        cout << 1 << endl;
    else if (S[0] != S[1] && S[1] != S[2] && S[2] != S[0])
        cout << 6 << endl;
    else
        cout << 3 << endl;
}

2024-04-05

AtCoder ABC 224 A - Tires (灰色, 100 点)

if文文字列易しい文字列の問題文字列のindexアクセス Yes/No判定問題易しいYes/No判定問題 AtCoder AtCoder100点 ABC-A 灰色diff

文字列を上手に使う練習

問題へのリンク

問題概要

末尾が "er" か "ist" であるような文字列 $S$ (2 文字以上) が与えられます。

どちらであるかを判定してください。

解法

末尾が "er" であるかどうかを判定することにしよう。文字列 S の長さを N とするとき、

S の末尾の文字は S[N - 1]
S の末尾から 2 文字目の文字は S[N - 2]

であることから、末尾が "er" であるかどうかは、次のように判定できる。

if (S[N - 1] == 'r' && S[N - 2] == 'e')

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    string S;
    cin >> S;
    int N = (int)S.size();
    if (S[N-1] == 'r'&& S[N-2] == 'e')
        cout << "er" << endl;
    else
        cout << "ist" << endl;
}

別解

与えられる文字列は末尾が "er" か "ist" であることが保証されているのだから、実は「末尾の文字が 'r' であるかどうか」のみを判定すれば OK

#include <bits/stdc++.h>
using namespace std;

int main() {
    string S;
    cin >> S;
    if (S.back() == 'r')
        cout << "er" << endl;
    else
        cout << "ist" << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

EDPC (Educational DP Contest) V - Subtree

問題概要

制約

解法：全方位木 DP

木 DP を抽象化

全方位木 DP

まとめ

コード

AtCoder ABC 227 A - Last Card (灰色, 100 点)

問題概要

解法 1：演算子「%」を使用する

リセットつき

コード

解法 (2)

AtCoder ABC 226 A - Round decimals (灰色, 100 点)

問題概要

考えたこと

コード

AtCoder ABC 225 A - Distinct Strings (灰色, 100 点)

問題概要

解法

問題に戻って

コード

AtCoder ABC 224 A - Tires (灰色, 100 点)

問題概要

解法

コード

別解