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

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

# A問題
- 左側`left`が全部`1`
- 真ん中`mid`が`/`
- 右側`right`が全部`2`
- `//`は切り捨てに注意．
```A.py
"""
<方針>
- 左側`left`が全部`1`
- 真ん中`mid`が`/`
- 右側`right`が全部`2`
- `//`は切り捨てに注意．
"""
# 入力
N = int(input())
S = input()

left = S[:N//2] # 左側
mid = S[N//2] # 真ん中
right = S[N//2 + 1:] # 右側

# 全ての条件が一致する時
if(
  left == "1"*(N//2) and 
  mid == "/" and
  right == "2"*(N//2)
  ):
  # Yes
  print("Yes")
else:
  # No
  print("No")
```

# B問題
- 文字の長さが奇数ならすぐ `No` を出力する．
- 文字を二つずつみて，同じかどうかをみる．既にみたことある英小文字かどうかも確認する．
```B.py
"""
<方針>
- 文字の長さが奇数ならすぐ `No` を出力する．
- 文字を二つずつみて，同じかどうかをみる．既にみたことある英小文字かどうかも確認する．
"""
# 入力
S = input()

# 入力文字列が奇数の時
if(len(S)%2==1):
  # Noとして，プログラムを終了する．
  print("No")
  exit()

# 既にみたことあるかどうかを管理するリスト
look = [False]*26

# 2文字ずつ見る
for i in range(len(S)//2):
  # 連続する2文字が等しい時，
  if(S[i*2]==S[i*2 + 1]):
    # リスト上での現在の文字のindex
    ind = ord(S[i*2]) - ord("a")
    # 既にみたことある文字なら
    if(look[ind]):
      # Noとして，プログラムを終了する．
      print("No")
      exit()
    # 既にみたことあるものとして登録する．
    look[ind] = True
  # 連続する2文字が等しく無い時，
  else:
    # Noとして，プログラムを終了する．
    print("No")
    exit()

# Yesを出力
print("Yes")
```

# C問題
## 方針
- 番兵として右側に `1` を置いておく．
- 左側から見る．
- `1` がどれだけ連続するかを記録する．
- `/` が出てきたら `2` の数を数える．
- 条件分岐を頑張って実装する．ソースコードは `†WYSIWYG†` です．
- P.S.
    - 左から順番に見ていくだけなので，計算量は `O(N)` です．
## 前提
- `C`問題あたりで，`TLE`になる人は，制約条件を見る癖をつけよう．
- `A`と`B`問題では，基本的に制約条件を見ずにやっても解ける．
- しかし，`C`問題以降では，制約条件を見ないと必ず`TLE`すると思っても良い．
- 詳しい話は私の[352回の記事](https://qiita.com/mattsunkun/items/837444254f03e6105922) の`C`問題の解説に記したので，是非参照してほしい．
```C.py
"""
<方針>
- 番兵として右側に `1` を置いておく．
- 左側から見る．
- `1` がどれだけ連続するかを記録する．
- `/` が出てきたら `2` の数を数える．
- 条件分岐を頑張って実装する．ソースコードは `†WYSIWYG†` です．
"""
# 入力
N = int(input())
S = list(input())

# 番兵
S.append("1")

ans = -1 # 答え
look = 1 # 現在何をカウントアップしているか．最初は1
one = 0 # 1の現在のカウント数
two = 0 # 2の現在のカウント数
# 文字を順番に見ていく．
for s in S:
  match look:
    case 1:
      match s:
        case "1":
          one += 1
          two = 0
          look = 1
        case "/":
          two = 0
          look = 2
        case "2":
          one = 0
          two = 0
          look = 1
    case 2:
      match s:
        case "1":
          ans = max(ans, min(one, two)*2 + 1) # 答えを更新
          one = 1
          two = 0
          look = 1
        case "/":
          ans = max(ans, min(one, two)*2 + 1) # 答えを更新
          one = 0
          two = 0
          look = 1
        case "2":
          two += 1
          look = 2
# 出力
print(ans)
```

# D問題
- 尺取法で左から順番に見ていく．
- 常に長さ `l` を意識して処理する．
- そのまま `A` を二つずつ調べるか，最初の一個を飛ばして調べるかの2通りやる必要がある．
```D.py
"""
<方針>
- 尺取法で左から順番に見ていく．
- 常に長さ `l` を意識して処理する．
- そのまま `A` を二つずつ調べるか，最初の一個を飛ばして調べるかの2通りやる必要がある．
"""
N = int(input())
A = list(map(int, input().split()))

def check(A):
  # 特定の数値が出てきた時のindexを管理
  di = {}
  # 現在の長さ(2個で1つの長さ．ansでは2倍すれば良い．)
  l = 0
  # 答え
  ans = 0
  # セットずつ見ていく
  for i in range(len(A)//2):
    # セットが合った時
    if A[2*i] == A[2*i + 1]:
      a = A[2*i]
      # 既にその数値が組み込まれている時，
      if a in di:
        # その長さを組み込んだ長さ or 同一の文字を削除した長さ
        l = min(l + 1, i - di[a])
      # まだ組み込まれてない時，
      else:
        # 組み込んだ長さ
        l += 1
      di[a] = i
    # セットが合わなかった時
    else:
      # 長さをリセット
      l = 0
      # indexもリセット
      di = {}
    # 答えを更新
    ans = max(ans, 2*l)
  return ans
# 部分列全体と部分列 A[1:] の両方を調べる
ans = max(check(A), check(A[1:]))
print(ans)
```

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