[ABC388] ABC 388(Atcoder Beginner Contest)のA~E(A,B,C,D,E)問題をPythonで解説(復習)

# [ABC388] ABC 388(Atcoder Beginner Contest)のA~E(A,B,C,D,E)問題をPythonで解説(復習)

# A問題
- スライス `[0]` を用いて入力の先頭を取得する．
- 文字列を `+` で結合する．
```A.py
"""
<方針>
- スライス `[0]` を用いて入力の先頭を取得する．
- 文字列を `+` で結合する．
"""
# 入力
S = input()

# 頭の文字
head = S[0]
# 結合
ans = head + "UPC"

# 出力
print(ans)
```

# B問題
- 🐍それぞれの現在の重さを管理する変数 `W` を作成する．
- `D` 回🐍それぞれの重さ `W` を🐍それぞれの太さ `T` を用いて更新する．
- その時の🐍の一番重たいやつを出力する．
```B.py
"""
<方針>
- 🐍それぞれの現在の重さを管理する変数 `W` を作成する．
- `D` 回🐍それぞれの重さ `W` を🐍それぞれの太さ `T` を用いて更新する．
- その時の🐍の一番重たいやつを出力する．
"""
# 入力
N, D = map(int, input().split())
T = [] # 太さ
L = [] # 長さ
W = [] # 重さ
for _ in range(N):
  t, l = map(int, input().split())
  T.append(t) # 太さ
  L.append(l) # 長さ
  W.append(t*l) # 重さ

# D回伸ばす
for _ in range(D):
  # 蛇全員の重さを更新する
  for i in range(N):
    W[i] += T[i] # 太さを用いて重さを更新
  
  # 現在一番重たいやつを出力する．
  print(max(W))
```

# C問題
## 方針
- 全ての組み合わせをフルメッシュで確認していたら，`O(N^2)` となってしまい，当然間に合わない．
- なので，土台 `a` を固定して，上にセットできるやつがいくつあるかを効率よく探したい．
- 大きさが小さい順に並んでいるので，二分探索で見つけていけば良い．
  - めぐる式二分探索を組めるようになるとバグらせにくい．
