[ABC408] ABC 408(Atcoder Beginner Contest)のA~D(A,B,C,D)問題をPythonで解説(復習)
A問題
-
Tの差分がSを超えたら、長老は寝てしまう。 -
T_-1を導入して、0秒目に肩を叩く番兵を作る。
A.py
"""
<方針>
- `T` の差分が `S` を超えたら、長老は寝てしまう。
- `T_-1` を導入して、`0` 秒目に肩を叩く番兵を作る。
"""
# 入力
N, S = map(int, input().split())
T = list(map(int, input().split()))
# 番兵
T = [0] + T
# 差分を順番に見る。
for i in range(N):
# `T` の差分が `S` を超えたら、
if(S < (T[i+1] - T[i])):
# 寝て、プログラムを終了する。
print("No")
exit()
# 長老は寝なかった。
print("Yes")
B問題
-
setに入れて、重複を消す。 -
.sort()して、小さい順にする。 - アンパック
*して、出力する。
B.py
"""
<方針>
- `set` に入れて、重複を消す。
- `.sort()` して、小さい順にする。
- アンパック `*` して、出力する。
"""
# 入力
N = int(input())
A = list(map(int, input().split()))
# 重複を消し、リストに戻す。
C = list(set(A))
# 小さい順にする。
C.sort()
# 出力
print(len(C))
print(*C)
C問題
方針
- それぞれの壁が幾つの砲台に守られているか
Pを計算できれば、後は、その中で最小の数字を返せば良い。 - しかし、素朴にそれぞれの
L,Rに対して、一つずつPを構築すると、O(MN)かかってしまう。 - そこで、累積和を考えると、計算量が
O(M+N)になる。 - 全体でも計算量は
O(M+N)程度になるだろう。
前提
-
C問題あたりで，TLEになる人は，制約条件を見る癖をつけよう． -
AとB問題では，基本的に制約条件を見ずにやっても解ける． - しかし，
C問題以降では，制約条件を見ないと必ずTLEすると思っても良い． - 詳しい話は私の352回の記事 の
C問題の解説に記したので，是非参照してほしい．
C.py
"""
<方針>
- それぞれの壁が幾つの砲台に守られているか `P` を計算できれば、後は、その中で最小の数字を返せば良い。
- しかし、素朴にそれぞれの `L`, `R` に対して、一つずつ `P` を構築すると、`O(MN)` かかってしまう。
- そこで、累積和を考えると、計算量が `O(M+N)` になる。
- 全体でも計算量は `O(M+N)` 程度になるだろう。
"""
N, M = map(int, input().split())
P = [0]*(N+2) # 累積和のためのマージンもとっておく
# フラグを立てる
for _ in range(M):
L, R = map(int, input().split())
P[L] += 1
P[R+1] -= 1
# 累積する。
for i in range(len(P)-1):
P[i+1] += P[i]
# 端っこは含まない
ans = min(P[1:-1])
print(ans)
D問題
- ユーザー（AngrySadEight）公式解説と一緒です。
D.py
"""
- ユーザー（AngrySadEight）公式解説と一緒です。
"""
T = int(input())
for _ in range(T):
N = int(input())
S = list(map(int, list(input())))
# dp
dp = [[None]*3 for _ in range(N+1)]
dp[0] = [0]*3 # 初期値
# 遷移
for i in range(N):
dp[i+1][0] = dp[i][0] + int(S[i] != 0)
dp[i+1][1] = min(dp[i][0] + int(S[i] != 1), dp[i][1] + int(S[i] != 1))
dp[i+1][2] = min(dp[i][1] + int(S[i] != 0), dp[i][2] + int(S[i] != 0))
# 答え
ans = min(dp[N])
print(ans)
補足
関係するリンク(参考文献など)
筆者について
- Atcoderアカウント
- 今回も不参加のため，成績なし．
- 解説で示したA問題の提出
- 解説で示したB問題の提出
- 解説で示したC問題の提出
- 解説で示したD問題の提出
その他
- 間違いを含んでいる可能性があります．
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
最後に一言
- 晴れ時々
ヘビー・ウェザー