C++の練習を兼ねて, AtCoder Beginner Contest 181 の 問題D (Hachi) ～ 問題E (Transformable Teacher) を解いてみた.
■感想.
1. 久しぶりに, 解説見る前に, AC版に到達できたと思う.
2. 個人的には, D問題, E問題ともに, 非常に面白いと感じた.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Beginner Contest 181 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題D／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; #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 cs[10]; // 数字列 S に 含まれる 各文字 の 個数. int main(){ // 1. 入力情報. char c[202020]; scanf("%s", c); string S(c); int l = S.size(); // 2. S が 1桁の場合. if(l == 1){ printf("%s\n", (S[0] == '8') ? "Yes" : "No"); return 0; } // 3. S が 2桁の場合. if(l == 2){ // 2桁 の 数字で, 8 の 倍数となるもの. bool ok = false; repx(i, 10, 100){ string s = to_string(i); if(s[0] != '0' && s[1] != '0' && i % 8 == 0){ if((S[0] == s[0] && S[1] == s[1]) || (S[0] == s[1] && S[1] == s[0])){ ok = true; break; } } } printf("%s\n", ok ? "Yes" : "No"); return 0; } // 4. S が 3桁以上 の 場合. if(l >= 3){ // 4桁以上が, どのような組み合わせであっても, // 3桁部分が, 8 の 倍数ならば, 全体としても 8 の 倍数 に注意. // -> 理由としては, 1000 は, 8 の 倍数であるから. rep(i, l) cs[S[i] - '0']++; // 3桁 の 数字で, 8 の 倍数となるもの. bool ok = false; repx(i, 100, 1000){ string s = to_string(i); if(s[0] != '0' && s[1] != '0' && s[2] != '0' && i % 8 == 0){ ok = true; int cn[10]; memset(cn, 0 ,sizeof(cn)); rep(j, 3) cn[s[j] - '0']++; // 3桁 の 数字 が, 数字列 S の 文字 で 構成可能か？ rep(j, 10){ // 数字列 S の 文字 では, 構成できない場合は, false. if(cn[j] && cn[j] > cs[j]){ ok = false; break; } } } if(ok) break; } 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 |
[入力例] 1234 [出力例] Yes ※AtCoderテストケースより [入力例] 1333 [出力例] No ※AtCoderテストケースより [入力例] 8 [出力例] Yes ※AtCoderテストケースより [入力例] 1233321 [出力例] Yes [入力例] 111111111133333333335555555555 [出力例] No [入力例] 2333333333333333333333333333333555555555555555555555555555555777777777777777777777777777777999999999 [出力例] Yes [入力例] 69999999999777777777755555555553333333333111111111199999999997777777777555555555533333333331111111111999999999977777777775555555555333333333311111111119999999999777777777755555555553333333333111111111199999999997777777777555555555533333333331111111111 [出力例] Yes |
■C++版プログラム(問題E／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 |
// 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--) LL h[202020], w[202020], lCum[101010], rCum[101010]; int main(){ // 1. 入力情報. int N, M; scanf("%d %d", &N, &M); rep(i, N) scanf("%lld", &h[i]); rep(i, M) scanf("%lld", &w[i]); int N2 = N / 2; // 2. sort. sort(h, h + N); // 3. 累積和. rep(i, N2){ // h[1] - h[0], h[3] - h[2], h[5] - h[4], ... を 保存(※ h[N - 1] が 余る). lCum[i + 1] = lCum[i] + abs(h[2 * i + 1] - h[2 * i]); // h[2] - h[1], h[4] - h[3], h[6] - h[5], ... を 保存(※ h[0] が 余る). rCum[i + 1] = rCum[i] + abs(h[2 * i + 2] - h[2 * i + 1]); } // 4. 最小化するには？ LL ans = 202020202020202020; rep(i, M){ // ex. // h[0], h[1], h[2], h[3], h[4] の 場合. // at = 0, 1, ... , 5 の パターンがある. // at = 0 の場合: h[0] - w[i], h[2] - h[1], h[4] - h[3] の 合計 を 評価. // at = 1 の場合: w[i] - h[0], h[2] - h[1], h[4] - h[3] の 合計 を 評価. // at = 2 の場合: h[1] - h[0], h[2] - w[i], h[4] - h[3] の 合計 を 評価. // at = 3 の場合: h[1] - h[0], w[i] - h[2], h[4] - h[3] の 合計 を 評価. // at = 4 の場合: h[1] - h[0], h[3] - h[2], h[4] - w[i] の 合計 を 評価. // at = 5 の場合: h[1] - h[0], h[2] - h[1], w[i] - h[4] の 合計 を 評価. int at = lower_bound(h, h + N, w[i]) - h; int at2 = at / 2; // 左. LL l = lCum[at2]; // 右. LL r = rCum[N2] - rCum[at2]; // 中央. LL m = abs(w[i] - h[at2 * 2]); // 最小値更新. ans = min(ans, l + m + r); } // 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 |
[入力例] 5 3 1 2 3 4 7 1 3 8 [出力例] 3 ※AtCoderテストケースより [入力例] 7 7 31 60 84 23 16 13 32 96 80 73 76 87 57 29 [出力例] 34 ※AtCoderテストケースより [入力例] 15 10 554 525 541 814 661 279 668 360 382 175 833 783 688 793 736 496 732 455 306 189 207 976 73 567 759 [出力例] 239 ※AtCoderテストケースより [入力例] 50 25 6112220 9783018 2479422 2269829 7714144 9539484 6992540 10270860 11097942 8714607 9539098 8475395 9171642 9678191 3494236 4387544 7279578 8352819 4799010 301560 12034975 5647824 5831236 8908282 8301643 7428094 5442233 6313757 3689481 10886952 4957765 7476024 2491214 5604047 11797342 8202939 980344 5711285 4345840 10815056 1638509 7281838 1052127 5696706 11851239 6912861 7386159 578827 4393448 1045889 10894829 11523747 10330013 9016970 1140391 11336743 1169651 2932069 517012 12205331 10771065 3655248 9531446 2609964 2438078 10058915 3136281 4517832 11412406 7395623 10271658 6532730 4207747 8825708 9499227 [出力例] 17375903 |
■参照サイト
AtCoder Beginner Contest 181