C++の練習を兼ねて, AtCoder Regular Contest 124 の 問題A (LR Constraints) ～ 問題B (XOR Matching 2) を解いてみた.
■感想.
1. 問題B は, 方針が見えなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. 個人的には, 非常に面白い問題に感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 124 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題A／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 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using vi = vector<int>; using vvi = vector<vi>; #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 const LL MOD = 998244353; int l[1010], r[1010], memo[1010]; int main(){ // 1. 入力情報. int N, K; scanf("%d %d", &N, &K); vvi v(N); rep(i, K){ char c[11]; int k, n = i + 1; scanf("%s %d", c, &k); k--; // 最も左にあるカードが指定された場合. if(c[0] == 'L'){ l[n] = k; r[n] = N - 1; } // 最も右にあるカードが指定された場合. if(c[0] == 'R'){ l[n] = 0; r[n] = k; } // 使用済み. v[k].pb(n); memo[k]++; } // 2. 数字を, 新たに保存. rep(i, K){ int n = i + 1; repx(j, l[n], r[n] + 1) if(!memo[j]) v[j].pb(n); } // 3. 集計. LL ans = 1; rep(i, N) ans = ans * (LL)v[i].size() % MOD; // 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 |
[入力例] 3 2 L 1 R 2 [出力例] 1 ※AtCoderのテストケースより [入力例] 30 10 R 6 R 8 R 7 R 25 L 26 L 13 R 14 L 11 L 23 R 30 [出力例] 343921442 ※AtCoderのテストケースより [入力例] 5 3 L 2 R 3 L 4 [出力例] 2 [入力例] 7 5 L 5 R 2 L 3 R 4 L 1 [出力例] 9 [入力例] 50 17 R 29 R 45 R 33 L 36 L 35 R 5 L 6 L 43 L 48 R 7 L 32 R 17 L 41 R 2 R 50 R 28 L 11 [出力例] 733873656 |
■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 |
// 解き直し. // https://atcoder.jp/contests/arc124/editorial/2329 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using vi = vector<int>; #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() int main(){ // 1. 入力情報. int N; scanf("%d", &N); vi a(N), b(N); rep(i, N) scanf("%d", &a[i]); rep(i, N) scanf("%d", &b[i]); // 2. sort. sort(all(b)); // 3. N 通り試す. set<int> ans; rep(i, N){ // 3-1. x を 取得. int x = a[0] ^ b[i]; // 3-2. すでに確認済みか？ if(ans.count(x)) continue; // 3-3. 数列 c を 作成. vi c; rep(j, N) c.pb(a[j] ^ x); // 3-4. sort. sort(all(c)); // 3-5. 良い数を保存. if(b == c) ans.insert(x); } // 4. 出力. printf("%d\n", ans.size()); for(auto &p : ans) printf("%d\n", p); 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 |
[入力例] 3 1 2 3 6 4 7 [出力例] 1 5 ※AtCoderのテストケースより [入力例] 2 0 1 0 2 [出力例] 0 ※AtCoderのテストケースより [入力例] 24 14911005 70152939 282809711 965900047 168465665 337027481 520073861 20800623 934711525 944543101 522277111 580736275 468493313 912814743 99651737 439502451 365446123 198473587 285587229 253330309 591640417 761745547 247947767 750367481 805343020 412569406 424258892 329301584 123050452 1042573510 1073384116 495212986 158432830 145726540 623594202 836660574 380872916 722447664 230460104 718360386 620079272 109804454 60321058 38178640 475708360 207775930 393038502 310271010 [出力例] 8 107543995 129376201 139205201 160626723 312334911 323172429 481902037 493346727 ※AtCoderのテストケースより [入力例] 5 9323 23050 4277 6413 18289 23409 11325 16692 6379 17676 [出力例] 0 [入力例] 8 0 1 2 3 4 5 6 7 7 6 5 4 3 2 1 0 [出力例] 8 0 1 2 3 4 5 6 7 |
■参照サイト
AtCoder Regular Contest 124