C++の練習を兼ねて, AtCoder Beginner Contest 250 の 問題E (Prefix Equality) を解いてみた.
■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に実装したところ, AC版に到達できた.
2. 集合の性質を上手く使うことで, 高速判定できる点が, 大変参考になったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 250 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題E／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 |
// 解き直し. // https://atcoder.jp/contests/abc250/editorial/3906 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using vi = vector<int>; #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[202020], b[202020], pa[202020], pb[202020], q[202020]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N) scanf("%d", &a[i]); rep(i, N) scanf("%d", &b[i]); // 2. 事前計算①. set<int> aSt, bSt; vi va, vb; rep(i, N){ // 整数列 A. if(!aSt.count(a[i])) va.pb(a[i]); aSt.insert(a[i]); pa[i] = aSt.size(); // 整数列 B. if(!bSt.count(b[i])) vb.pb(b[i]); bSt.insert(b[i]); pb[i] = bSt.size(); } // 3. 事前計算②. set<int> st; int na = va.size(), nb = vb.size(); rep(i, N){ // 整数列 A. if(i < na){ if(st.count(va[i])) st.erase(va[i]); else st.insert(va[i]); } // 整数列 B. if(i < nb){ if(st.count(vb[i])) st.erase(vb[i]); else st.insert(vb[i]); } // サイズ. q[i + 1] = st.size(); } // 4. クエリ回答. int Q; scanf("%d", &Q); rep(i, Q){ // 4-1. クエリ入力情報. int x, y; scanf("%d %d", &x, &y); --x, --y; // 4-2. 出力. if(pa[x] != pb[y]) puts("No"); else printf("%s\n", (!q[pa[x]]) ? "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 |
[入力例] 5 1 2 3 4 5 1 2 2 4 3 7 1 1 2 2 2 3 3 3 4 4 4 5 5 5 [出力例] Yes Yes Yes No No Yes No ※AtCoderテストケースより [入力例] 15 1 5 2 3 2 2 1 2 4 5 2 4 5 3 3 2 5 3 1 5 5 4 1 2 3 1 5 4 2 3 10 2 5 5 5 6 5 3 4 11 7 6 10 9 7 7 8 9 9 10 11 [出力例] No Yes Yes No Yes No Yes No Yes Yes [入力例] 100 5 11 6 10 12 11 7 3 5 13 6 18 13 10 2 5 4 19 11 20 13 12 4 11 1 16 16 20 19 20 13 13 10 12 8 9 11 6 5 7 2 9 4 19 9 4 15 2 17 14 18 8 18 1 19 1 13 18 2 14 11 14 6 10 19 4 10 14 5 4 8 14 11 11 14 9 12 18 20 18 1 18 9 6 19 10 19 14 5 6 8 9 12 3 15 10 11 9 11 16 10 5 12 5 11 7 6 3 7 2 18 11 13 3 4 19 7 18 19 4 5 20 8 12 12 19 1 18 6 16 3 5 20 9 10 14 17 4 13 18 20 13 19 16 19 3 5 13 18 1 14 15 10 13 10 13 18 13 5 18 10 16 18 2 13 6 11 1 1 1 16 18 5 10 11 11 1 6 5 17 3 2 1 12 18 9 9 7 18 13 4 2 9 12 18 18 8 15 20 1 10 7 7 3 90 20 22 59 12 18 16 50 55 35 32 50 60 25 97 88 99 [出力例] Yes No Yes No Yes Yes Yes Yes No Yes |
■参照サイト
AtCoder Beginner Contest 250