6月, 2019 | 個人用メモ帳

2019年6月15日2019年6月15日

C++ の動作確認をしてみた（７２）

C++の練習を兼ねて, AtCoder Regular Contest 059 の問題F (F – バイナリハック / Unhappy Hacking) を解いてみた.

■感想.
1. DPが良くわかってないので, 解説(数え上げテクニック集)を参照して実装してみた.

■C++版プログラム(問題F／AC版).

// 数え上げテクニック集
// https://drive.google.com/file/d/1WC7Y2Ni-8elttUgorfbix9tO1fvYN3g3/view
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const LL MOD = 1e9 + 7;
LL dp[5001][5001];

int main() {
    
    // 1. 入力情報取得.
    LL N;
    string S;
    cin >> N >> S;
    
    // 2. 数え上げ.
    // 数え上げテクニック集 に従って, dp[n][x] で 数え上げ.
    // n: 操作回数, x: 現在の文字列長.
    // ex.
    // n = 1: dp[1][0] = 1, dp[1][1] = 2
    //   => 合計 3通り.
    // n = 2: dp[2][0] = dp[1][0] * 1 + dp[1][1] * 1 = 3, dp[2][1] = dp[1][0] * 2 = 2, 
    //        dp[2][2] = dp[1][1] * 2 = 4
    //   => 合計 9通り.
    // n = 3: dp[3][0] = dp[2][0] * 1 + dp[2][1] * 1 = 5, dp[3][1] = dp[2][0] * 2 + dp[2][2] * 1 = 10, 
    //        dp[3][2] = dp[2][1] * 2 = 4, dp[3][3] = dp[2][2] * 2 = 8
    //   => 合計 27通り.
    int l = S.size();
    dp[1][0] = 1, dp[1][1] = 2;
    for(int i = 1; i <= N; i++){
        for(int j = 0; j <= N; j++){
            // 2-1. (j - 1)文字 から j文字 に 遷移(文字 '0' or '1' を 右端 に 追加)する場合.
            if(j - 1 >= 0) dp[i][j] += dp[i - 1][j - 1] * 2, dp[i][j] %= MOD;

            // 2-2. (j + 1)文字 から j文字 に 遷移(バックスペースキー で 右端 の 文字 を 削除)する場合.
            if(j + 1 < i)  dp[i][j] += dp[i - 1][j + 1] * 1, dp[i][j] %= MOD;

            // 2-3. 0文字 から 0文字 に 遷移する場合.
            if(j == 0)     dp[i][j] += dp[i - 1][j] * 1,     dp[i][j] %= MOD;
            // cout << "i=" << i << " j=" << j << " dp=" << dp[i][j] << " ";
        }
    }
    
    // 3. 出力 ～ 後処理.
    // 数え上げテクニック集 に従って, 同じ文字数の文字列を作る場合の数が, すべて等しいとの内容を反映.
    // -> 2 で, S.size()回割れば良い筈 => 500000004 を 乗ずる形に修正.
    LL ans = dp[N][l];
    for(int j = 1; j <= l; j++) ans *= 500000004, ans %= MOD;
    cout << ans << endl;
    return 0;
    
}

// 数え上げテクニック集

// https://drive.google.com/file/d/1WC7Y2Ni-8elttUgorfbix9tO1fvYN3g3/view

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

const LL MOD = 1e9 + 7;

LL dp[5001][5001];

