C++の練習を兼ねて, AtCoder Beginner Contest 186 の 問題F (Rook on Grid) を解いてみた.
■感想.
1. 問題F は, 解答方針が見えなかったので, 解説を参考に実装したところ, AC版に到達できたので良かったと思う.
2. Binary Indexed Tree の 復習が出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
3. 個人的には, 非常に面白い問題に感じた.
4. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Beginner Contest 186 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題F／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 87 88 |
// 解き直し. // https://atcoder.jp/contests/abc186/editorial/400 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using vi = vector<int>; using vvi = vector<vi>; 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 pb push_back int p[202020], q[202020]; // Binary Indexed Tree (Fenwick Tree) // https://youtu.be/lyHk98daDJo?t=7960 template<typename T> struct BIT{ int n; vector<T> d; BIT(int n = 0) : n(n), d(n + 1) {} void add(int i, T x = 1){ for(i++; i <= n; i += i & -i) d[i] += x; } T sum(int i){ T x = 0; for(i++; i; i -= i & -i) x += d[i]; return x; } T sum(int l, int r){ return sum(r - 1) - sum(l - 1); } }; int main(){ // 1. 入力情報. int H, W, M; scanf("%d %d %d", &H, &W, &M); vvi gx(H), gy(W); rep(i, 202020) p[i] = H, q[i] = W; rep(i, M){ int x, y; scanf("%d %d", &x, &y); x--, y--; // y列目で, 最も上の場所を保存. p[y] = min(p[y], x); // x行目で, 最も左の場所を保存. q[x] = min(q[x], y); // 障害物情報を保存. gx[x].pb(y); gy[y].pb(x); } // 2. 列方向で, 到達可能なマスをカウント. LL ans = 0; rep(i, q[0]) ans += (LL)p[i]; // 3. 行方向で, 到達可能なマスをカウント. BIT<int> ft(W + 1); // 3-1. 1行目. repx(i, q[0], W) ft.add(i, 1); // 3-2. 2行目以降. // hand_01.txt などの WA回避のため, H でなく, min(p[0], H) に 修正. repx(i, 1, min(p[0], H)){ // hand_01.txt などの WA回避のため, 障害物情報を保存するように修正. // i行目における障害物情報を確認. for(auto &e : gx[i]){ // e での 値は？ int c = ft.sum(e, e + 1); // e に, 1 を 加算してない場合は, 加算. if(!c) ft.add(e, 1); } // 到達可能なマスをカウント. ans += (LL)ft.sum(0, q[i]); } // 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 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 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 |
[入力例] 4 3 2 2 2 3 3 [出力例] 10 ※AtCoderテストケースより [入力例] 5 4 4 3 2 3 4 4 2 5 2 [出力例] 14 ※AtCoderテストケースより [入力例] 200000 200000 0 [出力例] 40000000000 ※AtCoderテストケースより [入力例] 8 8 6 8 1 6 1 3 3 5 4 4 6 1 5 [出力例] 26 ※AtCoder解説より [入力例] 3141 5926 53 741 4553 263 4518 1923 2000 1590 3092 1153 5152 998 2557 2225 4785 1507 4263 926 2045 1734 1779 2450 1861 2418 3157 1262 614 1378 2739 469 3426 1535 177 666 2261 986 1069 664 2974 8 2189 1085 2284 127 63 1313 1270 2447 5096 1742 4455 2381 1950 1642 2125 3019 3885 3036 1955 1610 5587 2553 2608 2793 4949 1899 711 2295 2411 2227 5171 2007 1287 616 2464 2863 3904 2095 103 2426 1714 3032 947 1939 434 1555 5230 1402 1732 1257 5092 580 4158 58 5762 1469 1991 159 4216 1650 938 2917 5046 630 1018 1444 5479 [出力例] 18612801 [入力例] 12345 54321 111 3380 7603 2766 42189 1692 18776 847 36182 6332 34339 11353 7128 462 17645 7300 10221 6547 8730 9611 18279 5337 49433 10626 18701 6238 36344 5599 25160 7572 53853 9656 30278 3187 27962 1237 50246 6766 14957 12024 13850 10233 33769 4347 23261 7616 48070 3443 49325 5801 23729 10088 2083 10363 14495 11812 53334 5210 18384 11507 17284 789 34256 1136 43881 5459 28138 3989 3274 3842 13060 10151 40796 8552 48826 3581 47710 5227 35431 5380 22096 1929 38879 5244 20145 3328 4439 2026 16771 3600 17493 850 51513 10874 46777 3141 45219 9618 28523 6407 42392 10157 16575 9489 28181 9545 30078 7506 53839 10974 1600 526 45719 551 33405 2340 52053 83 1445 401 52385 5220 31082 4020 5801 6216 32678 1550 8118 3221 40984 9671 9761 9229 7774 12056 13481 9020 11706 12324 11278 9948 18686 3073 53434 82 24598 11194 1886 9930 41186 1222 32892 3500 28528 3732 32046 9251 44305 7588 5529 3385 16742 1680 3461 2865 46835 7031 53358 2774 10342 2688 42340 1202 33398 3525 40694 3965 47463 9307 33335 1603 14673 12331 11107 7573 52038 5632 30129 3194 52099 948 28377 4246 10173 4775 22690 5854 17150 10193 4767 9890 21905 8528 31920 3299 35700 9584 33188 1046 13669 7802 22358 4017 52000 12201 34348 6369 15326 6884 29200 4376 9989 [出力例] 670589166 |
■参照サイト
パナソニックプログラミングコンテスト（AtCoder Beginner Contest 186）
Binary Indexed Tree (Fenwick Tree)