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

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

# A問題
- `replace()` を使って， `.` を削除する．

```A.py
"""
<方針>
- `replace()` を使って， `.` を削除する．
"""
# 入力
S = input()
# . を削除
T = S.replace(".", "")
# 出力
print(T)

```

# B問題
- `A_i` は `20` 個程度しか作れないので，なるべく大きい `A_i` を採用する必要がある．
- `M` を `3` で `divmod()` をとっていけば，何とかなりそう．
- 制約的には， `10**5 < 3**11` だから， `range(12)` のループでいけるな．
- 何言ってるかわからんかもしれんが，まあみてなって．
```B.py
"""
<方針>
- `A_i` は `20` 個程度しか作れないので，なるべく大きい `A_i` を採用する必要がある．
- `M` を `3` で `divmod()` をとっていけば，何とかなりそう．
- 制約的には， `10**5 < 3**11` だから， `range(12)` のループでいけるな．
- 何言ってるかわからんかもしれんが，まあみてなって．
"""
# 入力
M = int(input())

# Aのリスト
A = []
# Mを3で割っていく
for i in range(12):
  
  # 3でわる
  M, mo = divmod(M, 3)
  
  # あまりの数だけ，現在のイテレートをappendする．
  for _ in range(mo):
    A.append(i)
    
# 出力
print(len(A))
print(*A)

# 検算
# print(sum([pow(3, a) for a in A]))
```

# C問題
## 方針
- 毎回 `ABC` の数を全て数えると， `O(NQ)` となって， `TLE` してしまう．
- クエリの数だけ操作すること(`O(Q)`)は変えられないので，何とか，一回の操作でやることを減らしたい．
- 文字を入れ替えた時に， `ABC` に影響しそうなのは，文字を入れ替えたところを利用するところにしか影響しない．
- 該当箇所だけを検査すれば，操作は線形時間(`O(1)`)に抑えることができる．
- よって，計算時間は `O(Q)` にすることができた．
- 今回は `cntABC(start, end)` という関数を作って，コードを簡潔にしてみた．
## 前提
- `C`問題あたりで，`TLE`になる人は，制約条件を見る癖をつけよう．
- `A`と`B`問題では，基本的に制約条件を見ずにやっても解ける．
- しかし，`C`問題以降では，制約条件を見ないと必ず`TLE`すると思っても良い．
- 詳しい話は私の[352回の記事](https://qiita.com/mattsunkun/items/837444254f03e6105922) の`C`問題の解説に記したので，是非参照してほしい．
```C.py
"""
<方針>
- 毎回 `ABC` の数を全て数えると， `O(NQ)` となって， `TLE` してしまう．
- クエリの数だけ操作すること(`O(Q)`)は変えられないので，何とか，一回の操作でやることを減らしたい．
- 文字を入れ替えた時に， `ABC` に影響しそうなのは，文字を入れ替えたところを利用するところにしか影響しない．
- 該当箇所だけを検査すれば，操作は線形時間(`O(1)`)に抑えることができる．
- よって，計算時間は `O(Q)` にすることができた．
- 今回は `cntABC(start, end)` という関数を作って，コードを簡潔にしてみた．
"""
# 入力
N, Q = map(int, input().split())
S = list(input()) # mutableなlistで扱う

# ABCの個数を数える関数．数えたい位置を渡す．数える位置は，そこのindexを「A」の位置と仮定している．
def cntABC(start, end):
  # 個数
  ret = 0
  # 有効範囲のみを数えるようにする．
  for i in range(max(0, start), min(end+1, N-2)):
    # ABCのとき，
    if(
      S[i+0] == "A" and
      S[i+1] == "B" and
      S[i+2] == "C"
      ):
        # カウント
        ret += 1
        
  return ret

# 現在のカウント数
ans = cntABC(0, N)

# クエリの処理
for _ in range(Q):
  # 入力
  x, c = input().split()
  # 0-indexedのintに変更
  x = int(x) - 1
  
  # cへの変更によって影響がある場所のカウントを行う．
  past = cntABC(x-2, x)
  
  # cへ変更
  S[x] = c
  
  # cへの変更によって影響がある場所のカウントを行う．
  will = cntABC(x-2, x)
  
  # 差分を更新
  ans += (will - past)
  
  # 出力
  print(ans)
```

# D問題
- 右から順番に見ていく．
- ビルの高さを超える一番右のやつに注目すれば，計算時間が抑えられそう．
```D.py
"""
<方針>
- 右から順番に見ていく．
- ビルの高さを超える一番右のやつに注目すれば，計算時間が抑えられそう．
"""
N = int(input())
H = list(map(int, input().split()))

ans = [0]
stack = []
for i in reversed(range(N - 1)):
  while stack and H[stack[-1]] < H[i + 1]:
      stack.pop()
  stack.append(i + 1)
  ans.append(len(stack))

ans.reverse()
print(*ans)
```


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