C++の練習を兼ねて, AtCoder Beginner Contest 035 の 問題B (B – ドローン) ～ 問題C (C – オセロ) を解いてみた.
■感想.
1. 問題B は, ‘?’ を カウント後, 後から評価する点が面白いと感じた.
2. 問題C は, 遅延評価セグメント木 が 使えそうに見えたので, 下記, 参照サイトのライブラリをもとに, 提出した内容である.
※新しい知識となるが, セグメント木の理解が, 全然追い付いてないので, いろいろなパターンの問題に触れてみて, 本質をつかんでいく必要があると感じた.
本家のサイトAtCoder Beginner Contest 035 解説をご覧下さい.
■C++版プログラム(問題B／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 |
#include <bits/stdc++.h> using namespace std; #define FOR(i, a, b) for(int i = (a); i < (b); ++i) int main() { // 1. 入力情報取得. string S; int T; cin >> S >> T; // 2. '?' を カウントしつつ, 文字列最終まで, 走査. int question = 0; int posX = 0, posY = 0; FOR(i, 0, S.size()){ char c = S[i]; // 命令が, 'L' の 場合. if(c == 'L') posX--; // 命令が, 'R' の 場合. if(c == 'R') posX++; // 命令が, 'U' の 場合. if(c == 'U') posY++; // 命令が, 'D' の 場合. if(c == 'D') posY--; // 命令が, '?' の 場合. if(c == '?') question++; } // 3. 最大値 を 計算. // int maxMD = 0; // 3-1. posX > 0 の 場合, 命令'?' は, 'R' だったと推定. // if(posX > 0) maxMD = posX + abs(posY) + question; // 3-2. posX < 0 の 場合, 命令'?' は, 'L' だったと推定. // if(posX < 0) maxMD = abs(posX) + abs(posY) + question; // 3-3. posX == 0 かつ posY > 0 の 場合, 命令'?' は, 'U' だったと推定. // if(posX == 0 && posY > 0) maxMD = posY + question; // 3-4. posX == 0 かつ posY < 0 の 場合, 命令'?' は, 'D' だったと推定. // if(posX == 0 && posY > 0) maxMD = abs(posY) + question; // 3-5. posX == 0 かつ posY == 0 の 場合, 命令'?' は, 'R' だったと推定(※なんでも良さそう). // if(posX == 0 && posY == 0) maxMD = question; // -> 3-1. ～ 3-5. は, 以下に集約されるはず. int maxMD = abs(posX) + abs(posY) + question; // 4. 最小値 を 計算. // -> 直観的には, abs(posX) + abs(posY) から question を 引いた数になりそう. // question が 非常に大きい場合は, 差分 を 2 で割った余りになりそう. int minMD = 0; if(abs(posX) + abs(posY) >= question) minMD = abs(posX) + abs(posY) - question; else minMD = question - abs(posX) - abs(posY), minMD %= 2; // 5. 出力 ～ 後処理. if(T == 1) cout << maxMD << endl; else cout << minMD << endl; return 0; } |
■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 81 82 83 84 85 86 |
// AC版. // ※※※ 以下のライブラリを使って, 解答を作成 ※※※. // 遅延評価セグメント木をソラで書きたいあなたに. // http://tsutaj.hatenablog.com/entry/2017/03/30/224339 // http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2236726 #include <bits/stdc++.h> using namespace std; using LL = long long; int const INF = INT_MAX; int N, Q; struct LazySegmentTree { private: int n; vector<LL> node, lazy; public: LazySegmentTree(vector<LL> v) { int sz = (int)v.size(); n = 1; while(n < sz) n *= 2; node.resize(2 * n - 1); lazy.resize(2 * n - 1, 0); // 元配列 の 値 を, セグメント木のノード に 保存. for(int i = 0; i < sz; i++) node[i + n - 1] = v[i]; for(int i = n - 2; i >= 0; i--) node[i] = node[i * 2 + 1] + node[i * 2 + 2]; } void eval(int k, int l, int r) { if(lazy[k] != 0) { node[k] += lazy[k]; if(r - l > 1) { lazy[2 * k + 1] += lazy[k] / 2; lazy[2 * k + 2] += lazy[k] / 2; } lazy[k] = 0; } } void add(int a, int b, LL x, int k = 0, int l = 0, int r = -1) { if(r < 0) r = n; eval(k, l, r); if(b <= l || r <= a) return; if(a <= l && r <= b) { lazy[k] += (r - l) * x; eval(k, l, r); } else { add(a, b, x, 2 * k + 1, l, (l + r) / 2); add(a, b, x, 2 * k + 2, (l + r) / 2, r); node[k] = node[2 * k + 1] + node[2 * k + 2]; } } LL getSum(int a, int b, int k = 0, int l = 0, int r = -1) { if(r < 0) r = n; eval(k, l, r); if(b <= l || r <= a) return 0; if(a <= l && r <= b) return node[k]; LL vl = getSum(a, b, 2 * k + 1, l, (l + r) / 2); LL vr = getSum(a, b, 2 * k + 2, (l + r) / 2, r); return vl + vr; } }; int main() { // 1. 入力情報取得. int N, Q; cin >> N >> Q; // 2. 遅延評価セグメント木を呼び出す. LazySegmentTree seg(vector<LL>(N, 0)); for(int i = 0; i < Q; i++){ int l, r; cin >> l >> r; seg.add(l - 1, r, 1); } // 3. 出力 ～ 後処理. // 区間和 を mod 2 で, 出力. for(int i = 0; i < N; i++){ int v = seg.getSum(i, i + 1); v %= 2; cout << v; } cout << endl; 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 |
[入力例] 5 4 1 4 2 5 3 3 1 5 [出力例] 01010 ※AtCoderテストケースより [入力例] 20 8 1 8 4 13 8 8 3 18 5 20 19 20 2 7 4 9 [出力例] 10110000011110000000 ※AtCoderテストケースより [入力例] 1 1 1 1 [出力例] 1 [入力例] 5 2 1 2 2 3 [出力例] 10100 [入力例] 7 5 1 3 2 4 1 5 4 6 5 7 [出力例] 0111101 ※実際, 以下のような順で, 更新される. 0000000 ↓ ↓[1, 3] ↓ 1110000 ↓ ↓[2, 4] ↓ 1001000 ↓ ↓[1, 5] ↓ 0110100 ↓ ↓[4, 6] ↓ 0111010 ↓ ↓[5, 7] ↓ 0111101 |