[ABC402] ABC 402(Atcoder Beginner Contest)のA~D(A,B,C,D)問題をPythonで解説(復習)
A問題
-
strとして受け取る。 - 答え
ansを空文字列として用意しておく。 -
for文の中で、.isupper()メソッドを使って、大文字のみをansに追記する。
A.py
"""
<方針>
- `str` として受け取る。
- 答え `ans` を空文字列として用意しておく。
- `for` 文の中で、`.isupper()` メソッドを使って、大文字のみを `ans` に追記する。
"""
# 入力
S = input()
# 最初は空文字列
ans = ""
# 文字を取り出す。
for s in S:
# 大文字であれば、
if(s.isupper()):
# 答えに追記する。
ans += s
# 出力
print(ans)
B問題
- シミュレーションをする。
- 行列を管理する上で、
dequeを用いる。
B.py
"""
<方針>
- シミュレーションをする。
- 行列を管理する上で、`deque` を用いる。
"""
# ライブラリ
from collections import deque
# 行列
q = deque()
# シミュレーション
for _ in range(int(input())):
match list(map(int, input().split())):
case [1, X]:
# 行列に並ぶ
q.append(X)
case [2]:
# 先頭を出力
print(q.popleft())
C問題
方針
-
MもNも大きいので、O(MN)は無理なので、毎回料理を見る余裕は当然ない。 - それぞれの料理がいつから
D食べれるようになるかを予め調べれば良い。
前提
-
C問題あたりで，TLEになる人は，制約条件を見る癖をつけよう． -
AとB問題では，基本的に制約条件を見ずにやっても解ける． - しかし，
C問題以降では，制約条件を見ないと必ずTLEすると思っても良い． - 詳しい話は私の352回の記事 の
C問題の解説に記したので，是非参照してほしい．
C.py
"""
<方針>
- `M` も `N` も大きいので、`O(MN)` は無理なので、毎回料理を見る余裕は当然ない。
- それぞれの料理がいつから `D` 食べれるようになるかを予め調べれば良い。
"""
# 入力
N, M = map(int, input().split())
AA = []
for _ in range(M):
K, *A = map(int, input().split())
A = [a-1 for a in A]
AA.append(A)
B = list(map(int, input().split()))
B = [b-1 for b in B]
# B の index と value を入れ替える。
indB = [None]*N
for i, b in enumerate(B):
indB[b] = i
# 初めて料理を食べれるようになる日
D = [0]*N
# 料理を順番に調べる
for A in AA:
# 食材を克服する日
invA = [None]*len(A)
for i, a in enumerate(A):
invA[i] = indB[a]
# 最後の食材を克服する日が初めてその料理を食べれるようになる日
D[max(invA)] += 1
# 答え。食べれるものは累積和的に増えて行く。
ans = 0
for d in D:
ans += d
print(ans)
D問題
- 全ての直線が互いに平行でなければ、できる交点の数は
M*(M-1)//2となる。 - 互いに平行な直線が
X本ある時、X*(X-1)//2個交点の数は減る。 - 互いに平行かどうかは
(A+B)%Nでわかる（たぶん）。
D.py
"""
<方針>
- 全ての直線が互いに平行でなければ、できる交点の数は `M*(M-1)//2` となる。
- 互いに平行な直線が `X` 本ある時、 `X*(X-1)//2` 個交点の数は減る。
- 互いに平行かどうかは `(A+B)%N` でわかる（たぶん）。
"""
N, M = map(int, input().split())
# 平行なものを管理
parallels = [0]*N
for _ in range(M):
A, B = map(int, input().split())
parallels[(A+B)%N] += 1
# 平行が無いと仮定
ans = M*(M-1)//2
# 平行な数だけ減らす。
for X in parallels:
ans -= X*(X-1)//2
print(ans)
補足
関係するリンク(参考文献など)
筆者について
- Atcoderアカウント
- 今回も不参加のため，成績なし．
- 解説で示したA問題の提出
- 解説で示したB問題の提出
- 解説で示したC問題の提出
- 解説で示したD問題の提出
その他
- 間違いを含んでいる可能性があります．
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
最後に一言
- 煌く時は一瞬で、グッドラック昨日までの僕よ。