- 二分探索なので，`O(logN)` より，全体として，`O(NlogN)` で解くことができる．
## 前提
- `C`問題あたりで，`TLE`になる人は，制約条件を見る癖をつけよう．
- `A`と`B`問題では，基本的に制約条件を見ずにやっても解ける．
- しかし，`C`問題以降では，制約条件を見ないと必ず`TLE`すると思っても良い．
- 詳しい話は私の[352回の記事](https://qiita.com/mattsunkun/items/837444254f03e6105922) の`C`問題の解説に記したので，是非参照してほしい．
```C.py
"""
<方針>
- 全ての組み合わせをフルメッシュで確認していたら，`O(N^2)` となってしまい，当然間に合わない．
- なので，土台 `a` を固定して，上にセットできるやつがいくつあるかを効率よく探したい．
- 大きさが小さい順に並んでいるので，二分探索で見つけていけば良い．
  - めぐる式二分探索を組めるようになるとバグらせにくい．
- 二分探索なので，`O(logN)` より，全体として，`O(NlogN)` で解くことができる．
"""
# 入力
N = int(input())
A = list(map(int, input().split()))


ans = 0 # 組み合わせの総数
# 土台を固定する．
for a in A:
  
  # めぐる式二分探索．詳しくはググってみてください．
  ok = -1 # 上に乗っけられる最大のindex
  ng = N # 乗っけられないやつ
  while abs(ok-ng) > 1:
    mid = (ok+ng)//2
    if(A[mid]<=a//2):
      ok = mid
    else:
      ng = mid
  
  # 個数を登録
  ans += (ok + 1)

# 出力
print(ans)
```

# D問題
- 線形時間で解く方法を考えると，年をとる左の人から順番に石の最終的な数を考えれば良さそう．
- そのためには，石がもらえなくなる数を保持する `lost` と，いつから石がもらえなくなるかの `when` を用意する．
- `i` 番目の人の具体的な計算方法
  - まず，石がもらえなくなる数を更新するので，`lost += when[i]` とする．
  - その人は，`earn = i - lost` の石を左の人からもらえる．
  - その人は，自分の石が途中でなくならなければ，`give = N - 1 -i` の意思を右の人に渡す．
  - なので，その人が持っている最終的な石の数は，`b = A[i] + take - give` になる．
  - もし，`b` が負の値になれば，`b` を `0` にし，`when[N+b] += 1` として，自分の石が `0` になるタイミングを記録する．
```D.py
"""
<方針>
- 線形時間で解く方法を考えると，年をとる左の人から順番に石の最終的な数を考えれば良さそう．
- そのためには，石がもらえなくなる数を保持する `lost` と，いつから石がもらえなくなるかの `when` を用意する．
- `i` 番目の人の具体的な計算方法
  - まず，石がもらえなくなる数を更新するので，`lost += when[i]` とする．
  - その人は，`earn = i - lost` の石を左の人からもらえる．
  - その人は，自分の石が途中でなくならなければ，`give = N - 1 -i` の意思を右の人に渡す．
  - なので，その人が持っている最終的な石の数は，`b = A[i] + take - give` になる．
  - もし，`b` が負の値になれば，`b` を `0` にし，`when[N+b] += 1` として，自分の石が `0` になるタイミングを記録する．
"""
# 入力
N = int(input())
A = list(map(int, input().split()))

lost = 0 # 石がもらえなくなった個数
when = [0]*N # いつ石がもらえなくなるか
B = [] # 答え
# 左から順番に見る
for i in range(N):
  # 石の数を更新
  lost += when[i]
  # 受け取る石の個数
  take = i - lost
  # できれば与えたい石の個数
  give = N - 1 - i
  # 最終的な石の数(負の値を許容)
  b = A[i] + take - give
  
  # 石の数が負の値の時，
  if(b<0):
    # 自分の石を失うタイミングを記録する．
    if(0<=N+b<=N-1):
      when[N+b] += 1
    # 石の個数を本当の値である，0にする．
    b = 0
  
  # 答えに記録
  B.append(b)

# 出力
print(*B)
```

# E問題
- `K` 個の鏡餅を作成するときは，前からと後ろからで `K` 個ずつ作成するパターンさえ試せば十分である．
- 適切な `K` を二分探索で調べれば良い．
- 全体の計算量は，`O(NlogN)`
```E.py
"""
<方針>
- `K` 個の鏡餅を作成するときは，前からと後ろからで `K` 個ずつ作成するパターンさえ試せば十分である．
- 適切な `K` を二分探索で調べれば良い．
- 全体の計算量は，`O(NlogN)`
"""
# 入力
N = int(input())
A = list(map(int, input().split()))

# 二分探索
ok = 0
ng = N//2 + 1
while abs(ok-ng)>1:
  mid = (ok+ng)//2
  K = mid
  flag = True # 鏡餅がK個作れる時はTrueである．
  # 前後からK個順番に取ってくる
  for top, bottom in zip(A[:K], A[-K:]):
    # 鏡餅が作れない時，
    if (top>bottom//2):
      # 作れないフラグを立てる
      flag = False
  
  # 鏡餅が作れるかどうか
  if(flag):
    ok = mid
  else:
    ng = mid

# 出力
print(ok)
```

# 補足
### 関係するリンク(参考文献など)
- [今回のコンテスト](https://atcoder.jp/contests/abc388)
### 筆者について
- [Atcoderアカウント](https://atcoder.jp/users/mattsunkun)
- *今回も不参加のため，成績なし．*
- [解説で示したA問題の提出](https://atcoder.jp/contests/abc388/submissions/61608552)
- [解説で示したB問題の提出](https://atcoder.jp/contests/abc388/submissions/61609904)
- [解説で示したC問題の提出](https://atcoder.jp/contests/abc388/submissions/61612699)
- [解説で示したD問題の提出](https://atcoder.jp/contests/abc388/submissions/61613731)
- [解説で示したE問題の提出](https://atcoder.jp/contests/abc388/submissions/61614092)
### その他
- **間違いを含んでいる可能性があります．**
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
### 最後に一言
- 友人に勧められて，独学大全を部分的に読んでいます．