[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)
補足
関係するリンク(参考文献など)
筆者について
- Atcoderアカウント
- 今回も不参加のため，成績なし．
- 解説で示したA問題の提出
- 解説で示したB問題の提出
- 解説で示したC問題の提出
- 解説で示したD問題の提出
- 解説で示したE問題の提出
その他
- 間違いを含んでいる可能性があります．
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
最後に一言
- 【朗報】大学卒業確定