C++の練習を兼ねて, AtCoder Regular Contest 154 の 問題A (Swap Digit) ~ 問題B (New Place) を解いてみた.
■感想.
1. 問題B は, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 問題B で, 二分探索の 復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 154 解説 の 各リンク を ご覧下さい.
■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 70 71 72 73 |
// 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--) const LL MOD = 998244353; int main(){ // 1. 入力情報. int N; char a[202020], b[202020]; scanf("%d %s %s", &N, a, b); // 2. 操作. LL A = 0, B = 0; int s = -1; bool f = true; rep(i, N){ // A, B が 等しい間. if(s == -1){ A = A * 10 + a[i] - '0'; A %= MOD; B = B * 10 + b[i] - '0'; B %= MOD; // A, B が, 最初に異なる場所. if(a[i] != b[i]){ s = i; continue; } } // それ以外. if(s != -1){ if(a[i] <= b[i]){ if(a[s] < b[s]){ A = A * 10 + a[i] - '0'; A %= MOD; B = B * 10 + b[i] - '0'; B %= MOD; } if(a[s] > b[s]){ A = A * 10 + b[i] - '0'; A %= MOD; B = B * 10 + a[i] - '0'; B %= MOD; } }else{ if(a[s] < b[s]){ A = A * 10 + b[i] - '0'; A %= MOD; B = B * 10 + a[i] - '0'; B %= MOD; } if(a[s] > b[s]){ A = A * 10 + a[i] - '0'; A %= MOD; B = B * 10 + b[i] - '0'; B %= MOD; } } } } // 3. 出力. printf("%lld\n", A * B % MOD); 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 |
[入力例] 2 13 22 [出力例] 276 ※AtCoderのテストケースより [入力例] 8 20220122 21002300 [出力例] 54558365 ※AtCoderのテストケースより [入力例] 5 13385 22576 [出力例] 291876750 [入力例] 20 55570287117956982219 55570312438184304678 [出力例] 414030506 [入力例] 50 73520943047002292615274910544319198112428012369710 71344425330648685657673067567450658751475913225975 [出力例] 319328486 |
■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 |
// 解き直し. // https://atcoder.jp/contests/arc154/editorial/5533 // 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--) #define all(x) x.begin(), x.end() int main(){ // 1. 入力情報. int N; char a[202020], b[202020]; scanf("%d %s %s", &N, a, b); string A(a), B(b), S(a), T(b); // 2. sort. sort(all(A)); sort(all(B)); // 3. 例外. if(A != B){ puts("-1"); return 0; } // 4. 評価関数. auto f = [&](int m) -> bool { // 4-1. 文字列 X. string X = S.substr(m, N - m); // 4-2. 文字列 T の 部分列か? int idx = 0; rep(i, N){ // 比較. if(X[idx] == T[i]) ++idx; // 部分列である. if(idx == X.size()) return true; } // 4-3. 部分列でない. return false; }; // 5. 二分探索で確認してみる. int l = -1, h = 2 * N; while(l + 1 < h){ int m = (h + l) >> 1; if(f(m)) h = m; else l = m; // printf("h=%d l=%d m=%d\n", h, l, m); } // 6. 出力. printf("%d\n", h); 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 |
[入力例] 4 abab abba [出力例] 2 ※AtCoderのテストケースより [入力例] 3 arc cra [出力例] 2 ※AtCoderのテストケースより [入力例] 5 pqrst opqrs [出力例] -1 [入力例] 10 pqrpqrpqrp pqrpqrpqrp [出力例] 0 [入力例] 50 mpgiytiagtmzuinudtjjawhbpibnfwaordasntnudtjjawhbpi mpgiytiagtsntnudtjjawhbpimzuinudtjjawhbpibnfwaorda [出力例] 34 [入力例] 100 pibnfwaordawwagcokbzekatmpgiytiagtsntnudtjjawhbpimzuinudtjjawhbyghmqyntdjphtlckueltiznnvnoeufuksahef atyghmqyntdjphtlckueltiznnvnoeufuksahempgiytiagtsntnudtjjawhbpimzuinudtjjawhbpibnfwaordawwagcokbzekf [出力例] 63 [入力例] 500 fsksicxhybwcetiaqgtmjlympuampnwxtgmhavxnsdpegtfwetkeyhufkcemxrfgelvdvrafixfhhanojvuthmsvxkyfrbfkfpxeofwmzcovmodktmumvjtwlgrtmxdgyqlzlgxjynfiflquoyhyqzlzepeiwgqjoixswqiagalfonvwedflwtldcdkgpzmravwrmyihsshtruvhmupxubtkddaexfiducbxixvkeushrsipxaktkcbftixyckzopppuljredlrgktntxjgaxrebrigybovwttuiatfwcpyoqrmiscvwwoqcibzcnddyxhmignqcxjlibcqqnvwkpovqafmyfbrldesgesbhxsnmbvpwfvzzzohtdsmjnznvftqbigsyclqoqxjuudyeqlsrsbzjbxtflvqbyheqlqlrlugaqfbdjfjwzeoltnfaioyygbljwdajhfmwaejirzytuotibelypoqvtxjdhzjnvarbtzim fgelvdvrafixfhhanojvuthmsvrmyihsshtruvhmupxubtkddaexfiducbxixvkeushrsipxaktkcbftixyckzopppuljrexkyfrbfkfpxeofwmzcovmodktmumvjtwldlrgktntxjgaxrebrivwwoqcibzcnddyxhmignqcxjlibcqqnvwkpovqafmyfbrlderbtzimgrtmxdgyqlzlgxjynfieiwgqjoixswqiagalsgesbhxsnmbvpwfvohtdsmjnznvftqbigsyclqoqxjuudyeqlsrsbzjbxttibelypoqvtxjdhzjnvafonvwgpzmravpuampnwxtgmhavxnsdpegtfwetkeyhufkcemxrffskzzzsicxhybwcetiaqgtmjlymwedflwtldcdklquoflvqbyheqlqlrlugaqfbdjfjwzeoltnfaioyygbljwdajhfmwaejirzytuoyhyqzlzepgybovwttuiatfwcpyoqrmisc [出力例] 465 |
■参照サイト
AtCoder Regular Contest 154