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

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

# A問題
- `3` つ連続している部分をずらしながら全て見て、全て同じかどうかを判定する。
```A.py
"""
<方針>
- `3` つ連続している部分をずらしながら全て見て、全て同じかどうかを判定する。
"""
# 入力
N = int(input())
A = list(map(int, input().split()))

# 存在判定
exist = False
# 順番にみる
for i in range(N-2):
  # ３箇所全て同じ値かどうか
  if(A[i] == A[i+1] == A[i+2]):
    # 存在判定を変える。
    exist = True

# 出力
if(exist):
  print("Yes")
else:
  print("No")
```

# B問題
- `list` を山に見立てて、最初は `0` を `100` 要素持たせて初期化する。
- `.append()` で山に追加し、 `.pop()` で山から取り出す。
```B.py
"""
<方針>
- `list` を山に見立てて、最初は `0` を `100` 要素持たせて初期化する。
- `.append()` で山に追加し、 `.pop()` で山から取り出す。
"""
# 山
cards = [0]*100

# クエリ処理
for _ in range(int(input())):
  match list(map(int, input().split())):
    # 追加
    case [1, x]:
      cards.append(x)
    # 取り出し
    case [2]:
      print(cards.pop())

```

# C問題
## 方針
- `B` と `W` を大きい順から並べた方が効率が良さそう。
- しかし、そのまま組み合わせをフルで考えると `O(MN)` で `TLE` してしまう。
- 何とか最大値を求める段階では線形時間程度に抑えたい。
  - まず、`B` は正の値であればなんぼあっても良いので、正の値を全て拾う。
  - 次に、`W` は正の値であったとしても、選んだ `B` の個数以下であることが求められ、個数が超えてしまうならば、 `B[b] + W[w] > 0` であることが要求される。
- 全体の計算量はソートがネックになるので、`O(MlogM + NlogN)`
## 前提
- `C`問題あたりで，`TLE`になる人は，制約条件を見る癖をつけよう．
- `A`と`B`問題では，基本的に制約条件を見ずにやっても解ける．
- しかし，`C`問題以降では，制約条件を見ないと必ず`TLE`すると思っても良い．
- 詳しい話は私の[352回の記事](https://qiita.com/mattsunkun/items/837444254f03e6105922) の`C`問題の解説に記したので，是非参照してほしい．
```C.py
"""
<方針>
- `B` と `W` を大きい順から並べた方が効率が良さそう。
- しかし、そのまま組み合わせをフルで考えると `O(MN)` で `TLE` してしまう。
- 何とか最大値を求める段階では線形時間程度に抑えたい。
  - まず、`B` は正の値であればなんぼあっても良いので、正の値を全て拾う。
  - 次に、`W` は正の値であったとしても、選んだ `B` の個数以下であることが求められ、個数が超えてしまうならば、 `B[b] + W[w] > 0` であることが要求される。
- 全体の計算量はソートがネックになるので、`O(MlogM + NlogN)`
"""
# 入力
N, M = map(int, input().split())
B = list(map(int, input().split())) 
W = list(map(int, input().split()))

# 番兵
B.append(-float("inf"))
N = len(B)

# 大きい順からソート
B.sort(reverse=True)
W.sort(reverse=True)

# 答え
ans = 0

# Bの正の値の境界を拾う
for b in range(N):
  if(B[b] < 0):
    break
  else:
    ans += B[b]

# Wを大きい順から見ていく
for w in range(M):
  # Wが負の値であれば、答えに加える必要がない。
  if(W[w] < 0):
    break
  # Wが正の値であれば、
  else:
    # Bの個数に勝らない範囲であれば、
    if(b > w):
      # 加える
      ans += W[w]
    # Bの個数をオーバーするならば、
    else:
      # B[b] + W[w]が正であることが要求される。
      if(B[b] + W[w] > 0):
        # 正の値を加える
        ans += B[b] + W[w]
        # Bの個数を増やす
        b += 1
        # Bを全て加え切ったら終了
        if(b == N):
          break
      # 負の値であれば終了
      else:
        break

# 終了
print(ans)
```

# D問題
- `N` が小さいので、計算量の問題ではなく、実装力が試されそう。
- パスを全列挙すれば良さそう。
```D.py
"""
<方針>
- `N` が小さいので、計算量の問題ではなく、実装力が試されそう。
- パスを全列挙すれば良さそう。
"""
# ライブラリ
from collections import deque

# 入力
N, M = map(int, input().split())
E = [[] for _ in range(N)]
for _ in range(M):
  u, v, w = map(int, input().split())
  u -= 1
  v -= 1
  E[u].append([v, w])
  E[v].append([u, w])

# 非再帰DFS
q = deque()
# 最初の頂点から始める。
q.append([0, 0, [False]*N])
# 答え
ans = float("inf")
while q:
  # 頂点, 総XOR, 訪れた頂点
  u, xor, visited = q.pop() # DFS
  
  # 自分を訪れた頂点に登録する。
  visited[u] = True
  
  # 終了状態になれば、答えを更新する。
  if (u == N - 1):
    ans = min(ans, xor)
  
  # 次のパスを見る
  for v, w in E[u]:
    # 訪れた頂点でなければ、
    if not visited[v]:
      # 次の頂点を追加する。
      q.append([v, xor^w, visited[:]])

# 出力
print(ans)
```
# 補足
### 関係するリンク(参考文献など)
- [今回のコンテスト](https://atcoder.jp/contests/abc396)
### 筆者について
- [Atcoderアカウント](https://atcoder.jp/users/mattsunkun)
- *今回も不参加のため，成績なし．*
- [解説で示したA問題の提出](https://atcoder.jp/contests/abc396/submissions/63628236)
- [解説で示したB問題の提出](https://atcoder.jp/contests/abc396/submissions/63628414)
- [解説で示したC問題の提出](https://atcoder.jp/contests/abc396/submissions/63643092)
- [解説で示したD問題の提出](https://atcoder.jp/contests/abc396/submissions/63643149)

### その他
- **間違いを含んでいる可能性があります．**
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
### 最後に一言
- いつまで記事を書き続けようか。