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

C++の練習を兼ねて, AtCoder Beginner Contest 218 の問題G (Game on Tree 2) を解いてみた.

■感想.
1. 問題G は, 方針が見えなかったので, 解説(プログラム)を参考に実装して, AC版に持って行く方針を取った.
2. 苦手な動的計画法(木dp)の訓練を積めたので, 非常に良かったと思う.
3. いったん自力で実装してみたものの, AC版に到達できなかった.
-> 原因としては, 二つの multiset の個数調整で, 実装が正しくなかったこと, dpへの中央値設定(のタイミング, 更新条件)などがあげられると推測する.
いずれにしても, dfsの実装を正しく行うことは, 相変わらず, 直観的に分かりづらく, 難しく感じる(※)ため, 継続して, 今後の課題になっていくと思う.
※dfsの終了条件, dp更新(条件, タイミング)などが, 難しく感じる原因の一つと推測する.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト AtCoder Beginner Contest 218 解説の各リンクをご覧下さい.

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

// 解答不能.
// https://atcoder.jp/contests/abc218/editorial/2607
// -> dfs の 実装パターン を 暗記すること(特に, 終了条件, multiset の 利用方法など).
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
int a[101010], dp[101010];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d", &a[i]);
    vvi G(N);
    rep(i, N - 1){
        int u, v;
        scanf("%d %d", &u, &v);
        u--, v--;
        G[u].pb(v);
        G[v].pb(u);
    }
    
    // 2. 中央値.
    auto f = [&](multiset<int> &l, multiset<int> &r) -> int{
        int m = -1;
        if(l.size() == r.size() + 1){
            auto it = l.end();
            m = *(--it);
        }else{
            auto it1 = l.end();
            auto it2 = r.begin();
            m = (*(--it1) + *it2) / 2;
        }
        return m;
    };
    
    // 3. 個数調整.
    auto g = [&](multiset<int> &l, multiset<int> &r) -> void{
        // 左側の最大値を, 右側に移動.
        if(l.size()){
            auto itr = l.end();
            --itr;
            r.insert(*itr);
            l.erase(itr);
        }
        
        // 左側, 右側のサイズを調整.
        while(l.size() < r.size()){
            l.insert(*r.begin());
            r.erase(r.begin());
        }
        return;
    };
    
    // 4. 削除.
    auto h = [&](multiset<int> &l, multiset<int> &r, int x) -> void{
        auto itr = l.end();
        --itr;
        if(*itr < x) r.erase(r.lower_bound(x));
        else         l.erase(l.lower_bound(x));
        return;
    };
    
    // 5. dfs.
    multiset<int> l, r;
    auto dfs = [&](auto self, int cur, int bef, int d) -> void{
        // 多重集合に, 要素を追加.
        l.insert(a[cur]);
        g(l, r);
        
        // dp更新.
        int mMin = 2020202020;
        int mMax = 0;
        for(int nex : G[cur]){
            if(nex != bef){
                self(self, nex, cur, d + 1);
                mMin = min(mMin, dp[nex]);
                mMax = max(mMax, dp[nex]);
            }
        }
        
        // 中央値設定など.
        if(mMax == 0)  dp[cur] = f(l, r);
        else if(d & 1) dp[cur] = mMin;
        else           dp[cur] = mMax;
        
        // 多重集合から, 要素を削除.
        h(l, r, a[cur]);
        g(l, r);
        
        // 終了.
        return;
    };
    
    // 6. 木dp.
    dfs(dfs, 0, -1, 0);
    
    // 7. 出力.
    printf("%d\n", dp[0]);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

// 解答不能.

// https://atcoder.jp/contests/abc218/editorial/2607

// -> dfs の実装パターンを暗記すること(特に, 終了条件, multiset の利用方法など).

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

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

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

#define repr(i, a, b) for(int i = a; i >= b; i--)

#define pb push_back

int a[101010], dp[101010];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N) scanf("%d", &a[i]);

vvi G(N);

rep(i, N - 1){

int u, v;

scanf("%d %d", &u, &v);

u--, v--;

G[u].pb(v);

G[v].pb(u);

}

// 2. 中央値.

