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

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

# A問題
- `0` と `1` の `falsy` や `truthy` な特性を使って解く．
- `not L and R` の時は `No`
- `L and not R` の時は `Yes`
- それ以外の時は `Invalid` である．
```A.py
"""
<方針>
- `0` と `1` の `falsy` や `truthy` な特性を使って解く．
- `not L and R` の時は `No`
- `L and not R` の時は `Yes`
- それ以外の時は `Invalid` である．
"""
# 入力
L, R = map(int, input().split())

# Rのとき
if(not L and R):
  print("No")
# Lのとき
elif(L and not R):
  print("Yes")
# 判定不能
else:
  print("Invalid")
```

# B問題
- シミュレーションを行う．ただし， `0-indexed`で行う(`0~N-1` の数字のみを利用する．)
- 入力を受け取り，二つの元素がどう変化するかの配列 `A` をあらかじめ作っておく．
- 最初に現在の元素(`e`) `0` をもち， `0~N-1` を与えていく
- ただし，現在の元素の方が番号が大きかったら，スワップする．
- `0-indexed` で処理を行っているため，最後の出力に `+1` をすることを忘れてはいけない．
```B.py
"""
<方針>
- シミュレーションを行う．ただし， `0-indexed`で行う(`0~N-1` の数字のみを利用する．)
- 入力を受け取り，二つの元素がどう変化するかの配列 `A` をあらかじめ作っておく．
- 最初に現在の元素(`e`) `0` をもち， `0~N-1` を与えていく
- ただし，現在の元素の方が番号が大きかったら，スワップする．
- `0-indexed` で処理を行っているため，最後の出力に `+1` をすることを忘れてはいけない．
"""
# 入力
N = int(input())
A = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(N)]

# 現在の元素
e = 0
# シミュレーション
for i in range(N):
  # 現在の元素の方が大きい時は，
  if(e>i):
    # スワップする
    e, i = i, e
  
  # 現在の元素を更新する
  e = A[i][e]

# 現在の元素を出力する．
print(e+1)
```

# C問題
## 方針
- 文字が異なる部分を一つずづ変更すれば良い．
- しかし，どの順番で変更するかを考えないと，計算時間が現実的でない．全パターン試すと， `O(len(S)!)` になってしまう．
- 実は，以下の２回に分けて変更すると，効率が最も良い．
  - 先頭から見て，辞書順で大きいやつがあれば，変更する．
  - 後ろから見て，辞書順で小さいやつがあれば，変更する．
