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

C++の練習を兼ねて, AtCoder Regular Contest 156 の問題C (Tree and LCS) を解いてみた.

■感想.
1. 問題C は, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 解説のロジックで, 順列を構築できる点が, 非常に不思議な印象を受けた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc156/editorial/5724
// 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 d[5050], ans[5050];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    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);
        ++d[u];
        ++d[v];
    }
    
    // 2. 解の構築.
    queue<int> q;
    rep(i, N) if(d[i] == 1) q.push(i);
    while(q.size() >= 2){
        // 頂点を二つ取り出す.
        int u = q.front();
        q.pop();
        int v = q.front();
        q.pop();
        
        // 頂点の次数(更新).
        --d[u];
        --d[v];
        
        // 順列を保存.
        ans[u] = v;
        ans[v] = u;
        
        // 頂点 u の 隣接頂点.
        for(auto &x : G[u]){
            if(!d[x] || x == v) continue;
            if(--d[x] == 1) q.push(x);
        }
        
        // 頂点 v の 隣接頂点.
        for(auto &x : G[v]){
            if(!d[x] || x == u) continue;
            if(--d[x] == 1) q.push(x);
        }
    }
    
    // 3. N が 奇数.
    if(N & 1) ans[q.front()] = q.front();
    
    // 4. 出力.
    rep(i, N) printf("%d%s", ans[i] + 1, (i < N - 1) ? " " : "\n");
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc156/editorial/5724

// 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 d[5050], ans[5050];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

++d[u];

++d[v];

}

// 2. 解の構築.

queue<int> q;

rep(i, N) if(d[i] == 1) q.push(i);

while(q.size() >= 2){

// 頂点を二つ取り出す.

int u = q.front();

q.pop();

int v = q.front();

q.pop();

// 頂点の次数(更新).

--d[u];

--d[v];

// 順列を保存.

ans[u] = v;

ans[v] = u;

// 頂点 u の隣接頂点.

for(auto &x : G[u]){

if(!d[x] || x == v) continue;

if(--d[x] == 1) q.push(x);

}

// 頂点 v の隣接頂点.

for(auto &x : G[v]){

if(!d[x] || x == u) continue;

if(--d[x] == 1) q.push(x);

}

// 3. N が奇数.

if(N & 1) ans[q.front()] = q.front();

// 4. 出力.

rep(i, N) printf("%d%s", ans[i] + 1, (i < N - 1) ? " " : "\n");

return 0;

}

[入力例]
3
1 2
2 3

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

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

[出力例]
3 4 1 2
※AtCoderのテストケースより

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

[出力例]
1 5 4 3 2

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

[出力例]
3 7 1 5 4 10 2 9 8 6

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

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

[入力例]

1 2

2 3

[出力例]

3 2 1

※AtCoderのテストケースより

[入力例]

2 1

2 3

2 4

[出力例]

3 4 1 2

※AtCoderのテストケースより

[入力例]

2 3

1 3

4 1

5 4

[出力例]

1 5 4 3 2

[入力例]

1 3

1 5

3 2

4 3

6 5

6 7

8 6

9 4

4 10

[出力例]

3 7 1 5 4 10 2 9 8 6

[入力例]

10 1

10 4

4 5

11 4

12 5

13 5

13 9

13 17

11 7

11 16

16 15

16 6

16 18

3 1

8 1

14 3

2 3

19 8

8 20

[出力例]

11 6 20 10 8 2 9 5 7 4 1 14 16 12 17 13 15 19 18 3

■参照サイト
AtCoder Regular Contest 156

C++の練習を兼ねて, AtCoder Regular Contest 156 の 問題C (Tree and LCS) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 156 の問題C (Tree and LCS) を解いてみた.

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