ABC364(Atcoder Beginner Contest)のA~E(A,B,C,D,E)問題をPythonで解説(復習)
A問題
-
2個連続してsweetとなっている箇所があったら，Noを出力する． - 最後の
2個はsweetが連続していても問題ないので，確認しない．
A.py
"""
<方針>
- `2` 個連続して `sweet` となっている箇所があったら， `No` を出力する．
- 最後の `2` 個は `sweet` が連続していても問題ないので，確認しない．
"""
# 標準入力から受け取る
N = int(input())
S = [input() for _ in range(N)]
# 最後以外の連続した部分を確認する．
for i in range(N-2):
# sweet が連続していたら，
if(S[i] == S[i+1] == "sweet"):
# No を出力する．
print("No")
# プログラムを終了する．
exit()
# No を出力しなかった場合，
print("Yes")
B問題
- 実際に動かすシミュレーションを行う．
- 同じ処理はまとめて，違うところ(i.e. 上下左右の向き)は
ifで分けることで，コードを簡単にする．
B.py
"""
<方針>
- 実際に動かすシミュレーションを行う．
- 同じ処理はまとめて，違うところ(i.e. 上下左右の向き)は `if` で分けることで，コードを簡単にする．
"""
# 標準入力
H, W = map(int, input().split())
y, x = list(map(int, input().split()))
CC = [input() for _ in range(H)]
X = input()
# 現在の位置
y -= 1
x -= 1
for s in X:
# 上下左右方向の変化量
dx, dy = 0, 0
if s=="L":
dx -= 1
if s == "R":
dx += 1
if s== "D":
dy += 1
if s=="U":
dy -= 1
# 新しい座標
a = dx+x
b = dy+y
# 新しい座標が枠内に収まっていて，新しい座標が空きマスの時，
if(0<=a<W and 0<=b<H and CC[b][a]=="."):
# 座標の更新
x, y = a, b
# 座標を 0-indexed に注意して出力する．
print(y+1, x+1)
C問題
方針
-
甘さor塩さが限界値を超えたら，食べれなくなる． - 食べ物をそれぞれ
甘さと塩さで逆順ソートしておく． -
甘さがバーストするパターンと塩さがバーストするパターンにて，先にバーストする方が答え．
前提
-
C問題あたりで，TLEになる人は，制約条件を見る癖をつけよう． -
AとB問題では，基本的に制約条件を見ずにやっても解ける． - しかし，
C問題以降では，制約条件を見ないと必ずTLEすると思っても良い． - 詳しい話は私の352回の記事 の
C問題の解説に記したので，是非参照してほしい．
C.py
"""
<方針>
- `甘さ` or `塩さ` が限界値を超えたら，食べれなくなる．
- 食べ物をそれぞれ `甘さ` と `塩さ` で逆順ソートしておく．
- `甘さ` がバーストするパターンと `塩さ` がバーストするパターンにて，先にバーストする方が答え．
"""
N, X, Y = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
# どこまで食べるとバーストするかを確認する関数
def burst(A, X):
# 食べ物を逆順ソートする．
A.sort(reverse=True)
# 現在の甘さ(塩さ)
now = 0
# 何個食べたか
cnt = 0
# 食べ物を一個ずつ食べていく．
for a in A:
now += a
cnt += 1
# バーストした時，
if(now > X):
break
# 何個食べたかを返す．
return cnt
# 甘さ or 塩さ 先にバーストした方が出力
print(min(burst(A, X), burst(B, Y)))
D問題
-
potato167さんのユーザー解説の考えかたです．
D.py
"""
<方針>
- `potato167` さんのユーザー解説の考えかたです．
"""
N, Q = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
for i in range(Q):
b, k = map(int, input().split())
# A[l]<=b となる最大のlを求める．
l = -1
r = N
while r-l>1:
m = (r+l)//2
if(A[m]<=b):
l = m
else:
r = m
# b-A[l]>A[m+k-1]-b を満たす最大のlを求める．
r = min(l+1, N-k+1)
l = l - k + 1
while r-l>1:
# k近傍の左側の座標
m = (r+l)//2
# k近傍の右側の座標
m_k = m+k-1
# 左側がout of range
if(m<0):
l = m
# 右側がout of range
elif(N<=m_k):
r = m
# in range
else:
if(b-A[m]>A[m_k]-b):
l = m
else:
r = m
# k番目に遠いindex, tを求める．
t = None
# 左側が out of range
if(l<0):
t = k-1
# 右側が out of range
elif(N<=l+k):
t = l
# 枠内
else:
# 左側がk番目の時
if(b-A[l]<A[l+k]-b):
t = l
# 右側がk番目の時，
else:
t = l+k
# 距離を出力
print(abs(b-A[t]))
E問題
- 公式解説と一緒です．
- 愚直な
dpを構築して，tleしないように，valueとindexを入れ替える - 高橋君は腹をぶっ壊してでもすぬけ君に飯を食わせるので，
+1した値を答えにする． - だが，全部食っても腹を壊さない可能性があるので，
Nとminをとる．
E.py
"""
<方針>
- 公式解説と一緒です．
- 愚直な `dp` を構築して， `tle` しないように， `value` と `index` を入れ替える
- 高橋君は腹をぶっ壊してでもすぬけ君に飯を食わせるので， `+1` した値を答えにする．
- だが，全部食っても腹を壊さない可能性があるので， `N` と `min` をとる．
"""
N, X, Y = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(N)]
INF = 10**10
# 愚直→iまでの料理で，甘さj, 塩さkの時に，最大val食えた
# 今回→iまでの料理で，j食って，甘さkの時に，最小の塩さ
dp = [[[INF]*(X+1) for _ in range(N+1)] for _ in range(N+1)]
# 初期値
dp[0][0][:] = [0]*(X+1)
# dp
for i in range(N):
for j in range(i+1):
for k in range(X+1):
a, b = AB[i]
# 料理iを選択しない時，
dp[i+1][j][k] = min(dp[i+1][j][k], dp[i][j][k])
# 料理iを選択する時，
if(k+a<=X):
dp[i+1][j+1][k+a] = min(dp[i+1][j+1][k+a], dp[i][j][k]+b)
# なるべくたくさん食べれたケースを仮定する．
for j in reversed(range(N+1)):
# 食った時に，塩さがY以下の時は，あと1品食べれる
if(min(dp[N][j]) <= Y):
# 腹壊してでももう一個食う or 全部食えた
print(min(j+1, N))
exit()
補足
関係するリンク(参考文献など)
筆者について
その他
- 間違いを含んでいる可能性があります．
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
最後に一言
- 2分探索をソラで書けるようになった(かも)．