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

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

# A問題
- `S` を `int` で受け取る。
- `int` で大小関係を考える。
```A.py
"""
<方針>
- `S` を `int` で受け取る。
- `int` で大小関係を考える。
"""
# 入力
S = int(input())

# 200~299のとき
if(200 <= S <= 299):
  print("Success")
# それ以外のとき
else:
  print("Failure")
```

# B問題
- ログイン状態を保持する `login` 変数を利用する。
- `match` 文で切り替えて処理する。
```B.py
"""
<方針>
- ログイン状態を保持する `login` 変数を利用する。
- `match` 文で切り替えて処理する。
"""
# 入力
N = int(input())

login = False # ログイン状態を保持。初期はログインしていない。
ans = 0 # 認証エラーした回数。

for _ in range(N):
  # 入力分岐
  match input():
    # ログインする。
    case "login":
      login = True
    # ログアウトする。
    case "logout":
      login = False
    # プライベートページにアクセスする。
    case "private":
      # ログインしてなければ、
      if(not login):
        # 認証エラー
        ans += 1

# 出力
print(ans)
```

# C問題
## 方針
- 毎回 `K` 個前のやつを全て足していては、`N` 回処理できず、`O(NK)` かかってしまう。
- `K` 個前全てを足さずに、一個前がちょっと手前の部分を含んでいることを考える。
- 一個前と一個前を足すと（つまり、一個前の２倍）、`K+1` 個前を多く含んでいるだけになるので、それを減らしてあげれば良い。
- ただし、`N==K` のときは最初に `K` 個前を全て足す状態なので、純粋に `1*K == K` とすれば良い。
- よって、`O(N)` として処理ができる。
## 前提
- `C`問題あたりで，`TLE`になる人は，制約条件を見る癖をつけよう．
- `A`と`B`問題では，基本的に制約条件を見ずにやっても解ける．
- しかし，`C`問題以降では，制約条件を見ないと必ず`TLE`すると思っても良い．
- 詳しい話は私の[352回の記事](https://qiita.com/mattsunkun/items/837444254f03e6105922) の`C`問題の解説に記したので，是非参照してほしい．
```C.py
"""
<方針>
- 毎回 `K` 個前のやつを全て足していては、`N` 回処理できず、`O(NK)` かかってしまう。
- `K` 個前全てを足さずに、一個前がちょっと手前の部分を含んでいることを考える。
- 一個前と一個前を足すと（つまり、一個前の２倍）、`K+1` 個前を多く含んでいるだけになるので、それを減らしてあげれば良い。
- ただし、`N==K` のときは最初に `K` 個前を全て足す状態なので、純粋に `1*K == K` とすれば良い。
- よって、`O(N)` として処理ができる。
"""
# 入力
N, K = map(int, input().split())

# Aの値。
A = [None]*(N+1)

# 割る値
mod = 10**9

# 前から順番に計算する。
for i in range(N+1):
  if(i<K):
    # 普通に1
    A[i] = 1
  elif(i == K):
    # 前K個を足す。全て1なので、Kになる。
    A[i] = 1*K
  else:
    # 一個前の２倍からK+1個前を引けば良い。
    A[i] = (2*A[i-1] - A[i-(K+1)])%mod

# 出力
print(A[N])
```

# D問題
- 大前提として、全てのパターンを列挙するにはあらゆるものがとても足りない。
- まず、`o` の隣の `?` は必ず `.` となる。
- 次に、既に `o` が足りていれば、`?` は全て `.` とする。
- 最後に、`o` を最大敷き詰めれる時を考えて、奇数のところは `oxoxoxo` のように埋める。
```D.py
"""
<方針>
- 大前提として、全てのパターンを列挙するにはあらゆるものがとても足りない。
- まず、`o` の隣の `?` は必ず `.` となる。
- 次に、既に `o` が足りていれば、`?` は全て `.` とする。
- 最後に、`o` を最大敷き詰めれる時を考えて、奇数のところは `oxoxoxo` のように埋める。
"""
N, K = map(int, input().split())
S = list(input())
T = ["?"]*N

# 一旦自明なところを転写する。
for i in range(N):
  # "o"の左右は必ず"."になる
  if(S[i] == "o"):
    for dx in [-1, 1]:
      I = i + dx
      if(0<=I<N):
        T[I] = "."
  # "o" or "." はそのまま転写
  if(S[i] != "?"):
    T[i] = S[i]

# 既に"o"が十分足りている時、
if(T.count("o") == K):
  for i in range(N):
    if(T[i] == "?"):
      T[i] = "."

o_vague = 0 # "?"が偶数回連続しているところに打ち込める"o"の最大数
o_idx = [] # "?"が奇数回連続しているところに最大"o"を打ち込んだ時の位置
x_idx = [] # "?"が奇数回連続しているところに最大"o"を打ち込んだ時の"."の位置
q_start = None # qが連続し始めた位置
for i in range(N+1):
  if(
    # 番兵
    i < N and 
    # "?" のとき
    T[i] == "?"):
    if(q_start is None):
      q_start = i
  else:
    if(q_start is not None):
      # 奇数回連続
      if((i - q_start)%2 == 1):
        # 位置登録
        for j in range(q_start, min(i+1, N)):
          # 奇数番目
          if(j - q_start)%2 == 0:
            o_idx.append(j)
          # 偶数番目
          else:
            x_idx.append(j)
      # 偶数回連続
      else:
        o_vague += (i - q_start)//2
    q_start = None

# oを最大打ち込んでちょうどの時
if(len(o_idx) + T.count("o") + o_vague == K):
  # 奇数の場所は確定させる
  for i in o_idx:
    T[i] = "o"
  for i in x_idx:
    T[i] = "."

# 出力
print("".join(T))
```


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