C++の練習を兼ねて, AtCoder Regular Contest 150 の 問題C (Path and Subsequence) を解いてみた.
■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に提出して, ようやく, AC版に到達出来た.
2. 個人的には, 01-BFSについて復習出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 150 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題C/AC版).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
// 解き直し. // 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; } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 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 [出力例] 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 |