【AtCoder】ABC401をPythonで解く
1. はじめに
目的
ABCを解くことにより、とにかくRatingを上げていく。
フィードバックして欲しい点
私は競技プログラミング初心者のため、いただいたアドバイスをすぐに理解できず、何度も質問してしまうかもしれません。それでも構わないという心優しい方がいらっしゃれば、ぜひアドバイスをいただけると嬉しいです。丁寧に教えていただけると、とても助かります！
- アルゴリズムの選択と最適化
- 今の実装よりも効率的なアルゴリズムがあるか？
- 計算量を減らせる部分や、ボトルネックになっている処理はないか？
- コードの可読性と整理
- もっとシンプルに書ける部分はないか？
- 変数名や関数名が分かりやすいか？
- エッジケース・例外処理の検討
- 想定外の入力でバグが発生する可能性がないか？
- 競プロのジャッジでWAになりそうなケースがあるか？
注意点
- 言語はPython(PyPy 3.10-v7.3.12) を使用しています。
2. コンテスト情報
コンテスト名
AtCoder Beginner Contest 401
コンテストURL
開催日
2025-04-12(土) 21:00 ~ 2025-04-12(土) 22:40 (100分)
配点
| 問題 | 点数 |
|---|---|
| A | 100 |
| B | 200 |
| C | 300 |
| D | 400 |
| E | 450 |
| F | 500 |
| G | 575 |
結果
順位：7237/11162
| 総合 | A | B | C | D | E | F | G | |
|---|---|---|---|---|---|---|---|---|
| 得点 | 600(4) | 100(1) | 200(3) | 300 | ||||
| 時間 | 95:59 | 4:57 | 28:47 | 75:59 |
3. 解いた問題と解法
A: Status Code
コード
s = int(input())
if 200 <= s <= 299:
print("Success")
else:
print("Failure")
解法
改善点
文字列に"ダブルクォーテーション"をつけ忘れてエラーを起こしてしまった。
B: Unauthorized
コード
n = int(input())
s = [input() for _ in range(n)]
logged_in = False
count = 0
for command in s:
if command == "login":
logged_in = True
elif command == "logout":
logged_in = False
elif command == "private":
if not logged_in:
count += 1
print(count)
解法
現時点でログインしているのかどうかを表す
また、
そして、
改善点
n = int(input())
s = [str(input()) for _ in range(n)]
count = 0
s_pre = "logout"
for i in s:
if s_pre == "logout" and i == "private":
count += 1
else:
s_pre = i
else:
print(count)
最初に書いたコードでは、
しかし、これでは
よって、このコードではエラーが出てしまった。
C: K-bonacci
コード
N, K = map(int, input().split())
A = [0] * (N + 1)
S = [0] * (N + 2)
for i in range(N + 1):
if i < K:
A[i] = 1
else:
A[i] = (S[i] - S[i - K]) % 10**9
S[i + 1] = (S[i] + A[i]) % 10**9
print(A[N])
解法
毎回
そのため、以下のように定義される和の
この
よって、
そして、合同式の性質より、法を
改善点
n, k = map(int, input().split())
s = k
a = [1 for i in range(n + 1)]
for i in range(k, n + 1):
a[i] = s
s -= a[i-k]
s += a[i]
s %= 1000000000
print(a[n])
まず初めに、
そして、
また、
-
A_i=S -
S A_(i-K) -
S A_i -
S 10^9
これで計算量を大幅に減らすことができる。
D: Logical Filling
模範解答コード
研究中
解法
E~Gは研究中
現在の私には解くことができません。
4. まとめ
今回は初めてC問題まで解くことができた。そこまで難しいアルゴリズムもなく、大学数学程度の知識で十分だった。しかし、A問題などの簡単な問題でエラーを多発してしまったため、
Discussion