C++の練習を兼ねて, AtCoder Beginner Contest 243 の 問題C (Collision 2) ～ 問題D (Moves on Binary Tree) を解いてみた.
■感想.
1. 問題C, Dは, 方針を絞り込めたので, AC版に到達できたと思う.
2. 個人的には, 問題Dで, stack の 考え方が使えたので, 非常に面白く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 243 解説 の 各リンク を ご覧下さい.
■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 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using P = pair<int, int>; using vp = vector<P>; using vvp = vector<vp>; #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 #define a first #define b second #define all(x) x.begin(), x.end() int x[202020], y[202020]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); map<int, int> m; rep(i, N){ scanf("%d %d", &x[i], &y[i]); m[y[i]]++; } char s[202020]; scanf("%s", s); // 2. 座標圧縮. int idx = -1; for(auto &p : m) p.b = ++idx; // 3. グループ分け. vvp v(idx + 1); rep(i, N){ // 左. if(s[i] == 'L') v[m[y[i]]].pb({x[i], -1}); // 右. if(s[i] == 'R') v[m[y[i]]].pb({x[i], +1}); } // 4. 衝突判定. bool ok = false; rep(i, idx + 1){ // sort. sort(all(v[i])); // 左向きに移動する人のX座標(最大値). // 右向きに移動する人のX座標(最小値). int l = -1, r = 2020202020; for(auto &p : v[i]){ if(p.b == 1) r = min(r, p.a); else l = max(l, p.a); } // 判定. if(r < l){ ok = true; break; } } // 5. 出力. printf("%s\n", ok ? "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 |
[入力例] 3 2 3 1 1 4 1 RRL [出力例] Yes ※AtCoderテストケースより [入力例] 2 1 1 2 1 RR [出力例] No ※AtCoderテストケースより [入力例] 10 1 3 1 4 0 0 0 2 0 4 3 1 2 4 4 2 4 4 3 3 RLRRRLRLRR [出力例] Yes ※AtCoderテストケースより [入力例] 5 1 3 5 3 7 2 1 2 2 2 RRLLR [出力例] Yes [入力例] 7 5 1 10 2 11 3 18 4 15 3 11 2 8 1 LLRRLRL [出力例] Yes |
■C++版プログラム(問題D／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 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; #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 puf push_front #define pub push_back int main(){ // 1. 入力情報. int N; LL X; char s[1010101]; scanf("%d %lld %s", &N, &X, s); // 2. 操作を保存. deque<char> dq; rep(i, N){ // 空. if(dq.empty()){ dq.pub(s[i]); continue; } // U. if(s[i] == 'U'){ char c = dq.back(); if(c != 'U') dq.pob(); else dq.pub(s[i]); } // L or R. if(s[i] != 'U') dq.pub(s[i]); } // 3. 移動. LL ans = X; while(!dq.empty()){ char c = dq.front(); dq.pof(); // U. if(c == 'U') ans >>= 1; // L. if(c == 'L') ans <<= 1; // R. if(c == 'R') ans <<= 1, ++ans; } // 4. 出力. printf("%lld\n", ans); 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 |
[入力例] 3 2 URL [出力例] 6 ※AtCoderテストケースより [入力例] 4 500000000000000000 RRUU [出力例] 500000000000000000 ※AtCoderテストケースより [入力例] 30 123456789 LRULURLURLULULRURRLRULRRRUURRU [出力例] 126419752371 ※AtCoderテストケースより [入力例] 5 5 ULRRU [出力例] 9 [入力例] 30 2020 RULULUURURRLRRURRRULLULLRURLRR [出力例] 8280971 [入力例] 50 20220312 ULUURLUURULRRLLRULLLRRURULRURRRURRUURRLRRURLURLURR [出力例] 5300633865183 |
■参照サイト
AtCoder Beginner Contest 243
thanks a lot
Thank you for your comments.