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

C++の練習を兼ねて, AtCoder Regular Contest 150 の問題C (Path and Subsequence) を解いてみた.

■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に提出して, ようやく, AC版に到達出来た.
2. 個人的には, 01-BFSについて復習出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc150/editorial/4867
// 01-BFSのちょっと丁寧な解説
// https://betrue12.hateblo.jp/entry/2018/12/08/000020
// 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 pof pop_front
#define pob pop_back
#define pub push_back
#define puf push_front
int a[101010], b[101010];

int main(){
    
    // 1. 入力情報.
    int N, M, K;
    scanf("%d %d %d", &N, &M, &K);
    vvi G(N + 1);
    rep(i, M){
        int u, v;
        scanf("%d %d", &u, &v);
        G[u].pub(v);
        G[v].pub(u);
    }
    rep(i, N) scanf("%d", &a[i + 1]);
    rep(i, K) scanf("%d", &b[i + 1]);
    
    // 2. 01-BFS(解説通り).
    // https://ja.wikipedia.org/wiki/幅優先探索
    // -> 01-BFS版へ修正.
    auto bfs01 = [&](int *d){
        // 空 の deque.
        deque<int> dq;
        
        // 未確定地点 を deque に追加.
        repx(i, 1, N + 1) dq.pub(i);
        
        // deque が 空 になるまで繰り返す.
        while(!dq.empty()){
            // deque から取り出す.
            int u = dq.front();
            dq.pof();
            
            // コスト更新(隣接頂点).
            for(auto &v : G[u]){
                // 整数列 A (要素) が, 整数列 B (要素) と一致しなかった.
                if(a[v] != b[d[u] + 1]){
                    if(d[v] > d[u] + 0){
                        d[v] = d[u] + 0;
                        dq.puf(v);
                    }
                }
                
                // 整数列 A (要素) が, 整数列 B (要素) と一致した.
                if(a[v] == b[d[u] + 1]){
                    if(d[v] > d[u] + 1){
                        d[v] = d[u] + 1;
                        dq.pub(v);
                    }
                }
            }
        }
    };
    int d[N + 1];
    rep(i, N + 1) d[i] = K + 1;
    d[1] = (a[1] == b[1]);
    bfs01(d);
    
    // 3. 出力.
    printf("%s\n", (d[N] == K) ? "Yes" : "No");
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc150/editorial/4867

// 01-BFSのちょっと丁寧な解説

// https://betrue12.hateblo.jp/entry/2018/12/08/000020

// 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 pof pop_front

#define pob pop_back

#define pub push_back

#define puf push_front

int a[101010], b[101010];

int main(){

// 1. 入力情報.

int N, M, K;

scanf("%d %d %d", &N, &M, &K);

vvi G(N + 1);

rep(i, M){

int u, v;

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

G[u].pub(v);

G[v].pub(u);

}

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

rep(i, K) scanf("%d", &b[i + 1]);

// 2. 01-BFS(解説通り).

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

// -> 01-BFS版へ修正.

auto bfs01 = [&](int *d){

// 空の deque.

deque<int> dq;

// 未確定地点を deque に追加.

repx(i, 1, N + 1) dq.pub(i);

// deque が空になるまで繰り返す.

while(!dq.empty()){

// deque から取り出す.

int u = dq.front();

dq.pof();

// コスト更新(隣接頂点).

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

// 整数列 A (要素) が, 整数列 B (要素) と一致しなかった.

if(a[v] != b[d[u] + 1]){

if(d[v] > d[u] + 0){

d[v] = d[u] + 0;

dq.puf(v);

}

// 整数列 A (要素) が, 整数列 B (要素) と一致した.

if(a[v] == b[d[u] + 1]){

if(d[v] > d[u] + 1){

d[v] = d[u] + 1;

dq.pub(v);

}

};

int d[N + 1];

rep(i, N + 1) d[i] = K + 1;

d[1] = (a[1] == b[1]);

bfs01(d);

// 3. 出力.

printf("%s\n", (d[N] == K) ? "Yes" : "No");

return 0;

}

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

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

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

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

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

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

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

[出力例]
Yes

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

[出力例]
Yes

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

[出力例]
Yes

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

128

129

130

[入力例]

6 6 3

1 2

1 3

2 4

3 5

4 6

5 6

1 2 4 5 2 6

1 2 6

[出力例]

Yes

※AtCoderのテストケースより

[入力例]

5 5 3

1 2

2 3

3 4

4 5

2 5

1 2 3 5 2

1 3 2

[出力例]

※AtCoderのテストケースより

[入力例]

10 20 3

5 6

5 10

5 7

3 5

3 7

2 6

3 8

4 5

5 8

7 10

1 6

1 9

4 6

1 2

1 4

6 7

4 8

2 5

3 10

6 9

2 5 8 5 1 5 1 1 5 10

2 5 1

[出力例]

Yes

※AtCoderのテストケースより

[入力例]

10 12 4

1 2

1 3

2 4

3 4

4 5

4 6

5 7

6 7

7 8

7 9

8 10

9 10

3 1 4 1 5 9 2 6 5 3

3 1 2 3

[出力例]

Yes

[入力例]

11 16 4

1 2

2 5

2 3

1 3

3 4

4 5

5 6

5 7

4 7

4 8

6 9

7 9

7 10

8 10

9 11

10 11

5 7 7 1 1 3 3 3 2 2 10

5 7 1 3 2 10

[出力例]

Yes

[入力例]

15 21 5

1 2

1 4

1 5

2 3

3 4

3 5

3 6

6 7

6 8

6 9

6 10

6 11

7 12

8 12

9 12

10 12

11 12

12 13

12 14

13 15

14 15

3 1 4 1 5 9 2 6 5 3 5 8 9 7 9

3 4 9 8 9

[出力例]

Yes

■参照サイト
AtCoder Regular Contest 150
01-BFSのちょっと丁寧な解説

C++の練習を兼ねて, AtCoder Regular Contest 150 の 問題C (Path and Subsequence) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 150 の問題C (Path and Subsequence) を解いてみた.

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