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

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

# A問題
- 全ての `A` の間の大小を見て、`A[i] >= A[i+1]` となっている部分があれば `No` となる。
```A.py
"""
<方針>
- 全ての `A` の間の大小を見て、`A[i] >= A[i+1]` となっている部分があれば `No` となる。
"""
# 入力
N = int(input())
A = list(map(int, input().split()))

# 間の大小を考える。
for i in range(N-1):
  # 条件
  if(A[i] >= A[i+1]):
    # No を出力
    print("No")
    # プログラムを終了
    exit()

# 狭義単調
print("Yes")
```

# B問題
- 外側から正方形を塗り替えていく。
```B.py
"""
<方針>
- 外側から正方形を塗り替えていく。
"""
# 入力
N = int(input())

# 答え（初期値は?にする）
ans = [["?"]*N for _ in range(N)]

# 外側の位置
for h in range(N//2 + 1):
  # 塗り替え
  for i in range(h, N-h):
    for j in range(h, N-h):
      # 偶奇で塗る文字を変える。
      if(h%2==0):
        ans[i][j] = "#"
      else:
        ans[i][j] = "."

# 出力
for i in range(N):
  print("".join(ans[i]))
```

# C問題
## 方針
- 全ての部分文字列を選ぶだけでも `O(N^2)` かかるので、`TLE` する。
- なんとか線形時間（`O(N)`）程度にしたいので、左から順番に見るだけで終わらせたい。
- それぞれの `A` の数値が前回どの位置にいたかを保存するリスト `A_before_index` を最初に作成すればいけそう。
- `A` の長さと、`A` の想定される最大値 `max(A)` がボトルネックなので、`O(N+max(A))` になりそう。
## 前提
- `C`問題あたりで，`TLE`になる人は，制約条件を見る癖をつけよう．
- `A`と`B`問題では，基本的に制約条件を見ずにやっても解ける．
- しかし，`C`問題以降では，制約条件を見ないと必ず`TLE`すると思っても良い．
- 詳しい話は私の[352回の記事](https://qiita.com/mattsunkun/items/837444254f03e6105922) の`C`問題の解説に記したので，是非参照してほしい．
```C.py
"""
<方針>
- 全ての部分文字列を選ぶだけでも `O(N^2)` かかるので、`TLE` する。
- なんとか線形時間（`O(N)`）程度にしたいので、左から順番に見るだけで終わらせたい。
- それぞれの `A` の数値が前回どの位置にいたかを保存するリスト `A_before_index` を最初に作成すればいけそう。
- `A` の長さと、`A` の想定される最大値 `max(A)` がボトルネックなので、`O(N+max(A))` になりそう。
"""
# 入力
N = int(input())
A = list(map(int, input().split()))

# 無限
INF = float("inf")

# 初期値は無限遠とする。
A_before_index = [-INF]*(max(A)+1)

# 最小の長さ。初期値は無限とする。
ans = INF

# 左から見ていく。
for i, a in enumerate(A):
  # 前回との距離
  ans = min(ans, i - A_before_index[a] + 1)
  # 位置の更新
  A_before_index[a] = i

# 出力
if(ans == INF):
  # 無限遠としか距離を測れなかった時→同じ数値がAになかった時
  print(-1)
else:
  # 距離
  print(ans)
```

# D問題
- 巣（`B`ox）と巣の番号（`L`abel）を分けて管理することで、鳩（`P`igeon）の巣の入れ替えを素早くする。
```D.py
"""
<方針>
- 巣（`B`ox）と巣の番号（`L`abel）を分けて管理することで、鳩（`P`igeon）の巣の入れ替えを素早くする。
"""
# 入力
N, Q = map(int, input().split())

# 管理するリスト３種類
B2L = list(range(N)) # Box[i] = Label
L2B = list(range(N)) # Label[i] = Box
P2B = list(range(N)) # Pigeon[i] = Box

for _ in range(Q):
  match list(map(int, input().split())):
    # 種類１
    case [1, a, b]:
      a -= 1
      b -= 1
      # 鳩の移動
      P2B[a] = L2B[b]
    # 種類２
    case [2, a, b]:
      a -= 1
      b -= 1
      # Labelの張り替え
      L2B[a], L2B[b] = L2B[b], L2B[a]
      B2L[L2B[a]], B2L[L2B[b]] = B2L[L2B[b]], B2L[L2B[a]]
    # 種類３
    case [3, a]:
      a -= 1
      # 鳩が住んでいる番号
      print(B2L[P2B[a]] + 1)
```

# E問題
- `dijkstra` で解く。
- グラフ全体像
  - 表のグラフと裏のグラフを作成する。
  - 表のグラフはそのまま有向辺を生やし、裏のグラフは辺の向きを逆にする。
  - 表のグラフと裏のグラフ同士は `X` コストを払うことで移動できるものとする。
```E.py
"""
<方針>
- `dijkstra` で解く。
- グラフ全体像
  - 表のグラフと裏のグラフを作成する。
  - 表のグラフはそのまま有向辺を生やし、裏のグラフは辺の向きを逆にする。
  - 表のグラフと裏のグラフ同士は `X` コストを払うことで移動できるものとする。
"""
import heapq
N, M, X = map(int, input().split())

# グラフ
E = [[] for _ in range(2*N)]

for _ in range(M):
  u, v = map(int, input().split())
  u -= 1
  v -= 1
  # 表のグラフ
  E[u].append([v, 1])
  # 裏のグラフ
  E[v+N].append([u+N, 1])

# 表裏の行き来
for i in range(N):
  # 表→裏
  E[i].append([i+N, X])
  # 裏→表
  E[i+N].append([i, X])

# dijkstra
V = [float("inf")]*(2*N)
# 開始位置は表の0
q = [[0, 0]]
V[0] = 0

while q:
  cost, x = heapq.heappop(q)
  if(cost>V[x]):
    continue
  
  for y, cost in E[x]:
    if(V[x] + cost < V[y]):
      V[y] = V[x] + cost
      heapq.heappush(q, [V[y], y])

# 表or裏のN番目にたどりつければ良い。
ans = min(V[N - 1], V[2*N - 1])

# 出力
print(ans)
```

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