ABC395をPythonで（A～E）

AtCoder Beginner Contest 395の解答等の速報的まとめ

A問題

全部試す

A

n = int(input())
a = list(map(int, input().split()))
print("Yes" if all(a_i < a_j for a_i, a_j in zip(a, a[1:])) else "No")

B問題

外側からの距離の偶奇で#と.が入れ替わる

B

n = int(input())

for i in range(n):
    ans_i = ""
    for j in range(n):
        k = min(i, j, n - i - 1, n - j - 1)
        if k % 2 == 0:
            ans_i += "#"
        else:
            ans_i += "."
    print(ans_i)

C問題

各数字ごとに
前後の数字の距離の最短を求める

C

n = int(input())
a = list(map(int, input().split()))

d = dict()
INF = 10 ** 7
ans = INF
for i, a_i in enumerate(a):
    if a_i in d:
        ans = min(ans, i - d[a_i] + 1)
    d[a_i] = i

print(ans if ans < INF else -1)

D問題

鳩の巣が数直線上に並んでいるとするとき
鳩の移動は、左から何番目に移動したかを記録する
巣は、$i$番目が左から何番目にあるかとその逆を記録しておいて、入れ替えるときに両方を入れ替える

D

n, q = map(int, input().split())

pigeons = [i for i in range(n)] # 鳩
nests = [i for i in range(n)] # 巣
d = [i for i in range(n)]

for _ in range(q):
    com = list(map(lambda x:int(x) - 1, input().split()))
    if com[0] == 0:
        a, b = com[1:]
        target_nest = d[b]
        pigeons[a] = target_nest
    elif com[0] == 1:
        a, b = com[1:]
        ind_a, ind_b = d[a], d[b]
        nests[ind_a], nests[ind_b] = nests[ind_b], nests[ind_a]
        d[a], d[b] = ind_b, ind_a
    else:
        a = com[1]
        print(nests[pigeons[a]] + 1)

E問題

辺の向きが初期の向きと逆向きをそれぞれ記録し、
各頂点で初期の向きと逆向きで到着した時のコストの最小値をダイクストラで求める

E

from heapq import heappop, heappush

n, m, x = map(int, input().split())
edge = [[] for _ in range(n)]
rev_e = [[] for _ in range(n)]
for _ in range(m):
    u, v = map(lambda x:int(x) - 1, input().split())
    edge[u].append(v)
    rev_e[v].append(u)

INF = float('inf')
cost = [[INF, INF] for _ in range(n)]
cost[0][0] = 0
q = [[0, 0, 0]]
while q:
    c_i, now, is_rev = heappop(q)
    if cost[now][is_rev] < c_i:
        continue

    if cost[now][is_rev ^ 1] > c_i + x:
        heappush(q, [c_i + x, now, is_rev ^ 1])

    if is_rev:
        for to in rev_e[now]:
            if cost[to][is_rev] > c_i + 1:
                cost[to][is_rev] = c_i + 1
                heappush(q, [c_i + 1, to, is_rev])
    else:
        for to in edge[now]:
            if cost[to][is_rev] > c_i + 1:
                cost[to][is_rev] = c_i + 1
                heappush(q, [c_i + 1, to, is_rev])

ans = min(cost[-1])
print(ans if ans < INF else -1)