C++の練習を兼ねて, AtCoder Regular Contest 110 の 問題A (Redundant Redundancy) ~ 問題B (Many 110) を解いてみた.
■感想.
1. 問題B は, 条件が絞り込めなかったので, 解説を参照して, 実装したところ, ようやくAC版に到達できた.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Regular Contest 110 解説 の 各リンク を ご覧下さい.
■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 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; int main(){ // 1. 入力情報. LL N; scanf("%lld", &N); // 2. 最小公倍数(2 ~ N)を計算. LL ans = 1, cur = 1; while(++cur <= N){ ans /= gcd(ans, cur); ans *= cur; } // 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 33 34 |
[入力例] 3 [出力例] 7 ※AtCoderのテストケースより [入力例] 10 [出力例] 39916801 ※AtCoderのテストケースより ※ 但し, 上記のプログラムでは, 以下の内容が出力される. 2521 [入力例] 15 [出力例] 360361 [入力例] 25 [出力例] 26771144401 [入力例] 30 [出力例] 2329089562801 |
■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 |
// 解き直し. // https://atcoder.jp/contests/arc110/editorial/383 // 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. 入力情報. int N; char c[202020]; scanf("%d %s", &N, c); string T(c); // 2. 解説通り // 2-1. 文字列 T が, "1" の 場合. if(T == "1") puts("20000000000"); // 2-2. 文字列 T が, "11" の 場合. if(T == "11") puts("10000000000"); // 2-3. 文字列 T が, "1", "11" の 場合は, 終了.(※testcase_2.txt のWA回避のため) if(T == "1" || T == "11") return 0; // 3. それ以外. // 3-1. 文字列 T が 文字列 S に, 含まれるか 確認. string t = ""; rep(i, 202020 / 3) t += "110"; // 3-2. 文字列 S が, mod 3 で 周期的なので, 3通り確認. bool ok = false; if(T == t.substr(0, N) || T == t.substr(1, N) || T == t.substr(2, N)) ok = true; // 3-3. 文字列 T に含まれる '0' の 個数. LL ans = 0, K = 0; rep(i, N) if(T[i] == '0') K++; // 3-4. 文字列 T が 含まれる個数を計算. if(ok) ans = 1e10 - K + (T.back() == '0'); // 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 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
[入力例] 4 1011 [出力例] 9999999999 ※AtCoderのテストケースより [入力例] 22 1011011011011011011011 [出力例] 9999999993 ※AtCoderのテストケースより [入力例] 1 1 [出力例] 20000000000 [入力例] 2 11 [出力例] 10000000000 [入力例] 2 00 [出力例] 0 [入力例] 7 1101101 [出力例] 9999999998 [入力例] 7 1011011 [出力例] 9999999998 [入力例] 10 1101101101 [出力例] 9999999997 [入力例] 200 11011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011 [出力例] 9999999934 |