int main() {

// 1. 入力情報取得.

LL N;

string S;

cin >> N >> S;

// 2. 数え上げ.

// 数え上げテクニック集に従って, dp[n][x] で数え上げ.

// n: 操作回数, x: 現在の文字列長.

// ex.

// n = 1: dp[1][0] = 1, dp[1][1] = 2

// => 合計 3通り.

// n = 2: dp[2][0] = dp[1][0] * 1 + dp[1][1] * 1 = 3, dp[2][1] = dp[1][0] * 2 = 2,

// dp[2][2] = dp[1][1] * 2 = 4

// => 合計 9通り.

// n = 3: dp[3][0] = dp[2][0] * 1 + dp[2][1] * 1 = 5, dp[3][1] = dp[2][0] * 2 + dp[2][2] * 1 = 10,

// dp[3][2] = dp[2][1] * 2 = 4, dp[3][3] = dp[2][2] * 2 = 8

// => 合計 27通り.

int l = S.size();

dp[1][0] = 1, dp[1][1] = 2;

for(int i = 1; i <= N; i++){

for(int j = 0; j <= N; j++){

// 2-1. (j - 1)文字から j文字に遷移(文字 '0' or '1' を右端に追加)する場合.

if(j - 1 >= 0) dp[i][j] += dp[i - 1][j - 1] * 2, dp[i][j] %= MOD;

// 2-2. (j + 1)文字から j文字に遷移(バックスペースキーで右端の文字を削除)する場合.

if(j + 1 < i) dp[i][j] += dp[i - 1][j + 1] * 1, dp[i][j] %= MOD;

// 2-3. 0文字から 0文字に遷移する場合.

if(j == 0) dp[i][j] += dp[i - 1][j] * 1, dp[i][j] %= MOD;

// cout << "i=" << i << " j=" << j << " dp=" << dp[i][j] << " ";

}

// 3. 出力～後処理.

// 数え上げテクニック集に従って, 同じ文字数の文字列を作る場合の数が, すべて等しいとの内容を反映.

// -> 2 で, S.size()回割れば良い筈 => 500000004 を乗ずる形に修正.

LL ans = dp[N][l];

for(int j = 1; j <= l; j++) ans *= 500000004, ans %= MOD;

cout << ans << endl;

return 0;

}

■参照サイト
AtCoder Regular Contest 059
数え上げテクニック集

2019年6月15日2019年6月15日

C++ の動作確認をしてみた（７１）

■感想.
1. どこかで類題を見た記憶があったので, 探したところ, yukicoder の No.697 池の数はいくつかに似ていることが分かった.
2. 上記の類題を適用するため, 埋め立て後の陸地の個数をカウントする方法で, 本問の解答方針とした.

■C++版プログラム(問題B／AC版).

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
constexpr int MAX = 100;
constexpr int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
int H, W;
char board[MAX];
int memo[MAX];

// 幅優先探索.
// https://ja.wikipedia.org/wiki/幅優先探索
// 迷路を幅優先探索する.
// ※bfsの動作確認用.
// @param c: 探索地点の迷路の座標.
// @param d: 池の番号.
// @return: 特に無し.
void bfs(int c, int d){
    
    // 1. 終了条件設定.
    if(board[c] == 'x') return;
    
    // 2. 空のキュー.
    queue<int> q;
    
    // 3. 訪問済みフラグ設定.
    memo[c] = d;
    
    // 4. 探索地点 c をキュー q に追加.
    q.push(c);
    while(!q.empty()){
        // 5. キューから取り出す.
        int v = q.front();
        q.pop();
        // 6. 取り出した要素を処理.
        // x: 列方向, y: 行方向 で考える.
        int nx, ny, n;
        int cx = v % W , cy = v / W;
        FOR(i, 0, 4){
            nx = cx + dx[i];
            ny = cy + dy[i];
            n = nx + ny * W;
            // cout << "cx=" << cx << " nx=" << nx  << " cy=" << cy << " ny=" << ny << " n=" << n << " c=" << c << endl;
            // 7. 訪問不可能なマス であれば, 処理をスキップ.
            if(n < 0 || nx < 0 || nx >= W || ny < 0 || ny >= H) continue;
            if(memo[n] == d)                                    continue;
            // 8. 訪問可能 かつ 未訪問 のマス であれば, 訪問済みを設定.
            if(board[n] == 'o' && memo[n] == 0) memo[n] = d, q.push(n);
        }
    }
    return;
}

int main() {
    
    // 1. 入力情報取得.
    W = 10, H = 10;
    FOR(i, 0, H){
        string s;
        cin >> s;
        FOR(j, 0, W) board[i * W + j] = s[j];
    }
    
    // 2. 海を1マスだけ陸地にして, 1つの島に出来るかを確認.
   int counter = 0;
   bool ans = false;
    FOR(i, 0, H * W){
        if(board[i] == 'x'){
            // 2-1. 海を1マスだけ陸地にしてみる.
            board[i] = 'o';
            
            // 2-2. 陸地の分割.
            // cout << "----- " << "i=" << i << " counter=" << counter <<" -----" << endl;
            FOR(j, 0, H * W) if(board[j] == 'o' && memo[j] == 0) counter++, bfs(j, counter);
            // FOR(k, 0, H){
            //     FOR(l, 0, W){
            //         cout << memo[k * W + l] << " ";
            //     }
            //     cout << endl;
            // }
            // cout << "----- " << "i=" << i << " counter=" << counter <<" -----" << endl;
            // ex.
            // [入力例]
            // xxxxoxxxxx
            // xxxxoxxxxx
            // xxxxoxxxxx
            // xxxxoxxxxx
            // ooooxooooo
            // xxxxoxxxxx
            // xxxxoxxxxx
            // xxxxoxxxxx
            // xxxxoxxxxx
            // xxxxoxxxxx
            // 
            // [探索状況(抜粋)]
            // ----- i=44 counter=0 -----
            // 0 0 0 0 1 0 0 0 0 0 
            // 0 0 0 0 1 0 0 0 0 0 
            // 0 0 0 0 1 0 0 0 0 0 
            // 0 0 0 0 1 0 0 0 0 0 
            // 1 1 1 1 1 1 1 1 1 1 
            // 0 0 0 0 1 0 0 0 0 0 
            // 0 0 0 0 1 0 0 0 0 0 
            // 0 0 0 0 1 0 0 0 0 0 
            // 0 0 0 0 1 0 0 0 0 0 
            // 0 0 0 0 1 0 0 0 0 0 
            // ----- i=44 counter=1 -----
            // -> YES 正しく判定されているように見える.
            
            // 2-3. 1つの島に出来た場合は, 後続処理をスキップ.
            if(counter == 1){
                ans = true;
                break;
            }
            
            // 2-4. 元に戻す.
            counter = 0;
            board[i] = 'x';
            FOR(j, 0, H * W) memo[j] = 0;
        }
    }
    
    // 3. 出力 ～ 後処理.
    if(ans) cout << "YES" << endl;
    else    cout << "NO"  << endl;
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)

constexpr int MAX = 100;

constexpr int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};

