ABC364(Atcoder Beginner Contest)のA~E(A,B,C,D,E)問題をPythonで解説(復習)

# 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回の記事](https://qiita.com/mattsunkun/items/837444254f03e6105922) の`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()
```

# 補足
### 関係するリンク(参考文献など)
- [今回のコンテスト](https://atcoder.jp/contests/abc364)
- [D問題のユーザ解説](https://atcoder.jp/contests/abc364/editorial/10566)
- [E問題の公式解説](https://atcoder.jp/contests/abc364/editorial/10550)
### 筆者について
- [Atcoderアカウント](https://atcoder.jp/users/mattsunkun)
- [今回の成績(oooxx--)](https://atcoder.jp/users/mattsunkun/history/share/abc364)
- [解説で示したA問題の提出](https://atcoder.jp/contests/abc364/submissions/56103653)
- [解説で示したB問題の提出](https://atcoder.jp/contests/abc364/submissions/56103785)
- [解説で示したC問題の提出](https://atcoder.jp/contests/abc364/submissions/56103970)
- [解説で示したD問題の提出](https://atcoder.jp/contests/abc364/submissions/56104207)
- [解説で示したE問題の提出](https://atcoder.jp/contests/abc364/submissions/56099907)
### その他
- **間違いを含んでいる可能性があります．**
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
### 最後に一言
- 2分探索をソラで書けるようになった(かも)．