[ABC428] ABC 428(Atcoder Beginner Contest)のA~C(A,B,C)問題をPythonで解説(復習)
A問題
- 合同（
%）を使って、進んだ距離を計算する。
A.py
"""
<方針>
- 合同（`%`）を使って、進んだ距離を計算する。
"""
# 入力
S, A, B, X = map(int, input().split())
# 割ってみる
di, mo = divmod(X, A+B)
# 走る速さX(繰り返した秒数＋最後に進んだ秒数)
ans = S*(di*A + min(mo, A))
# 出力
print(ans)
B問題
- 辞書（
defaultdict）を用いて、個数を管理する。
B.py
"""
<方針>
- 辞書（`defaultdict`）を用いて、個数を管理する。
"""
# ライブラリ
from collections import defaultdict
# 入力
N, K = map(int, input().split())
S = input()
# 辞書で管理
di = defaultdict(int)
# 辞書に登録
for i in range(N-K+1):
di[S[i:i+K]] += 1
# 個数の小ささで並び替えて、辞書順でも並べる
ls_sorted = sorted([(ke, va) for ke, va in di.items()], key=(lambda x: (-x[1], x[0])))
# 最大値を取得
ma = ls_sorted[0][1]
print(ma)
# 上から順番に取り出す
for ke, va in ls_sorted:
# 個数が最大値と一緒なら、
if(va == ma):
# 文字を出力する。
print(ke)
C問題
方針
- プラスマイナスの累積和だったりで、良い括弧列かどうかは判定できるが、毎回やっていると、
O(Q^2)となってしまう。 - というわけで、右側からしか操作をしないことを踏まえると、なんとか括弧が右から一個変わるくらいだったら、定数時間で求められないだろうか。
- そこで、以下の二つの変数を用いる。
-
)があと何個来たら、良い括弧列になるかを管理する変数cntを用いる。 - また、
(が超過して発生したら、そこの場所を記録する変数indを用いる。
-
前提
-
C問題あたりで，TLEになる人は，制約条件を見る癖をつけよう． -
AとB問題では，基本的に制約条件を見ずにやっても解ける． - しかし，
C問題以降では，制約条件を見ないと必ずTLEすると思っても良い． - 詳しい話は私の352回の記事 の
C問題の解説に記したので，是非参照してほしい．
C.py
"""
<方針>
- プラスマイナスの累積和だったりで、良い括弧列かどうかは判定できるが、毎回やっていると、`O(Q^2)` となってしまう。
- というわけで、右側からしか操作をしないことを踏まえると、なんとか括弧が右から一個変わるくらいだったら、定数時間で求められないだろうか。
- そこで、以下の二つの変数を用いる。
- `)` があと何個来たら、良い括弧列になるかを管理する変数 `cnt` を用いる。
- また、`(` が超過して発生したら、そこの場所を記録する変数 `ind` を用いる。
"""
ind = None # 先に")"が来てしまい、良い括弧列が崩れたところ
cnt = 0 # 括弧の個数が、良い括弧列を満たすようにバランスが良いかどうか
p = [] # 今の括弧列。長さを取るためだけに存在。
Q = int(input())
for _ in range(Q):
query = list(input().split())
match query:
case ["1", c]:
p.append(c) # 追加
cnt -= 1 if(c == ")") else -1 # カウントを変える
case ["2"]:
c = p.pop() # 削除
cnt += 1 if(c == ")") else -1 # カウントを変える
# まだ先に")"が来てない時、
if(ind is None):
# 先に")"が来てしまった時、
if(cnt < 0):
ind = len(p)
# 先に")"が来てるとき、
else:
# ")"を削除した時、
if(len(p) < ind):
# 戻す
ind = None
# 個数がバランスされていて、先に")"が来てない時、
if((cnt == 0) and (ind is None)):
print("Yes")
else:
print("No")
補足
関係するリンク(参考文献など)
筆者について
- Atcoderアカウント
- 今回も不参加のため，成績なし．
- 解説で示したA問題の提出
- 解説で示したB問題の提出
- 解説で示したC問題の提出
その他
- 間違いを含んでいる可能性があります．
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
最後に一言
- さみだれを
- あつめてやばし
- どなうがわ
- あつめてやばし
この記事書き続けてるけど、意味あるんかな...