int H, W;

char board[MAX];

int memo[MAX];

// 幅優先探索.

// https://ja.wikipedia.org/wiki/幅優先探索

// 迷路を幅優先探索する.

// ※bfsの動作確認用.

// @param c: 探索地点の迷路の座標.

// @param d: 池の番号.

// @return: 特に無し.

void bfs(int c, int d){

// 1. 終了条件設定.

if(board[c] == 'x') return;

// 2. 空のキュー.

queue<int> q;

// 3. 訪問済みフラグ設定.

memo[c] = d;

// 4. 探索地点 c をキュー q に追加.

q.push(c);

while(!q.empty()){

// 5. キューから取り出す.

int v = q.front();

q.pop();

// 6. 取り出した要素を処理.

// x: 列方向, y: 行方向で考える.

int nx, ny, n;

int cx = v % W , cy = v / W;

FOR(i, 0, 4){

nx = cx + dx[i];

ny = cy + dy[i];

n = nx + ny * W;

// cout << "cx=" << cx << " nx=" << nx << " cy=" << cy << " ny=" << ny << " n=" << n << " c=" << c << endl;

// 7. 訪問不可能なマスであれば, 処理をスキップ.

if(n < 0 || nx < 0 || nx >= W || ny < 0 || ny >= H) continue;

if(memo[n] == d) continue;

// 8. 訪問可能かつ未訪問のマスであれば, 訪問済みを設定.

if(board[n] == 'o' && memo[n] == 0) memo[n] = d, q.push(n);

}

return;

}

int main() {

// 1. 入力情報取得.

W = 10, H = 10;

FOR(i, 0, H){

string s;

cin >> s;

FOR(j, 0, W) board[i * W + j] = s[j];

}

// 2. 海を1マスだけ陸地にして, 1つの島に出来るかを確認.

int counter = 0;

bool ans = false;

FOR(i, 0, H * W){

if(board[i] == 'x'){

// 2-1. 海を1マスだけ陸地にしてみる.

board[i] = 'o';

// 2-2. 陸地の分割.

// cout << "----- " << "i=" << i << " counter=" << counter <<" -----" << endl;

FOR(j, 0, H * W) if(board[j] == 'o' && memo[j] == 0) counter++, bfs(j, counter);

// FOR(k, 0, H){

// FOR(l, 0, W){

// cout << memo[k * W + l] << " ";

// }

// cout << endl;

// }

// cout << "----- " << "i=" << i << " counter=" << counter <<" -----" << endl;

// ex.

// [入力例]

// xxxxoxxxxx

// ooooxooooo

// xxxxoxxxxx

// [探索状況(抜粋)]

// ----- i=44 counter=0 -----

// 0 0 0 0 1 0 0 0 0 0

// 1 1 1 1 1 1 1 1 1 1

// 0 0 0 0 1 0 0 0 0 0

// ----- i=44 counter=1 -----

// -> YES 正しく判定されているように見える.

// 2-3. 1つの島に出来た場合は, 後続処理をスキップ.

if(counter == 1){

ans = true;

break;

}

// 2-4. 元に戻す.

counter = 0;

board[i] = 'x';

FOR(j, 0, H * W) memo[j] = 0;

}

// 3. 出力～後処理.

if(ans) cout << "YES" << endl;

else cout << "NO" << endl;

return 0;

}

■参照サイト
AtCoder Regular Contest 031
No.697 池の数はいくつか

2019年6月11日

C++ の動作確認をしてみた（７０）

C++の練習を兼ねて, Typical DP Contest の問題A (A – コンテスト) を解いてみた.

■感想.
1. どこかで類題を見た記憶があったので, 探したところ, yukicoder の No.4 おもりと天秤に似ていることが分かった.
2. DPを使う方法を模索したが, 使い方が, 分からなかったので, 要復習と認識している.

■C++版プログラム(問題A／AC版).

// yukicoder の 問題 を 参照.
// No.4 おもりと天秤
// https://yukicoder.me/problems/no/4
#include <bits/stdc++.h>
using namespace std;

// 獲得可能な得点を更新する.
// @param m: 得点のリスト.
// @param s: 得点.
// @return ret: 更新した得点のリスト.
map<int, int> updateScore(map<int, int> m, int s){
    map<int, int> ret;
    ret[s]++;
    for(auto &p : m) ret[p.first]++, ret[p.first + s]++;
    // for(auto &p : ret) cout << "updateScore(ret): " << p.first << " ";
    // cout << endl;
    return ret;
}

int main() {
    
    // 1. 入力情報取得.
    int N;
    cin >> N;
    int p[N + 1];
    p[0] = 0;
    for(int i = 1; i < N + 1; ++i) cin >> p[i];
    
    // 2. sort.
    sort(p, p + N + 1);

    // 3. ありうる得点を保存.
    map<int, int> m;
    m[p[0]]++;
    for(int i = 1; i < N + 1; i++){
        map<int, int> lm = updateScore(m, p[i]);
        swap(m, lm);
    }
    // for(auto &p : m) cout << p.first << " ";

    // 4. 出力.
    int ans = 0;
    for(auto &p : m) if(p.second > 0) ans++;
    cout << ans << endl;
    return 0;
    
}

// yukicoder の問題を参照.

// No.4 おもりと天秤

// https://yukicoder.me/problems/no/4

#include <bits/stdc++.h>

using namespace std;

// 獲得可能な得点を更新する.

// @param m: 得点のリスト.

// @param s: 得点.

// @return ret: 更新した得点のリスト.

map<int, int> updateScore(map<int, int> m, int s){

map<int, int> ret;

ret[s]++;

for(auto &p : m) ret[p.first]++, ret[p.first + s]++;

// for(auto &p : ret) cout << "updateScore(ret): " << p.first << " ";

// cout << endl;

return ret;

}

int main() {

// 1. 入力情報取得.

int N;

cin >> N;

int p[N + 1];

p[0] = 0;

for(int i = 1; i < N + 1; ++i) cin >> p[i];

// 2. sort.

sort(p, p + N + 1);

// 3. ありうる得点を保存.

map<int, int> m;

m[p[0]]++;

for(int i = 1; i < N + 1; i++){

map<int, int> lm = updateScore(m, p[i]);

swap(m, lm);

}

// for(auto &p : m) cout << p.first << " ";

// 4. 出力.

int ans = 0;

for(auto &p : m) if(p.second > 0) ans++;

cout << ans << endl;

return 0;

}

■参照サイト
Typical DP Contest
No.4 おもりと天秤

2019年6月3日

C++ の動作確認をしてみた（６９）

C++の練習を兼ねて, Educational DP Contest / DP まとめコンテストの問題P (P – Independent Set) を解いてみた.

■感想.
1. どこかで類題を見た記憶があったので, 探したところ, AtCoder Beginner Contest 036(D – 塗り絵) に似ていることが分かった.
2. 差分は, N = 1 を含める(本問)か, 含めないかのようだった.

■C++版プログラム(問題P／AC版).

// 下記を, 一部修正.
// 解き直し.
// ABC #036 解説.
// http://abc036.contest.atcoder.jp/data/abc/036/editorial.pdf
#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)

typedef long long LL;
const int LIMIT = 100000;
const LL MOD = 1e9 + 7;

struct edge {
    int to;    // 次の頂点.
    int cost;  // コスト.
};

struct vertex {
    int id;        // 頂点番号.
    int distance;  // 指定された頂点(根)からの距離.
};

int depth[LIMIT];
vector<edge> tree[LIMIT];

// AtCoder Beginner Contest 070 (問題D Transit Tree Path) を参照.
// https://img.atcoder.jp/abc070/editorial.pdf
// 深さ優先探索(depth-first search).
// @param c: 探索地点となる頂点.
// @param b: 探索地点から見て, 前回探索済の頂点.
// @param d: 探索開始地点からの距離.
// @return : 特に無し.
void dfs(int c, int b, int d) {
    depth[c] = d;
    for (auto &e : tree[c]) {
        if (e.to == b) continue;
        dfs(e.to, c, d + e.cost);
    }
}

int main() {
    
    // 1. 入力情報取得.
    int N;
    cin >> N;
    map<int, int> m; // 開始頂点取得用.
    FOR(i, 0, N - 1) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        tree[a].push_back({b, 1});
        tree[b].push_back({a, 1});
        m[a]++;
        m[b]++;
    }
    
    // 2. N = 1 の 場合は, 終了(※本問用で追加).
    if(N == 1){
        cout << 2 << endl;
        return 0;
    }
    
    // 3. 探索開始の頂点(根)を取得し, 各頂点までの最短距離を保存.
    int root = -1;
    for(auto &p : m) {
        if(p.second == 1) {
            root = p.first;
            break;
        }
    }
    dfs(root, -1, 0);
    // cout << "root=" << root << endl;
    // FOR(i, 0, N) for(auto &p : tree[i]) cout << "i=" << i << " to=" << p.to << endl;
    // FOR(i, 0, N) cout << depth[i] << " ";
    
    // 4. 解説通り(色の塗り方の数をカウント).
    // -> tree DP を 使って解くとのこと.
    // 探索開始の頂点(根) から遠い順に, f, g の 値を計算していく.
    
    // 4-1. 頂点と距離のセットで保管.
    vector<vertex> vertexes;
    FOR(i, 0, N) {
        vertex v;
        v.id = i;
        v.distance = depth[i];
        vertexes.push_back(v);
    }
    
    // 4-2. 距離で, 降順sort.
    sort(vertexes.begin(), vertexes.end(), [](const vertex& x, const vertex& y) {return x.distance > y.distance;});
    
    // 4-3. f, g を 帰納的に計算.
    LL f[N] = {};
    LL g[N] = {};
    for(auto &x : vertexes) {
        // 頂点 x を 親とする部分木で, x と 隣り合っている頂点(xの子)を探索.
        int p = x.id;  // 親の頂点番号.
        LL lf = 1LL;
        LL lg = 1LL;
        // 隣接している, かつ, 探索開始の頂点(根) からより遠い場合は, xの子 と識別.
        for(auto &v : tree[p]) {
            int c = v.to;  // 子の候補となる頂点番号.
            if(depth[p] < depth[c]) {
                lg *= f[c];
                lf *= g[c];
                lg %= MOD;
                lf %= MOD;
            }
        }
        // f, g を 更新.
        lf += lg;
        lf %= MOD;
        f[p] = lf;
        g[p] = lg;
    }
    // FOR(i, 0, N) cout << f[i] << " ";
    // cout << endl;
    // FOR(i, 0, N) cout << g[i] << " ";
    
    // 5. 出力 ～ 後処理.
    LL ans = f[root];
    cout << ans << endl;
    return 0;

}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

// 下記を, 一部修正.

// 解き直し.

// ABC #036 解説.

// http://abc036.contest.atcoder.jp/data/abc/036/editorial.pdf

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)

