C++の練習を兼ねて, AtCoder Beginner Contest 141 の 問題F (Xor Sum 3) を解いてみた.
■感想.
1. 問題Fは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 実装に苦労したものの, 行列の掃き出し法について復習出来たので, 非常に良かったと思う.
※ 過去問 AtCoder Regular Contest 054 C – 鯛焼き を 参考にして, 掃き出し法の実装を進めてみたものの, 文字列ベースだと, TLE版になるため, 整数ベースで実装し直した版で, 提出している.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 141 解説 の 各リンク を ご覧下さい.
■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 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 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 |
// 解き直し. // https://img.atcoder.jp/abc141/editorial.pdf // 過去問参照(AtCoder Regular Contest 054 C - 鯛焼き) // https://atcoder.jp/contests/arc054/tasks/arc054_c // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using vs = vector<string>; using vl = vector<LL>; #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 all(x) x.begin(), x.end() LL a[101010]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); LL nXor = 0; // 興味深くないbitを全て立てた整数. rep(i, N){ scanf("%lld", &a[i]); nXor ^= a[i]; } /* // 2. 行列(文字列版). vs matrix; rep(i, N){ string s; repr(j, 59, 0){ if(nXor & (1LL << j)) s.pb('0'); else s.pb(((a[i] >> j) & 1) + '0'); } matrix.pb(s); } // puts("--- Matrix before update ---"); // rep(i, N) printf("%s\n", matrix[i].c_str()); */ /* // TLE版となるので, コメントアウト. // 3. 掃き出し法(mod2版). // https://ja.wikipedia.org/wiki/ガウスの消去法 // // ex. // [変更前行列] // 011001 // 001001 // 101011 // 010110 // 001100 // // [変更後行列] // 100001 // 010000 // 001001 // 000101 // 000011 // auto gauss = [&](vs &m, int N, int M) -> vs { // 3-1. 戻り値設定. vs ret = m; // 3-2. 各行を順次確認. rep(i, N){ // 降順sort. sort(all(ret)); reverse(all(ret)); // 最初に, '1' となる位置. int at = M; rep(j, M){ if(ret[i][j] == '1'){ at = j; break; } } // 見つからなった場合. if(at == M) continue; // i行目以外(j行目)と比較して, 前項で求めた位置(列)に, '1' が 有れば, 掃き出す. rep(j, N){ if(i != j && ret[j][at] == '1'){ // 操作対象を設定. string o = ret[i]; // i行目. string n = ret[j]; // j行目. // j行目の掃き出し. rep(k, M) n[k] = '0' + ((n[k] - '0') ^ (o[k] - '0')); // j行目更新. ret[j] = n; } } } // 3-3. 返却. return ret; }; vs gMatrix = gauss(matrix, N, 60); // puts("--- Matrix after update ---"); // rep(i, N) printf("%s\n", gMatrix[i].c_str()); */ /* // 4. 掃き出し法(mod2版, 計算量削減版). // -> TLE版(sub1_27.txt で, 2153[ms])となるので, コメントアウト. // https://ja.wikipedia.org/wiki/ガウスの消去法 auto gauss = [&](vs &m, int N, int M) -> vs { // 4-1. 戻り値設定. vs ret = m; // 4-2. 60桁目 → 1桁目 で, 行標準形 を 目指す. repr(i, M - 1, 0){ // 基準行. string bRow; string base(60, '0'); base[M - 1 - i] = '1'; string upper(60, '0'); repx(j, M - 1 - i, M) upper[j] = '1'; // sort. sort(all(ret)); // 操作. rep(j, N){ // Skip. if(ret[j] < base) continue; // 基準行設定. if(!bRow.size()){ if(ret[j] <= upper) bRow = ret[j]; continue; } // Skip. if(ret[j] > upper && ret[j][M - 1 - i] == '0') continue; // 基準行反映. rep(k, M) ret[j][k] = '0' + ((ret[j][k] - '0') ^ (bRow[k] - '0')); } } // 4-3. 返却. return ret; }; vs gMatrix = gauss(matrix, N, 60); // puts("--- Matrix after update ---"); // rep(i, N) printf("%s\n", gMatrix[i].c_str()); */ /* // 5. X'あおい の 最大値は? LL bXor = 0; rep(i, N){ LL cur = 0; repr(j, 59, 0) cur += (1LL << j) * (gMatrix[i][59 - j] - '0'); bXor ^= cur; } */ // 6. 行列(整数版). vl matrix; rep(i, N){ LL cur = a[i]; repr(j, 59, 0){ LL bit = 1LL << j; if((nXor & bit) && (a[i] & bit)) cur -= bit; } matrix.pb(cur); } // puts("--- Matrix before update ---"); // rep(i, N) printf("%lld\n", matrix[i]); // 7. 掃き出し法(mod2版, 文字列廃止, 計算量削減版). // https://ja.wikipedia.org/wiki/ガウスの消去法 auto gauss = [&](vl &m, int N, int M) -> vl { // 7-1. 戻り値設定. vl ret = m; // 7-2. 60桁目 → 1桁目 で, 行標準形 を 目指す. repr(i, M - 1, 0){ // 基準行. LL bRow = 0; LL base = 1LL << i; LL upper = (base << 1) - 1; // sort. sort(all(ret)); // 操作. rep(j, N){ // Skip. if(ret[j] < base) continue; // 基準行設定. if(!bRow){ if(ret[j] <= upper) bRow = ret[j]; continue; } // Skip. if(ret[j] > upper && !(ret[j] & base)) continue; // 基準行反映. ret[j] ^= bRow; } } // 7-3. 返却. return ret; }; vl gMatrix = gauss(matrix, N, 60); // puts("--- Matrix after update ---"); // rep(i, N) printf("%lld\n", gMatrix[i]); // 8. X'あおい の 最大値は? LL bXor = 0; rep(i, N){ LL cur = 0; repr(j, 59, 0) cur += (1LL << j) & gMatrix[i]; bXor ^= cur; } // 9. 出力. printf("%lld\n", bXor + bXor + nXor); 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 |
[入力例] 3 3 6 5 [出力例] 12 ※AtCoderのテストケースより [入力例] 4 23 36 66 65 [出力例] 188 ※AtCoderのテストケースより [入力例] 20 1008288677408720767 539403903321871999 1044301017184589821 215886900497862655 504277496111605629 972104334925272829 792625803473366909 972333547668684797 467386965442856573 755861732751878143 1151846447448561405 467257771752201853 683930041385277311 432010719984459389 319104378117934975 611451291444233983 647509226592964607 251832107792119421 827811265410084479 864032478037725181 [出力例] 2012721721873704572 ※AtCoderのテストケースより [入力例] 10 27 22 11 12 7 5 4 3 2 1 [出力例] 50 [入力例] 18 314 159 265 358 979 323 846 264 338 327 950 288 419 716 939 937 510 582 [出力例] 1204 [入力例] 50 34605 73340 57646 1818 49584 118833 110169 73623 90519 34931 51339 78836 54020 110920 12428 102502 86264 101668 123187 54134 40830 20657 30747 64207 33537 90037 68502 27555 119034 104789 47549 21622 33656 78834 104976 34375 78348 110133 39783 75735 23418 21824 77753 96235 22827 29758 35425 36413 25474 21908 [出力例] 233451 [入力例] 500 172 106 502 212 158 420 214 222 165 62 304 503 478 240 315 363 63 131 107 215 340 160 19 283 85 408 277 484 149 44 335 158 318 191 111 260 92 264 88 136 311 457 354 260 112 205 535 139 337 497 139 362 8 443 357 208 372 104 372 305 536 172 254 469 499 444 450 337 23 299 428 273 488 21 315 514 178 533 260 217 410 172 525 396 481 181 137 97 500 10 181 538 53 0 135 465 50 491 250 157 342 548 141 450 353 112 272 548 174 66 136 549 4 55 209 335 464 105 9 423 363 185 52 20 418 208 456 309 493 285 416 64 313 183 345 215 87 142 167 424 323 222 163 43 88 479 102 36 332 96 313 219 549 53 317 499 496 74 184 393 230 328 334 510 115 433 130 193 285 259 532 306 458 541 25 157 403 214 3 443 464 461 4 315 505 196 302 248 34 140 448 15 550 293 310 542 191 416 212 83 432 185 239 68 241 276 528 15 108 476 25 272 25 358 76 27 305 464 306 550 312 500 70 439 2 312 113 371 74 506 284 6 206 136 419 218 327 303 341 238 493 208 493 257 524 264 174 512 267 101 483 32 66 46 197 453 385 310 16 505 355 190 308 177 490 168 177 26 539 50 232 326 413 193 448 378 479 265 176 476 405 240 154 317 541 13 12 417 29 296 493 109 463 307 428 96 398 480 452 295 156 175 300 51 84 274 123 248 247 67 386 58 325 531 92 252 121 516 63 62 156 366 320 248 217 454 58 222 357 125 135 68 370 12 377 215 216 161 24 386 360 3 52 118 18 359 17 246 513 305 39 164 242 272 209 436 502 429 340 332 427 544 232 60 117 407 467 73 226 368 507 240 64 122 18 198 26 335 392 483 11 533 179 489 523 290 145 198 497 75 6 377 487 190 544 414 170 138 182 540 323 332 139 229 378 365 126 381 458 260 390 212 516 171 374 473 332 389 324 224 266 333 394 223 449 285 312 431 267 404 144 93 52 273 474 322 317 422 59 448 184 442 420 32 108 84 494 0 392 518 193 12 113 164 29 335 280 67 372 539 501 498 218 122 147 248 203 218 463 70 163 174 414 88 194 487 334 228 462 545 378 328 313 292 375 126 372 218 472 264 51 334 217 489 299 205 395 182 299 272 [出力例] 2023 |
■参照サイト
AtCoder Beginner Contest 141