C++の練習を兼ねて, AtCoder Beginner Contest 271 の 問題F (XOR on Grid Path) を解いてみた.
■感想.
1. 問題Fは, 方針が見えなかったため, 解説を参考に, AC版に到達できた.
2. 半分全列挙の復習が出来たので良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 271 解説 の 各リンク を ご覧下さい.
■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 |
// 解き直し. // https://atcoder.jp/contests/abc271/editorial/4925 // 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 a first #define b second int a[22][22]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N) rep(j, N) scanf("%d", &a[i][j]); // 2. 半分全列挙. // 2-1. マス(1, 1) ～ 対角線上のマス(x, y). // → 二進数の各桁を, 以下の移動とみなす. // 1: マス(i, j) → マス(i + 1, j) // 0: マス(i, j) → マス(i, j + 1) map<int, int> pXor[N]; rep(i, 1 << (N - 1)){ int x = 0, y = 0; int p = a[x][y]; rep(j, N - 1){ if(i & (1 << j)) ++x; else ++y; p ^= a[x][y]; } ++pXor[__builtin_popcount(i)][p]; } // 2-2. 対角線上のマス(N, N) ～ マス(x, y). // → 二進数の各桁を, 以下の移動とみなす. // 1: マス(i, j) → マス(i - 1, j) // 0: マス(i, j) → マス(i, j - 1) map<int, int> qXor[N]; rep(i, 1 << (N - 1)){ int x = N - 1, y = N - 1; int q = a[x][y]; rep(j, N - 1){ if(i & (1 << j)) --x; else --y; q ^= a[x][y]; } ++qXor[N - 1 - __builtin_popcount(i)][q]; } // 3. 集計. LL ans = 0; rep(i, N){ // マス(x, y) を 固定して, 全探索. for(auto &p : pXor[i]){ int cur = a[i][N - 1 - i] ^ p.a; if(qXor[i].count(cur)) ans += (LL)p.b * (LL)qXor[i][cur]; } } // 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 |
[入力例] 3 1 5 2 7 0 5 4 2 3 [出力例] 2 ※AtCoderテストケースより [入力例] 2 1 2 2 1 [出力例] 0 ※AtCoderテストケースより [入力例] 10 1 0 1 0 0 1 0 0 0 1 0 0 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 0 0 0 0 1 0 0 0 1 1 0 0 1 0 0 1 1 0 1 1 0 1 0 1 0 0 0 1 0 0 1 1 0 1 1 1 0 0 0 1 1 0 0 0 1 1 0 0 1 1 0 1 0 1 0 1 1 0 0 0 0 0 0 1 0 1 1 0 0 1 1 1 0 [出力例] 24307 ※AtCoderテストケースより [入力例] 2 3 1 1 2 [出力例] 2 [入力例] 3 3 2 0 1 2 3 0 1 3 [出力例] 2 [入力例] 7 87 47 83 83 33 76 95 32 114 38 7 46 90 118 116 14 1 55 29 40 76 25 41 115 13 66 79 43 71 67 73 94 43 111 83 57 121 98 97 57 67 91 24 110 47 28 22 64 37 [出力例] 5 [入力例] 10 2 0 1 10 3 1 0 4 6 0 3 5 6 11 1 4 2 7 7 9 5 8 4 2 0 11 2 4 5 8 0 8 3 11 4 11 0 11 8 11 2 10 1 6 10 1 0 3 0 6 10 3 2 8 4 2 10 2 8 9 11 11 4 10 10 7 9 8 8 4 11 0 7 6 5 3 5 5 3 11 11 4 1 11 1 7 9 10 1 3 2 7 6 4 5 0 8 10 11 3 [出力例] 3107 [入力例] 20 261 92 16 184 99 232 142 1 23 173 135 112 45 50 115 171 224 132 109 49 293 108 122 163 124 276 97 200 70 183 301 166 64 65 38 298 182 298 9 53 290 274 207 298 45 227 220 198 132 137 176 144 12 182 112 265 316 133 225 312 114 191 76 164 227 184 254 98 137 114 265 8 177 121 234 4 177 137 21 88 272 331 11 330 288 1 165 274 234 99 137 201 331 105 184 132 301 90 139 103 44 299 33 135 67 142 113 196 226 279 107 144 296 46 181 43 33 51 11 10 214 123 67 65 313 183 266 98 3 203 197 292 262 55 22 323 108 63 330 103 314 295 295 273 172 73 85 320 150 38 20 11 276 301 10 226 125 233 225 116 2 166 10 116 249 258 84 142 191 54 39 327 137 90 27 262 313 39 153 40 7 170 272 72 121 332 105 327 76 61 188 144 208 258 313 154 76 223 123 196 256 263 272 201 13 296 200 171 195 176 48 239 111 225 173 235 268 159 154 201 287 112 10 276 46 316 168 199 220 144 208 290 56 194 53 305 229 192 43 168 159 297 328 51 48 75 292 181 193 33 17 21 19 219 167 160 94 104 46 240 58 318 199 20 178 150 213 97 242 278 187 312 213 41 108 52 41 165 98 292 6 181 148 51 290 9 128 230 12 266 136 225 6 319 26 115 274 256 164 129 309 210 276 294 202 68 37 53 98 184 112 49 20 259 286 105 86 325 134 158 4 321 125 150 197 190 13 286 44 314 33 152 189 201 80 80 222 239 70 155 263 134 327 70 108 161 207 124 225 144 58 70 69 308 104 239 309 232 142 222 212 162 301 261 286 246 163 296 285 9 117 6 9 22 273 235 317 55 326 90 97 264 249 115 309 249 242 7 49 1 254 215 43 145 267 48 18 65 65 168 [出力例] 69041220 [入力例] 23 27 19 16 13 25 25 12 26 26 6 13 13 29 5 7 10 17 11 6 20 8 14 25 24 0 31 5 27 27 21 29 0 7 13 28 6 2 3 23 2 26 21 17 16 29 9 32 15 20 32 22 2 15 23 19 20 18 19 1 9 29 15 3 13 5 32 4 19 31 29 8 12 9 32 25 26 6 31 17 14 10 26 14 11 19 11 29 17 0 7 16 18 23 6 18 30 18 32 16 8 16 15 6 24 18 3 5 1 0 9 29 10 14 9 11 22 23 29 2 28 5 10 1 21 27 20 22 15 21 12 13 15 30 1 13 9 10 22 16 18 19 8 29 20 18 29 1 6 21 22 7 15 13 0 20 26 22 12 32 7 28 6 1 28 7 23 11 24 7 9 4 32 11 21 4 29 8 30 25 16 27 7 17 10 18 5 26 3 21 11 8 6 3 8 3 12 25 19 28 26 20 11 20 5 27 25 4 12 7 18 12 7 3 4 9 0 20 22 7 4 19 27 22 16 22 16 8 19 24 27 26 27 8 6 4 12 12 25 14 12 22 25 18 20 27 15 32 18 8 23 15 17 11 12 22 4 14 24 30 28 5 16 6 9 25 18 4 10 11 29 28 21 17 15 5 9 22 5 15 17 16 23 28 10 5 19 13 31 24 0 28 1 15 24 25 1 2 27 29 9 5 14 20 26 16 14 14 27 30 15 12 14 2 4 14 2 32 14 19 10 4 12 22 11 12 16 19 11 11 19 16 0 2 10 15 24 32 12 25 15 31 10 28 29 19 5 32 6 20 3 9 17 27 20 18 2 30 0 6 10 25 30 14 0 2 2 5 3 28 1 11 26 5 27 32 26 16 16 14 19 29 23 3 24 0 9 3 13 6 29 14 25 17 23 21 21 12 29 23 30 18 5 2 23 12 3 16 17 10 1 26 24 0 20 12 19 26 29 12 26 24 30 15 0 28 13 6 9 4 31 3 32 3 10 3 20 23 32 0 22 26 21 0 30 26 5 27 32 11 29 23 21 24 3 10 17 7 32 9 21 4 4 3 17 17 6 11 17 32 27 8 5 7 17 10 5 12 12 5 24 15 23 2 7 32 32 5 9 14 12 25 22 26 27 31 32 2 10 1 25 17 19 6 21 13 0 13 22 3 13 21 24 25 3 27 3 32 6 28 32 4 10 8 9 15 7 31 17 28 [出力例] 32767609364 ※ 整数 N が, 問題文の制約条件から範囲外であるケース. |