C++の練習を兼ねて, AtCoder Beginner Contest 198 の 問題C (Compass Walking) ～ 問題D (Send More Money) を解いてみた.
■感想.
1. 問題C, Dは, 解答方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 問題D の 覆面算をプログラムで, 計算できてしまうことが, 個人的には, 面白い問題に感じた.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Beginner Contest 198 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題C／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 |
// 解き直し. // https://atcoder.jp/contests/abc198/editorial/1043 // 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--) int main(){ // 1. 入力情報. LL R, X, Y; scanf("%lld %lld %lld", &R, &X, &Y); // 2. 必要な歩数の最小値を計算. LL X2Y2 = X * X + Y * Y; LL ans = (LL)(sqrt(X2Y2) / R); if(ans * ans * R * R != X2Y2){ if(X2Y2 <= 4 * R * R) ans = 2; else ans++; } // 3. 出力. 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 |
[入力例] 5 15 0 [出力例] 3 ※AtCoderテストケースより [入力例] 5 11 0 [出力例] 3 ※AtCoderテストケースより [入力例] 3 4 4 [出力例] 2 ※AtCoderテストケースより [入力例] 26 1176 490 [出力例] 49 [入力例] 3939 87912 15129 [出力例] 23 |
■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 |
// 解き直し. // https://atcoder.jp/contests/abc198/editorial/1050 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using vi = vector<int>; 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 all(x) x.begin(), x.end() int a[26]; int main(){ // 1. 入力情報. char c1[22], c2[22], c3[22]; scanf("%s %s %s", c1, c2, c3); string S1(c1), S2(c2), S3(c3); // 2. 文字の種類数を数える. set<char> st; rep(i, S1.size()) st.insert(S1[i]); rep(i, S2.size()) st.insert(S2[i]); rep(i, S3.size()) st.insert(S3[i]); // 3. 11種類以上ある場合. int n = st.size(); if(n > 10){ puts("UNSOLVABLE"); return 0; } // 4. アルファベットの出現順に採番. int idx = -1; for(auto &p : st) a[p - 'a'] = ++idx; // 5. 全探索. LL N1 = 0, N2 = 0, N3 = 0; vi z(10); iota(all(z), 0); bool ok = false; do{ // 初期化. N1 = N2 = N3 = 0; // 先頭文字がゼロか否か. int z1 = z[a[S1[0] - 'a']]; int z2 = z[a[S2[0] - 'a']]; int z3 = z[a[S3[0] - 'a']]; // 先頭文字がゼロの場合. if(z1 == 0 || z2 == 0 || z3 == 0) continue; // 覆面算の検算. rep(i, S1.size()) N1 = 10 * N1 + z[a[S1[i] - 'a']]; rep(i, S2.size()) N2 = 10 * N2 + z[a[S2[i] - 'a']]; rep(i, S3.size()) N3 = 10 * N3 + z[a[S3[i] - 'a']]; if(N1 + N2 == N3){ ok = true; break; } }while(next_permutation(all(z))); // 6. 出力. if(ok) printf("%lld\n%lld\n%lld\n", N1, N2, N3); else puts("UNSOLVABLE"); 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 69 70 |
[入力例] a b c [出力例] 1 2 3 ※AtCoderテストケースより [入力例] x x y [出力例] 1 1 2 ※AtCoderテストケースより [入力例] p q p [出力例] UNSOLVABLE ※AtCoderテストケースより [入力例] abcd efgh ijkl [出力例] UNSOLVABLE ※AtCoderテストケースより [入力例] send more money [出力例] 9567 1085 10652 ※AtCoderテストケースより [入力例] abcdbde faaccde fdagheda [出力例] 8950904 1885504 10836408 [入力例] cgjibicjjh hebdidbdaf babbcabedac [出力例] 2698182997 7413831305 10112014302 |
■参照サイト
AtCoder Beginner Contest 198