- 以上を行うと， `S==T` となり，制約を満たす `X` が得られる．計算時間は `O(len(S))`
## 前提
- `C`問題あたりで，`TLE`になる人は，制約条件を見る癖をつけよう．
- `A`と`B`問題では，基本的に制約条件を見ずにやっても解ける．
- しかし，`C`問題以降では，制約条件を見ないと必ず`TLE`すると思っても良い．
- 詳しい話は私の[352回の記事](https://qiita.com/mattsunkun/items/837444254f03e6105922) の`C`問題の解説に記したので，是非参照してほしい．
```C.py
"""
<方針>
- 文字が異なる部分を一つずづ変更すれば良い．
- しかし，どの順番で変更するかを考えないと，計算時間が現実的でない．全パターン試すと， `O(len(S)!)` になってしまう．
- 実は，以下の２回に分けて変更すると，効率が最も良い．
  - 先頭から見て，辞書順で大きいやつがあれば，変更する．
  - 後ろから見て，辞書順で小さいやつがあれば，変更する．
- 以上を行うと， `S==T` となり，制約を満たす `X` が得られる．計算時間は `O(len(S))`
"""
# 入力
S = list(input())
T = list(input())

# 文字列の長さ
N = len(S)

# 答え
X = []

# 先頭から見る
for i in range(N):
  # 辞書順で大きい時，
  if(S[i]>T[i]):
    # 文字を変える
    S[i] = T[i]
    # 答えに追記
    X.append(S[:])

# 後ろから見る
for i in reversed(range(N)):
  # 辞書順で小さいとき
  if(S[i]<T[i]):
    # 文字を変える
    S[i]=T[i]
    # 答えに追記
    X.append(S[:])
    
# 出力
print(len(X))
for x in X:
  # Xを一つずつ，出力する．
  print("".join(x))
```

# D問題
## `SortedSet` を使う方針
- 公式解説と一緒です．
```D(SortedSet).py
"""
<方針>
- 公式解説と一緒です．
"""
from sortedcontainers import SortedSet
from bisect import bisect

H, W, Q = map(int, input().split())

g1 = [SortedSet() for _ in range(H)]
g2 = [SortedSet() for _ in range(W)]

# 壁を全て登録
for i in range(H):
  for j in range(W):
    g1[i].add(j)
    g2[j].add(i)

# 壁を消す(g1, g2のデータを同時に消す必要があるため．)
def erase(i, j):
  g1[i].discard(j)
  g2[j].discard(i)

for _ in range(Q):
  r, c = map(int, input().split())
  r -= 1;c -= 1
  
  # 壁があったら
  if c in g1[r]:
    # その壁を消す
    erase(r, c)
  # 壁がなかったら
  else:
    # 左右のブロックを削除する
    if(g1[r]):
      m = bisect(g1[r], c)
      for j in [m, m-1]:
        if(0<=j<len(g1[r]) and 0<=g1[r][j]<W):
          erase(r, g1[r][j])
    
    # 上下のブロックを削除する
    if(g2[c]):
      m = bisect(g2[c], r)
      for i in [m, m-1]:
        if(0<=i<len(g2[c]) and 0<=g2[c][i]<H):
          erase(g2[c][i], c)

print(sum([len(g1[i]) for i in range(H)]))
  
```

# D問題
## `UnionFind` を使う方針
- ユーザ解説と一緒です．

```D(UnionFind).py
"""
<方針>
- ユーザ解説と一緒です．
"""

# 最左右を保持するUnionFind
class UnionFind:
  
  def __init__(self, N):
    # 全体要素数
    self.N = N
    # 根っこの時は，-(要素数)を表し，そうで無い時は，親のインデックス
    self.P = [-1]*N
    # 最左のもの
    self.L = list(range(N))
    # 最右のもの
    self.R = list(range(N))
  
  def find(self, x):
    # 根っこと判定されたとき
    if(self.P[x] < 0):
      # 根っこを返す
      return x
    # 根っこでないとき
    else:
      # 経路圧縮
      self.P[x] = self.find(self.P[x])
      # 親を返す
      return self.P[x]
  
  def union(self, y, x):
    # 根っこを取得
    y = self.find(y)
    x = self.find(x)
    
    # 同一グループだったら終了
    if(x==y):return
    
    # xの方が要素数が小さい時，
    if(-self.P[x] < -self.P[y]):
      # xの方が要素数が大きいようにする
      x, y = y, x 
    
    # xの要素数を増やす
    self.P[x] += self.P[y]
    # yの親をxにする
    self.P[y] = x
    # 最左を更新
    self.L[x] = min(self.L[x], self.L[y])
    # 最右を更新
    self.R[x] = max(self.R[x], self.R[y])
    
  # 最左右を取得
  def LR(self, x):
    # 根っこが最左右のデータを持っているため，根っこに変更
    x = self.find(x)
    return self.L[x], self.R[x]

# 入力 
H, W, Q = map(int, input().split())

# UnionFindを縦横別で保持
ufYX = [UnionFind(W) for _ in range(H)]
ufXY = [UnionFind(H) for _ in range(W)]

# 壁が削除されたかどうか
erased = [[False]*(W) for _ in range(H)]

# 壁を削除する
def erase(y, x):
  # 有効範囲内の時のみ処理
  if(0<=y<H and 0<=x<W):
    # 壁を削除
    erased[y][x] = True
    
    # 上下の壁の最左右を登録
    for d in [-1, 1]:
      Y = y + d
      # 壁が存在する時
      if(0<=Y<H and erased[Y][x]):
        # 最左右を更新
        ufXY[x].union(y, Y)
    
    # 左右の壁の最左右を登録
    for d in [-1, 1]:
      X = x + d
      # 壁が存在する時
      if(0<=X<W and erased[y][X]):
        # 最左右を更新
        ufYX[y].union(x, X)

# シミュレーション
for _ in range(Q):
  # 入力
  y, x = map(int, input().split())
  y -= 1;x -= 1
  
  # 壁が破壊されている時，
  if(erased[y][x]):
    # 上下の壁を壊す
    Lx, Rx = ufYX[y].LR(x)
    erase(y, Lx - 1)
    erase(y, Rx + 1)
    
    # 左右の壁を壊す
    Ly, Ry = ufXY[x].LR(y)
    erase(Ly - 1, x)
    erase(Ry + 1, x)
  
  # 壁が破壊されていない時，
  else:
    # その壁を壊す
    erase(y, x)

# 残った壁の数を計測
print(H*W - sum(sum(erased, [])))
```

# 補足
### 関係するリンク(参考文献など)
- [今回のコンテスト](https://atcoder.jp/contests/abc370)
- [D問題の公式解説(SortedSet)](https://atcoder.jp/contests/abc370/editorial/10857)
- [D問題のユーザー解説(UnionFind)](https://atcoder.jp/contests/abc370/editorial/10883)
### 筆者について
- [Atcoderアカウント](https://atcoder.jp/users/mattsunkun)
- [今回の成績(ooox---)](https://atcoder.jp/users/mattsunkun/history/share/abc370)
- [解説で示したA問題の提出](https://atcoder.jp/contests/abc370/submissions/57608113)
- [解説で示したB問題の提出](https://atcoder.jp/contests/abc370/submissions/57608387)
- [解説で示したC問題の提出](https://atcoder.jp/contests/abc370/submissions/57608646)
- [解説で示したD問題(SortedSet)の提出](https://atcoder.jp/contests/abc370/submissions/57608714)
- [解説で示したD問題(UnionFind)の提出](https://atcoder.jp/contests/abc370/submissions/57607865)
### その他
- **間違いを含んでいる可能性があります．**
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
### 最後に一言
- D問題が解けそうで解けなくて，時間だけが溶けました🫠🫠🫠