auto f = [&](multiset<int> &l, multiset<int> &r) -> int{

int m = -1;

if(l.size() == r.size() + 1){

auto it = l.end();

m = *(--it);

}else{

auto it1 = l.end();

auto it2 = r.begin();

m = (*(--it1) + *it2) / 2;

}

return m;

};

// 3. 個数調整.

auto g = [&](multiset<int> &l, multiset<int> &r) -> void{

// 左側の最大値を, 右側に移動.

if(l.size()){

auto itr = l.end();

--itr;

r.insert(*itr);

l.erase(itr);

}

// 左側, 右側のサイズを調整.

while(l.size() < r.size()){

l.insert(*r.begin());

r.erase(r.begin());

}

return;

};

// 4. 削除.

auto h = [&](multiset<int> &l, multiset<int> &r, int x) -> void{

auto itr = l.end();

--itr;

if(*itr < x) r.erase(r.lower_bound(x));

else l.erase(l.lower_bound(x));

return;

};

// 5. dfs.

multiset<int> l, r;

auto dfs = [&](auto self, int cur, int bef, int d) -> void{

// 多重集合に, 要素を追加.

l.insert(a[cur]);

g(l, r);

// dp更新.

int mMin = 2020202020;

int mMax = 0;

for(int nex : G[cur]){

if(nex != bef){

self(self, nex, cur, d + 1);

mMin = min(mMin, dp[nex]);

mMax = max(mMax, dp[nex]);

}

// 中央値設定など.

if(mMax == 0) dp[cur] = f(l, r);

else if(d & 1) dp[cur] = mMin;

else dp[cur] = mMax;

// 多重集合から, 要素を削除.

h(l, r, a[cur]);

g(l, r);

// 終了.

return;

};

// 6. 木dp.

dfs(dfs, 0, -1, 0);

// 7. 出力.

printf("%d\n", dp[0]);

return 0;

}

[入力例]
5
2 4 6 8 10
4 5
3 4
1 5
2 4

[出力例]
7
※AtCoderテストケースより

[入力例]
5
6 4 6 10 8
1 4
1 2
1 5
1 3

[出力例]
8
※AtCoderテストケースより

[入力例]
6
2 2 6 4 6 6
1 2
2 3
4 6
2 5
2 6

[出力例]
2
※AtCoderテストケースより

[入力例]
2
6 18
1 2

[出力例]
12

[入力例]
3
6 8 2
1 2
2 3

[出力例]
6

[入力例]
6
6 2 8 12 4 2
1 2
1 6
6 3
6 4
4 5

[出力例]
5

[入力例]
16
8 2 10 12 16 2 4 20 18 14 12 6 4 8 10 6
1 2
1 3
2 4
2 5
4 8
4 9
5 10
5 11
3 6
3 7
6 12
6 13
7 14
7 15
7 16

[出力例]
10

[入力例]
9
18 2 4 18 24 12 8 14 12
1 2
1 3
2 4
2 5
5 6
5 7
7 8
7 9

[出力例]
15

100

101

102

[入力例]

2 4 6 8 10

4 5

3 4

1 5

2 4

[出力例]

※AtCoderテストケースより

[入力例]

6 4 6 10 8

1 4

1 2

1 5

1 3

[出力例]

※AtCoderテストケースより

[入力例]

2 2 6 4 6 6

1 2

2 3

4 6

2 5

2 6

[出力例]

※AtCoderテストケースより

[入力例]

6 18

1 2

[出力例]

[入力例]

6 8 2

1 2

2 3

[出力例]

[入力例]

6 2 8 12 4 2

1 2

1 6

6 3

6 4

4 5

[出力例]

[入力例]

8 2 10 12 16 2 4 20 18 14 12 6 4 8 10 6

1 2

1 3

2 4

2 5

4 8

4 9

5 10

5 11

3 6

3 7

6 12

6 13

7 14

7 15

7 16

[出力例]

[入力例]

18 2 4 18 24 12 8 14 12

1 2

1 3

2 4

2 5

5 6

5 7

7 8

7 9

[出力例]

■参照サイト
AtCoder Beginner Contest 218

C++の練習を兼ねて, AtCoder Beginner Contest 218 の 問題G (Game on Tree 2) を解いてみた.

コメントを残す コメントをキャンセル

C++の練習を兼ねて, AtCoder Beginner Contest 218 の問題G (Game on Tree 2) を解いてみた.

コメントを残すコメントをキャンセル