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

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

# A問題
- 全体の半分(`half`)より多い票数を，高橋くん(`T`)が得ているか，青木くん(`A`)が得ていたら，勝敗は決定している．
```A.py
"""
<方針>
- 全体の半分(`half`)より多い票数を，高橋くん(`T`)が得ているか，青木くん(`A`)が得ていたら，勝敗は決定している．
"""
# 標準入力を受け取っている．
N, T, A = map(int, input().split())

# 全体の半分
half = N//2

# もし，高橋くんor青木くんが全体の半分より多く表を得ていたら，
if(T>half or A>half):
  # 勝敗は決定している．
  print("Yes")
else:
  # 勝敗は決まらず．
  print("No")
```

# B問題
- 制約の最大 `MAX=100` 行分の多重リスト( `SS` )を作成しておく(これに逆順で文字を追記していくこととする)．
- まず文字列( `S` )を素直に受け取る．
- 今までで受け取った文字列で最も長い分( `ma` )だけ `SS` に追記する．文字がない時は `*` で代用する．
- `SS` に逆順で文字を入れているので，出力する時は `[::-1]` を用いて正順に戻す．
```B.py
"""
<方針>
- 制約の最大 `MAX=100` 行分の多重リスト( `SS` )を作成しておく(これに逆順で文字を追記していくこととする)．
- まず文字列( `S` )を素直に受け取る．
- 今までで受け取った文字列で最も長い分( `ma` )だけ `SS` に追記する．文字がない時は `*` で代用する．
- `SS` に逆順で文字を入れているので，出力する時は `[::-1]` を用いて正順に戻す．
"""
# 制約の最大行数
MAX = 100
# 標準入力を受け取る
N = int(input())
SS = [[] for _ in range(MAX)]

# 文字列の最大長
ma = 0
# N回文字を受け取る
for i in range(N):
  # 文字を素直に受け取る
  S = input()
  
  # 文字列の最長を更新する．
  ma = max(ma, len(S))
  
  # 文字をSSに追記していく
  for j in range(ma):
    # 追記する文字
    s = None
    
    # 文字があるときは
    if(j<len(S)):
      # その文字を使う
      s = S[j]
    # 文字がない時は，
    else:
      # *で代用する．
      s = "*"
    
    # SSにsを追記する．
    SS[j].append(s)

for i in range(ma):
  # 区切り文字なしで，正順に戻して出力する．
  print("".join(SS[i][::-1]))
```

# C問題
## 方針

