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

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

# A問題
- 「時」が前であるかをチェックする。
- 「時」が同じなら、「分」をチェックする。
```A.py
"""
<方針>
- 「時」が前であるかをチェックする。
- 「時」が同じなら、「分」をチェックする。
"""
# 入力
A, B, C, D = map(int, input().split())

# 時が前なら
if(A > C):
  print("Yes")
# 時が同じで、分が前なら
elif(A == C and B > D):
  print("Yes")
# それ以外
else:
  print("No")
```

# B問題
- `for` で順番にかけていき、`K+1` 桁以上になったら、`1` に戻す。
```B.py
"""
<方針>
- `for` で順番にかけていき、`K+1` 桁以上になったら、`1` に戻す。
"""
# 入力
N, K = map(int, input().split())
A = list(map(int, input().split()))

# 答え
ans = 1
# 順番に見る
for a in A:
  # かける
  ans *= a
  # 桁数がKを超えた時、
  if(len(str(ans)) > K):
    ans = 1

# 出力
print(ans)
```

# C問題
## 方針
- 全ての連続部分列を作成すると、`O(N^2)` かかり、とても間に合わない。
- なんとか線形時間で処理を組む必要がある。
- まず、`R` に、どの位置で、`^` or `v` になるかを見つける。 `O(N)`
- 次に、`R` を見て、`^` の次に `v` が来る場所を見つける。`O(N)`
- そのとき、`^` の一個前のやつとの距離を `l` とし、 `v` の一個次のやつとの距離を `r` とし、`l*r` を答えに追加する。`O(1)`
- よって、全体では、`O(N+N*1) = O(N)` 程度で処理できた。
## 前提
- `C`問題あたりで，`TLE`になる人は，制約条件を見る癖をつけよう．
- `A`と`B`問題では，基本的に制約条件を見ずにやっても解ける．
- しかし，`C`問題以降では，制約条件を見ないと必ず`TLE`すると思っても良い．
- 詳しい話は私の[352回の記事](https://qiita.com/mattsunkun/items/837444254f03e6105922) の`C`問題の解説に記したので，是非参照してほしい．
```C.py
"""
<方針>
- 全ての連続部分列を作成すると、`O(N^2)` かかり、とても間に合わない。
- なんとか線形時間で処理を組む必要がある。
- まず、`R` に、どの位置で、`^` or `v` になるかを見つける。 `O(N)`
- 次に、`R` を見て、`^` の次に `v` が来る場所を見つける。`O(N)`
- そのとき、`^` の一個前のやつとの距離を `l` とし、 `v` の一個次のやつとの距離を `r` とし、`l*r` を答えに追加する。`O(1)`
- よって、全体では、`O(N+N*1) = O(N)` 程度で処理できた。
"""
# 入力
N = int(input())
P = list(map(int, input().split()))

# ^とvを格納する。
## ^: [1, index]
## v: [-1, index]
R = []

R.append([0, 0]) # 番兵

# ラスター走査
for i in range(1, N-1):
  # ^ の時、
  if(P[i-1] < P[i] > P[i+1]):
    R.append([1, i])
  # v の時、
  if(P[i-1] > P[i] < P[i+1]):
    R.append([-1, i])

R.append([0, N-1]) # 番兵

# 答えを集計する。
ans = 0
for i in range(1, len(R)-1):
  # ^の次vがきてる時、
  if(R[i][0] == 1 and R[i+1][0] == -1):
    # 左の長さ
    l = R[i][1] - R[i-1][1]
    # 右の長さ
    r = R[i+2][1] - R[i+1][1]
    # 答えに追記
    ans += (l*r)

# 出力
print(ans)
```

# D問題
- `H x W` の空間はリストで持てないから、集合で管理する。
- `X` で処理したら、`Y` も更新する。逆も然り。
```D.py
"""
<方針>
- `H x W` の空間はリストで持てないから、集合で管理する。
- `X` で処理したら、`Y` も更新する。逆も然り。
"""
from collections import defaultdict

_, _, N = map(int, input().split())

# X[x][y] -> (x, y) にゴミがある。
X = defaultdict(set)
# Y[y][x] -> (x, y) にゴミがある。
Y = defaultdict(set)

# X, Yの作成
for _ in range(N):
  x, y = map(int, input().split())
  Y[y].add(x)
  X[x].add(y)

# ループ処理
for _ in range(int(input())):
  match list(map(int, input().split())):
    case [1, x]:
      # xにあるゴミを出力
      print(len(X[x]))
      # Yの方のゴミを消す
      for y in X[x]:
        Y[y].discard(x)
      # Xの方のゴミを消す
      X[x] = set()
    # 上と同じ
    case [2, y]:
      print(len(Y[y]))
      for x in Y[y]:
        X[x].discard(y)
      Y[y] = set()
```


# 補足
### 関係するリンク(参考文献など)
- [今回のコンテスト](https://atcoder.jp/contests/abc406)
### 筆者について
- [Atcoderアカウント](https://atcoder.jp/users/mattsunkun)
- *今回も不参加のため，成績なし．*
- [解説で示したA問題の提出](https://atcoder.jp/contests/abc406/submissions/65969154)
- [解説で示したB問題の提出](https://atcoder.jp/contests/abc406/submissions/65969194)
- [解説で示したC問題の提出](https://atcoder.jp/contests/abc406/submissions/65969564)
- [解説で示したD問題の提出](https://atcoder.jp/contests/abc406/submissions/65975653)
### その他
- **間違いを含んでいる可能性があります．**
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
### 最後に一言
- 奇妙な[記事](https://qiita.com/mattsunkun/items/96241a3c39282cbca1f5)があるな...