C++の練習を兼ねて, AtCoder Regular Contest 151 の 問題A (Equal Hamming Distances) ～ 問題B (A < AP) を解いてみた.
■感想.
1. 問題A, Bは, 方針が見えなかったので, 解説を参考に提出して, ようやく, AC版に到達出来た.
2. 個人的には, 問題B で, 幅優先探索 の 復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 151 解説 の 各リンク を ご覧下さい.
■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 59 60 61 62 63 64 65 66 67 68 69 |
// 解き直し. // https://atcoder.jp/contests/arc151/editorial/5028 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; #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--) int u[202020]; int main(){ // 1. 入力情報. int N; char s[202020], t[202020]; scanf("%d %s %s", &N, s, t); // 2. 事前計算. int d = 0; rep(i, N) if(s[i] != t[i]) ++d; // 3. 例外. if(d & 1){ puts("-1"); return 0; } // 4. U を 構成. d /= 2; int dus = d, dut = d; rep(i, N){ if(s[i] != t[i]){ if(s[i] == '0'){ if(dut){ --dut; continue; } if(dus){ u[i] = 1; --dus; } } if(s[i] == '1'){ if(dus){ --dus; continue; } if(dut){ u[i] = 1; --dut; } } } } // 5. 検証. int e1 = 0, e2 = 0; rep(i, N){ if(s[i] - '0' != u[i]) ++e1; if(t[i] - '0' != u[i]) ++e2; } assert(e1 == e2); // 6. 出力. rep(i, N) printf("%d", u[i]); 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 |
[入力例] 5 00100 10011 [出力例] 00001 ※AtCoderのテストケースより [入力例] 1 0 1 [出力例] -1 ※AtCoderのテストケースより [入力例] 10 0000101101 1011111011 [出力例] 0000010010 [入力例] 20 10100100010000100000 01100011110000011111 [出力例] 00000000000000000111 [入力例] 100 1010110111100111110001110011011100011100011110011110101000001001101110110110111001000011101100101000 0100011101111010110001001111000100101011001000110010011111101111001100111010100100111011110111101011 [出力例] 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001 [入力例] 500 00101101101010110000110011011001101111110111010111011000111011111100110111010101010011011010110000100001101011000001100011111100000111011010100111010111001110010000110100001100110100010010111111111101110000101111001000100101001110110000011110011100000010100111100101111111100011011010001011100101100110111110011110111101010001011000110101010010101101100110010001011110001100101011110010000111101011110100111101000100101000101101100001110110111110001110111100001111000110100101111010000011101101101101 11111000010110001010001110001111111101110000000001000001010010100000110011010010001010010010001110100101110100001110010010100101101001010001011001101000100111000001001100010111010110111100010000100010001101110110111000101110110111110111001001110000011011100110001111101100110001101110111110000110100101100100000100011011100011110101101010011000000110010001101010101011101111111011100000100101001010011111111011101010110011001111101101010010010110100110010010000001101100010101110100111111110101000101 [出力例] 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100001110000010100000001010000000001000101000 |
■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 61 62 63 64 65 66 67 68 69 70 71 |
// 解き直し. // https://atcoder.jp/contests/arc151/editorial/5010 // 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 const LL MOD = 998244353; LL mPowM[202020]; // M の 冪乗(MOD版) int p[202020]; int main(){ // 1. 入力情報. int N, M; scanf("%d %d", &N, &M); vvi G(N); rep(i, N){ scanf("%d", &p[i]); --p[i]; G[i].pb(p[i]); G[p[i]].pb(i); } // 2. M の 冪乗(MOD版) を 保存. mPowM[0] = 1; repx(i, 1, 202020) mPowM[i] = mPowM[i - 1] * M, mPowM[i] %= MOD; // 3. bfs. // https://ja.wikipedia.org/wiki/幅優先探索 auto bfs = [&](vvi &G, int s, int* c, int l){ // 空のキュー. queue<int> q; // 連結成分番号を設定. c[s] = l; // 探索地点 s をキュー q に追加. q.push(s); while(!q.empty()){ // キューから取り出す. int u = q.front(); q.pop(); // 取り出した要素を処理. for(auto &e : G[u]) if(!c[e] && e != s) c[e] = l, q.push(e); } }; int c[N], idx = 0; rep(i, N) c[i] = 0; rep(i, N) if(!c[i]) bfs(G, i, c, ++idx); // 4. 集計. LL ans = mPowM[N]; ans += MOD; ans -= mPowM[idx]; ans %= MOD; ans *= 499122177; ans %= MOD; // 5. 出力. 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 |
[入力例] 4 2 4 1 3 2 [出力例] 6 ※AtCoderのテストケースより [入力例] 1 1 1 [出力例] 0 ※AtCoderのテストケースより [入力例] 20 100000 11 15 3 20 17 6 1 9 5 19 10 16 7 8 12 2 18 14 4 13 [出力例] 55365742 ※AtCoderのテストケースより [入力例] 5 7 5 4 3 2 1 [出力例] 8232 [入力例] 10 3 3 1 2 5 6 4 8 9 10 7 [出力例] 29511 [入力例] 50 20221022 30 8 20 22 28 36 17 24 43 14 15 35 11 5 37 23 50 27 39 25 40 47 32 42 2 4 26 19 16 12 1 44 18 49 34 6 48 45 21 3 29 13 46 10 7 41 33 31 38 9 [出力例] 783859669 |
■参照サイト
AtCoder Regular Contest 151