[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回の記事の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問題

巣（Box）と巣の番号（Label）を分けて管理することで、鳩（Pigeon）の巣の入れ替えを素早くする。

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)

補足

関係するリンク(参考文献など)

今回のコンテスト

筆者について

その他

間違いを含んでいる可能性があります．
方針と言いつつ，方針ではない感想などを書いている可能性があります．
A問題から解説がだんだん省略されます．
コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．

最後に一言

【朗報】大学卒業確定