- バッグに整数がどれだけ格納されているかを管理するリスト( `bag` )を作成する．
- 毎回 `bag` の中にある整数の種類を計算しては `O(xQ)` で `tle` してしまう．
- そこで， `bag` の中にある整数の数を記録する変数( `kinds` )を用意する．
- `bag` の中にある"任意の整数"の数が `0->1` になる時と， `1->0` となる時に書き換えれば良い．
## 前提
- `C`問題あたりで，`TLE`になる人は，制約条件を見る癖をつけよう．
- `A`と`B`問題では，基本的に制約条件を見ずにやっても解ける．
- しかし，`C`問題以降では，制約条件を見ないと必ず`TLE`すると思っても良い．
- 詳しい話は私の[352回の記事](https://qiita.com/mattsunkun/items/837444254f03e6105922) の`C`問題の解説に記したので，是非参照してほしい．
```C.py
"""
<方針>
- バッグに整数がどれだけ格納されているかを管理するリスト( `bag` )を作成する．
- 毎回 `bag` の中にある整数の種類を計算しては `O(xQ)` で `tle` してしまう．
- そこで， `bag` の中にある整数の数を記録する変数( `kinds` )を用意する．
- `bag` の中にある"任意の整数"の数が `0->1` になる時と， `1->0` となる時に書き換えれば良い．
"""

# バッグの中に入りうる整数の種類の数
MAX = (10**6) + 1

# バッグを初期化する．最初は空
bag = [0]*MAX
# 何も入ってないので，0で初期化する．
kinds = 0

# クエリを処理する．
Q = int(input())
for i in range(Q):
  # クエリを受け取る．
  query = list(map(int, input().split()))
  match query:
    case [1, x]:
      # バッグにxを入れる
      bag[x] += 1
      # 0->1になった時，
      if(bag[x] == 1):
        # 種類が増えた．
        kinds += 1
        
    case [2, x]:
      # バッグからxを取り除く
      bag[x] -= 1
      # 1->0になった時，
      if(bag[x] == 0):
        # 種類が減った．
        kinds -= 1
        
    case [3]:
      # 種類を出力する．
      print(kinds)
```

# D問題
- 毎回値を計算していては `tle` するので，あらかじめ累積和を考えることで高速化を行う．
- 3次元の累積和なので，足しすぎに気をつけて適切に引いてあげる．
- 立方体でベン図を考えると意外とわかる．
```D.py
"""
<方針>
- 毎回値を計算していては `tle` するので，あらかじめ累積和を考えることで高速化を行う．
- 3次元の累積和なので，足しすぎに気をつけて適切に引いてあげる．
- 立方体でベン図を考えると意外とわかる．
"""
# 立体の情報を得る
N = int(input())
A = [[list(map(int, input().split())) for _ in range(N)] for _ in range(N)]

# 累積和を考える．0番目の値は0とする．
B = [[[0]*(N+1) for _ in range(N+1)] for _ in range(N+1)]
for i in range(1, N+1):
  for j in range(1, N+1):
    for k in range(1, N+1):
      B[i][j][k] = 0
      # 自分自身の値を足す
      B[i][j][k] += A[i-1][j-1][k-1]
      # 自分よりも一個横の奴らも足す
      B[i][j][k] += B[i-1][j][k] + B[i][j-1][k] + B[i][j][k-1]
      # 足しすぎたので，引く
      B[i][j][k] -= B[i-1][j-1][k] + B[i][j-1][k-1] + B[i-1][j][k-1]
      # 引きすぎたので足す．
      B[i][j][k] += B[i-1][j-1][k-1]

# クエリ処理
Q = int(input())
for _ in range(Q):
  x, X, y, Y, z, Z = map(int, input().split())
  
  ans = 0
  # まずは自分自身の位置を足す
  ans += B[X][Y][Z]
  # 足しすぎなので，引く
  ans -= B[x-1][Y][Z] + B[X][y-1][Z] + B[X][Y][z-1]
  # 引きすぎたので足す
  ans += B[x-1][y-1][Z] + B[X][y-1][z-1] + B[x-1][Y][z-1]
  # 引きすぎたので足す
  ans -= B[x-1][y-1][z-1]
  
  print(ans)
  
  
```

# E問題
- `x` と `y` 方向で分けて考えても問題ない．
- それぞれの方向で距離が `0~D` となる箇所がいくつあるかを計算する．
- コストの和が `D` 以下になるのを累積和を使って効率良く計算する．
```E.py
"""
<方針>
- `x` と `y` 方向で分けて考えても問題ない．
- それぞれの方向で距離が `0~D` となる箇所がいくつあるかを計算する．
- コストの和が `D` 以下になるのを累積和を使って効率良く計算する．
"""
# 標準入力を受け取る．
N, D = map(int, input().split())
X = []
Y = []
for i in range(N):
  x, y = map(int, input().split())
  X.append(x)
  Y.append(y)
  
# 引数のリストで距離を計算する．
def distance(A):
  # 引数をソートする．
  A.sort()
  
  # 距離がindexとなる点がいくつあるかをvalueとしたリスト
  ans = [0]*(D+1)
  
  # indexが範囲内の時に，ansに追記する関数
  def ad(a):
    if(a<=D):
      ans[a] += 1
  
  # 最左点における距離
  l = sum(map(lambda x: x - A[0], A))
  
  # 初期値とする
  di = l
  
  # ansに追記
  ad(di)
  
  # 次の点に移動しながらansを更新する．
  for i in range(N-1):
    
    # 次の点までのマスの数
    le = A[i+1] - A[i]
    
    # 横に動くと変動する距離
    de = -( (N - (i+1)) - (i+1) )
    
    # 横に移動させつつansに追記する．
    for j in range(le):
      di += de
      ad(di)
  
  # 最右点における距離
  r = di
  
  # 最左点から左に動かしつつansに追記する．
  for i in range(l+N, D+1, N):
    ad(i)
  
  # 最右点から右に動かしつつansに追記する．
  for i in range(r+N, D+1, N):
    ad(i)
  
  return ans

# X方向での距離を求める
P = distance(X)

# Y方向での距離を求める
Q = distance(Y)

# Y方向での結果の累積和を求める．
QQ = [0] * (D+1)
QQ[0] = Q[0]
for i in range(D):
  QQ[i+1] = QQ[i] + Q[i+1]

# 場合の数
ans = 0
for i in range(D+1):
  # X方向での距離がiとなった時にあり得る場合を足している．
  ans += P[i] * QQ[D-i]

print(ans)
```

# 補足
### 関係するリンク(参考文献など)
- [今回のコンテスト](https://atcoder.jp/contests/abc366)
### 筆者について
- [Atcoderアカウント](https://atcoder.jp/users/mattsunkun)
- *不参加より成績無し*
- [解説で示したA問題の提出](https://atcoder.jp/contests/abc366/submissions/56630475)
- [解説で示したB問題の提出](https://atcoder.jp/contests/abc366/submissions/56721035)
- [解説で示したC問題の提出](https://atcoder.jp/contests/abc366/submissions/56721207)
- [解説で示したD問題の提出](https://atcoder.jp/contests/abc366/submissions/56719102)
- [解説で示したE問題の提出](https://atcoder.jp/contests/abc366/submissions/56720692)
### その他
- **間違いを含んでいる可能性があります．**
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
### 最後に一言
- 実は [ARC181](https://atcoder.jp/users/mattsunkun/history/share/arc181) で入水しました💧🎉