C++の練習を兼ねて, AtCoder Regular Contest 163 の 問題A (Divide String) ～ 問題B (Favorite Game) を解いてみた.
■感想.
1. 問題A, Bは, 方針が見えなかったので, 解説を参考に, AC版に到達できた.
2. 両問とも, 解説のロジックで, 解けることが興味深く思った.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 163 解説 の 各リンク を ご覧下さい.
■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 |
// 解き直し. // https://atcoder.jp/contests/arc163/editorial/6693 // C++20(GCC 12.2) #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 main(){ // 1. 入力情報. int T; scanf("%d", &T); // 2. テストケース. rep(i, T){ // 2-1. 各テストケース. int N; char c[2020]; scanf("%d %s", &N, c); string s(c); // 2-2. 長さ 2 の分割方法が存在するか？ bool ok = false; rep(i, N - 1){ string l = s.substr(0, i + 1); string r = s.substr(i + 1, N - i - 1); // printf("l=%s r=%s\n", l.c_str(), r.c_str()); // 狭義単調増加に注意(等号は含めない). if(l < r){ ok = true; break; } } // 2-3. 出力. printf("%s\n", ok ? "Yes" : "No"); } 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 |
[入力例] 5 4 abac 3 cac 2 ab 12 abababababab 5 edcba [出力例] Yes No Yes Yes No ※AtCoderのテストケースより [入力例] 9 2 aa 3 aba 4 zyyx 5 qqqqp 6 zyxwvx 7 pqrsqrp 8 zyxzxyzy 9 pqrpqrpqr 10 srqposrqpo [出力例] No Yes No Yes No Yes No Yes No |
■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 |
// 解き直し. // https://atcoder.jp/contests/arc163/editorial/6699 // C++20(GCC 12.2) #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--) LL a[202020]; int main(){ // 1. 入力情報. int N, M; scanf("%d %d", &N, &M); rep(i, N) scanf("%lld", &a[i]); // 2. 数列 B. sort(a + 2, a + N); // 3. 全探索. LL ans = 202020202020202020; repx(i, 2, N - M + 1){ // 左端, 右端. LL l = a[i]; LL r = a[i + M - 1]; // 操作回数. LL op = 0; op += max(0LL, a[0] - l); op += max(0LL, r - a[1]); // 最小値更新. ans = min(ans, op); } // 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 |
[入力例] 3 1 2 3 5 [出力例] 2 ※AtCoderのテストケースより [入力例] 5 2 1 4 2 3 5 [出力例] 0 ※AtCoderのテストケースより [入力例] 8 5 15 59 64 96 31 17 88 9 [出力例] 35 ※AtCoderのテストケースより [入力例] 7 5 31 14 91 40 16 56 99 [出力例] 100 [入力例] 20 12 81 43 53 37 98 14 38 92 84 31 8 17 77 72 123 83 6 57 117 51 [出力例] 105 [入力例] 30 15 830 698 320 654 1055 357 16 713 244 523 463 1020 912 514 298 528 549 801 424 490 323 246 1163 301 392 290 645 458 1099 776 [出力例] 525 |
■参照サイト
AtCoder Regular Contest 163