[ABC394] ABC 394(Atcoder Beginner Contest)のA~D(A,B,C,D)問題をPythonで解説(復習)
A問題
- 文字を一つずつ見て、
"2"だった場合は、答えに追記する。
A.py
"""
<方針>
- 文字を一つずつ見て、`"2"` だった場合は、答えに追記する。
"""
# 入力
S = input()
# 答え
ans = ""
# 文字を一つずつ見る
for s in S:
# 文字が"2"かどうかをみる
if(s == "2"):
# 答えに追記する。
ans += s
# 出力
print(ans)
B問題
- リストで受け取り、文字の長さでソートする。
- リストを
joinで連結して出力する。
B.py
"""
<方針>
- リストで受け取り、文字の長さでソートする。
- リストを `join` で連結して出力する。
"""
# 入力
N = int(input())
SS = []
for _ in range(N):
S = input()
SS.append(S)
# 文字の長さでソート
SS.sort(lambda S: len(S))
# 連結する。
ans = "".join(SS)
# 出力
print(ans)
C問題
方針
- 毎回左から順番に
WAがあるかどうかを見ていたら、文字列の長さNに対して、O(N^2)かかってしまう。 - なんとか一回見るだけで済ませたい。
- 法則
-
WA->AC -
WWA->ACC -
WWWA->ACCC -
W...WA->AC...C
-
- 法則に従って左から一回だけ見れば、
O(N)でいけそう。
前提
-
C問題あたりで，TLEになる人は，制約条件を見る癖をつけよう． -
AとB問題では，基本的に制約条件を見ずにやっても解ける． - しかし，
C問題以降では，制約条件を見ないと必ずTLEすると思っても良い． - 詳しい話は私の352回の記事 の
C問題の解説に記したので，是非参照してほしい．
C.py
"""
<方針>
- 毎回左から順番に `WA` があるかどうかを見ていたら、文字列の長さ `N` に対して、`O(N^2)` かかってしまう。
- なんとか一回見るだけで済ませたい。
- 法則
- `WA` -> `AC`
- `WWA` -> `ACC`
- `WWWA` -> `ACCC`
- `W...WA` -> `AC...C`
- 法則に従って左から一回だけ見れば、`O(N)` でいけそう。
"""
# 入力
S = list(input())
# Wが連続した回数
wCnt = 0
# 前から見ていく
for i in range(len(S)):
# Wの時
if(S[i] == "W"):
# カウントする
wCnt += 1
# Wじゃないとき
else:
# Aの時
if(S[i] == "A"):
# Wが溜まってる時
if wCnt > 0:
# 最初をAにする
S[i - wCnt] = "A"
# そこからはCにする
while wCnt > 0:
wCnt -= 1
S[i - wCnt] = "C"
# Wのカウントを0に戻す。
wCnt = 0
# 出力
print("".join(S))
D問題
-
dequeを使って、右から文字を入れていき、最右でペアができるかを判定し、最終的に空になるかどうかをみる。
D.py
"""
<方針>
- `deque` を使って、右から文字を入れていき、最右でペアができるかを判定し、最終的に空になるかどうかをみる。
"""
# ライブラリ
from collections import deque
# 入力
S = deque(list(input()))
# キュー
q = deque()
# 入力を回す
while S:
# 左から取り出し、
s = S.popleft()
# キューに追加する
q.append(s)
# キューの右側二つを見る
while True:
if(
# キューが二つ以上要素を持つ
len(q) >= 2 and
# ペアができているかどうか
(
(q[-2] == "(" and q[-1] == ")") or
(q[-2] == "[" and q[-1] == "]") or
(q[-2] == "<" and q[-1] == ">")
)
):
# ペアを対消滅させる
q.pop()
q.pop()
else:
# 対消滅できなかったときは抜ける。
break
# キューがからの時
if not q:
print("Yes")
# キューに残っている時
else:
print("No")
補足
関係するリンク(参考文献など)
筆者について
- Atcoderアカウント
- 今回も不参加のため，成績なし．
- 解説で示したA問題の提出
- 解説で示したB問題の提出
- 解説で示したC問題の提出
- 解説で示したD問題の提出
その他
- 間違いを含んでいる可能性があります．
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
最後に一言
-
第342回からABCの記事を毎週書き続けて、今回が
(394 - 342 + 1 = )53回目だから多分１年経った（？）