typedef long long LL;

const int LIMIT = 100000;

const LL MOD = 1e9 + 7;

struct edge {

int to; // 次の頂点.

int cost; // コスト.

};

struct vertex {

int id; // 頂点番号.

int distance; // 指定された頂点(根)からの距離.

};

int depth[LIMIT];

vector<edge> tree[LIMIT];

// AtCoder Beginner Contest 070 (問題D Transit Tree Path) を参照.

// https://img.atcoder.jp/abc070/editorial.pdf

// 深さ優先探索(depth-first search).

// @param c: 探索地点となる頂点.

// @param b: 探索地点から見て, 前回探索済の頂点.

// @param d: 探索開始地点からの距離.

// @return : 特に無し.

void dfs(int c, int b, int d) {

depth[c] = d;

for (auto &e : tree[c]) {

if (e.to == b) continue;

dfs(e.to, c, d + e.cost);

}

int main() {

// 1. 入力情報取得.

int N;

cin >> N;

map<int, int> m; // 開始頂点取得用.

FOR(i, 0, N - 1) {

int a, b;

cin >> a >> b;

a--, b--;

tree[a].push_back({b, 1});

tree[b].push_back({a, 1});

m[a]++;

m[b]++;

}

// 2. N = 1 の場合は, 終了(※本問用で追加).

if(N == 1){

cout << 2 << endl;

return 0;

}

// 3. 探索開始の頂点(根)を取得し, 各頂点までの最短距離を保存.

int root = -1;

for(auto &p : m) {

if(p.second == 1) {

root = p.first;

break;

}

dfs(root, -1, 0);

// cout << "root=" << root << endl;

// FOR(i, 0, N) for(auto &p : tree[i]) cout << "i=" << i << " to=" << p.to << endl;

// FOR(i, 0, N) cout << depth[i] << " ";

// 4. 解説通り(色の塗り方の数をカウント).

// -> tree DP を使って解くとのこと.

// 探索開始の頂点(根) から遠い順に, f, g の値を計算していく.

// 4-1. 頂点と距離のセットで保管.

vector<vertex> vertexes;

FOR(i, 0, N) {

vertex v;

v.id = i;

v.distance = depth[i];

vertexes.push_back(v);

}

// 4-2. 距離で, 降順sort.

sort(vertexes.begin(), vertexes.end(), [](const vertex& x, const vertex& y) {return x.distance > y.distance;});

// 4-3. f, g を帰納的に計算.

LL f[N] = {};

LL g[N] = {};

for(auto &x : vertexes) {

// 頂点 x を親とする部分木で, x と隣り合っている頂点(xの子)を探索.

int p = x.id; // 親の頂点番号.

LL lf = 1LL;

LL lg = 1LL;

// 隣接している, かつ, 探索開始の頂点(根) からより遠い場合は, xの子と識別.

for(auto &v : tree[p]) {

int c = v.to; // 子の候補となる頂点番号.

if(depth[p] < depth[c]) {

lg *= f[c];

lf *= g[c];

lg %= MOD;

lf %= MOD;

}

// f, g を更新.

lf += lg;

lf %= MOD;

f[p] = lf;

g[p] = lg;

}

// FOR(i, 0, N) cout << f[i] << " ";

// cout << endl;

// FOR(i, 0, N) cout << g[i] << " ";

// 5. 出力～後処理.

LL ans = f[root];

cout << ans << endl;

return 0;

}

■参照サイト
Educational DP Contest / DP まとめコンテスト
 AtCoder Beginner Contest 036 (D – 塗り絵)

C++の練習を兼ねて, AtCoder Regular Contest 059 の 問題F (F – バイナリハック / Unhappy Hacking) を解いてみた.

C++の練習を兼ねて, Typical DP Contest の 問題A (A – コンテスト) を解いてみた.

C++の練習を兼ねて, Educational DP Contest / DP まとめコンテスト の 問題P (P – Independent Set) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 059 の問題F (F – バイナリハック / Unhappy Hacking) を解いてみた.

C++の練習を兼ねて, Typical DP Contest の問題A (A – コンテスト) を解いてみた.

C++の練習を兼ねて, Educational DP Contest / DP まとめコンテストの問題P (P – Independent Set) を解いてみた.