【AtCoder】Daily Training 2025/03/25
1. はじめに
目的
Daily Trainingを解くことにより、競技プログラミングに慣れることを目的としています。
フィードバックして欲しい点
私は競技プログラミング初心者のため、いただいたアドバイスをすぐに理解できず、何度も質問してしまうかもしれません。それでも構わないという心優しい方がいらっしゃれば、ぜひアドバイスをいただけると嬉しいです。丁寧に教えていただけると、とても助かります！
- アルゴリズムの選択と最適化
- 今の実装よりも効率的なアルゴリズムがあるか？
- 計算量を減らせる部分や、ボトルネックになっている処理はないか？
- コードの可読性と整理
- もっとシンプルに書ける部分はないか？
- 変数名や関数名が分かりやすいか？
- エッジケース・例外処理の検討
- 想定外の入力でバグが発生する可能性がないか？
- 競プロのジャッジでWAになりそうなケースがあるか？
注意点
- 言語はPython(PyPy 3.10-v7.3.12) を使用しています。
- 今回はバーチャル参加ではありません。
2. コンテスト情報
コンテスト名
AtCoder Daily Training EASY 2025/03/25 15:30start
コンテストURL
開催日
2025-03-25(火) 15:30 ~ 2025-03-25(火) 16:30 (60分)
配点
| 問題 | 点数 |
|---|---|
| A (過去のABCのA問題から出題) | 100 |
| B (過去のABCのA問題から出題) | 100 |
| C (過去のABCのA問題から出題) | 200 |
| D (過去のABCのA問題から出題) | 200 |
| E (過去のABCのA問題から出題) | 300くらい |
3. 解いた問題と解法
A: Not Too Hard
コード
N, X = map(int, input().split())
S = list(map(int, input().split()))
count = 0
for i, v in enumerate(S):
if v <= X:
count += v
print(count)
解法
enumerate関数を用いることで、イテラブルオブジェクトの要素を取得する。
そして、条件分岐を用いて、
改善点
- for i, v in enumerate(S):
+ for i in S:
インデックスを使用しなかったため、リストの要素取得で十分である。
B: 321-like Checker
コード
N = str(input())
if len(N) == 1:
print("Yes")
else:
for i in range(len(N)-1):
if int(N[i]) <= int(N[i+1]):
print("No")
break
else:
print("Yes")
解法
また、常に
そして、for文が最後まで実行される、すなわち単調減少となれば
改善点
数値のまま受け取り、
- if len(N) == 1:
- print("Yes")
-
- else:
C: Strawberries
コード
N, K = map(int, input().split())
S = input()
print(S.count("O"*K))
解法
countメソッドを使うことで、
また、
改善点
+ if i[i:i+k] == list("0"*K):
+ ans += 1
+ for j in range(i, i+k):
+. N[j] = "X"
全ての歯について
D: Modulo Number
コード
N = int(input())
for i in range(998244353):
if (N-i) % 998244353 == 0:
print(i)
解法
改善点
N = int(input())
print(N % 998244353)
E: Submask
コード
N = int(input())
bit = []
for i in range(len(format(N, "b"))):
if N & (1<<i):
bit.append(i)
for i in range(1<<len(bit)):
x = 0
for j in range(len(bit)):
if i & (1<<j):
x |= (1<<bit[j])
print(x)
解法
そのため、リストbitに
そして、
| 変換前 | 変換後 |
|---|---|
| 0000 | 000 |
| 0001 | 001 |
| 0010 | 010 |
| 0011 | 011 |
| 1000 | 100 |
| 1001 | 101 |
| 1010 | 110 |
| 1011 | 111 |
上記の表のように、この
よって、変数
改善点
def generate_submasks(N):
submasks = [0]
for i in range(60):
if N & (1<<i):
submasks += [x|(1<<i) for x in submasks]
return submasks
N = int(input())
results = generate_submasks(N)
# results.sort()
for result in results:
print(result)
上記のコードのように、集合を徐々に大きくして構成する方法もある。
まずは、
そして、
4. 他の解法・考察
別のアプローチの可能性
- 問題Eでは集合を拡張するアプローチが新鮮だった。
計算量や工夫点
- int型とstr型をうまく使い分けられた点は非常に良かった。
- 計算量を意識して、冗長なループを避けた。
5. まとめ
今回の気づき
- ビット操作を活用した解法の理解が進んだ。
- 異なるアプローチの比較が重要
改善したい点
- 時間制限内に解くスキルを向上させる。
- C++の解法を研究し、Pythonでの最適な書き方を模索する。
Discussion