Atcoder ABC237 振り返り

　期末レポートやらが重なって最近できていなかったので久しぶりのABC．今回も当日は参加出来なかったのでバーチャル参加しました．

A - Not Overflow【AC】

　問題文で言われたとおりのことをコードに翻訳する．

n = int(input())
if -2**31 <= n < 2**31:
    print("Yes")
else:
    print("No")

B - Matrix Transposition【AC】

　numpyは.Tとすることで転置ができる．join関数がndarrayでも使えるのは初めて知った

import numpy as np
h, w = map(int, input().split())

lis = []
for _ in range(h):
    lis.append([i for i in input().split()])
lis = np.array(lis).T
for i in lis:
    print(" ".join(i))

C - kasaka【AC】

　少なくともSが回文になる為には，先頭のaの数と末尾のaの数が一致してないといけない．先頭のaの数と末尾のaの数を数え，その差の個数だけ先頭にaを追加する．（先頭にしかaを加えられないので，先頭のaの数 > 末尾のaの数 となった時点で回文にはなり得ない）
　文字の反転はスライスを用いて，a[::-1]とすると出来る．

S = input()
i = 0
maea = 0

while i <= len(S)-1:
    if S[i] != "a":
        break
    maea += 1
    i += 1

i = 1
usiroa = 0
while i <= len(S):
    if S[-i] != "a":
        break
    usiroa += 1
    i += 1

ok = False
S = S[::-1] + "a"*max(0, usiroa-maea)

if S==S[::-1]:
    print("Yes")
else:
    print("No")

D - LR insertion【AC】

　言われたとおりに順番にやると1,0→1,2,0みたいな挿入でめっちゃ時間かかりそう．
→逆から順番にやれば，前から足すと後ろから足すの処理だけで挿入とかやらずにできるな．
→でも前から足すってのも時間掛かったような．
→キュー構造を使えばいい．

from collections import deque

N = int(input())
S = input()
d = deque([str(N)])

for i in range(N-1, -1, -1):
    if S[i] == "L":
        d.append(str(i))
    else:
        d.appendleft(str(i))
print(" ".join(d))

E - Skiing【解説AC】

　なんとなくダイクストラ法を使えば解けそうというのはふんわりと分かっていた．でもダイクストラ法は負辺があるとき使えないしベルマンフォード法は間に合わないし……で解説を見た．ユーザー解説の方が分かりやすかったが，なんだが狐につままれたような感覚で納得したけど……？といった感触．
　ダイクストラ法での解法だったのでとりあえず実装してAC

import heapq

N, M = map(int, input().split())
H = [int(i) for i in input().split()]

costs = [[] for _ in range(N)]

for _ in range(M):
    u, v = map(int, input().split())
    u, v = u-1, v-1
    costs[u].append((v, abs(H[u] - H[v])))
    costs[v].append((u, abs(H[u] - H[v])))


dist = [10**10] * N
dist[0] = 0
que = [(0, 0)] #(コスト, ノード)
visited = [False] * N

while que:
    q = heapq.heappop(que)[1]
    visited[q] = True
    for node, cost in costs[q]:
         if not visited[node] and dist[q] + cost < dist[node]:
            dist[node] = dist[q] + cost
            heapq.heappush(que, (dist[node], node))

ans = 0
for node, cost in enumerate(dist):
    if cost == 10**10:
        continue
    ans = max(ans, -0.5*cost - (3/2)*(H[node] - H[0]))
print(int(ans))