C++の練習を兼ねて, AtCoder Beginner Contest 280 の 問題C (Extra Character), 問題E (Critical Hit) を解いてみた.
■感想.
1. 問題C, E は, 方針を絞り込めたので, AC版に到達できたと思う.
2. 問題D は, 初見で提出したもの, 解説確認後にしたものが, いずれも, AC版とならなかったため, 割愛した(理解不足と見做して, 解答不能のステータスとした).
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 280 解説 の 各リンク を ご覧下さい.
■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 |
// 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 main(){ // 1. 入力情報. char s[505050], t[505050]; scanf("%s %s", s, t); string S(s), T(t); // 2. 対象の英文字は？ int ans = T.size(); rep(i, S.size()){ if(S[i] != T[i]){ ans = i + 1; break; } } // 3. 出力. printf("%d\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 |
[入力例] atcoder atcorder [出力例] 5 ※AtCoderテストケースより [入力例] million milllion [出力例] 5 ※AtCoderテストケースより [入力例] vvwvw vvvwvw [出力例] 3 ※AtCoderテストケースより [入力例] pppqqr pppqqrs [出力例] 7 [入力例] aaaaaaaaaa aaaaaaaaaaa [出力例] 11 [入力例] abracadabra aabracadabra [出力例] 2 |
■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 |
// 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; const LL I100 = 828542813; LL e[202020]; int main(){ // 1. 入力情報. int N, P; scanf("%d %d", &N, &P); // 2. 漸化式. // E[n] = (1 - P / 100) * (E[n - 1] + 1) + (P / 100) * (E[n - 2] + 1) で 計算. e[1] = 1; e[2] = (2 + MOD - (P * I100 % MOD)) % MOD; repx(i, 3, N + 1){ e[i] += (1 + MOD - (P * I100 % MOD)) % MOD * (e[i - 1] + 1) % MOD; e[i] %= MOD; e[i] += (P * I100 % MOD) * (e[i - 2] + 1) % MOD; e[i] %= MOD; } // 3. 出力. printf("%lld\n", e[N]); 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 |
[入力例] 3 10 [出力例] 229596204 ※AtCoderテストケースより [入力例] 5 100 [出力例] 3 ※AtCoderテストケースより [入力例] 280 59 [出力例] 567484387 ※AtCoderテストケースより [入力例] 1 50 [出力例] 1 [入力例] 2 50 [出力例] 499122178 [入力例] 3 20 [出力例] 119789325 [入力例] 5 15 [出力例] 520228810 [入力例] 20 22 [出力例] 89557086 [入力例] 2022 12 [出力例] 23091804 |
■参照サイト
デンソークリエイトプログラミングコンテスト2022 Winter(AtCoder Beginner Contest 280)