ABC237解説：本番でACできた問題＋2問（Python）
A - Not Overflow
以上
Pythonですとオーバーフローを考える必要がなく、かつ1 < x < 3といった形で比較ができるので簡潔に記載できます。
N = int(input())
if (-2) ** 31 <= N < 2 ** 31:
print("Yes")
else:
print("No")
B - Matrix Transposition
タイトルのとおり行列の転置を求める問題です。
Pythonにおける行列の転置はlist(zip(MATRIX))と書くことができます。
H, W = list(map(int, input().split()))
A = [tuple(map(int, input().split())) for _ in range(H)]
for i in list(zip(*A)):
print(*i)
numpyのTメソッドで解くこともできます。
import numpy as np
H, W = list(map(int, input().split()))
A = [tuple(map(int, input().split())) for _ in range(H)]
a = np.array(A)
for i in a.T:
print(*i)
C - kasaka
まず右端のaの数だけ左端にaを増やす方法が考えつきますが、これではaba(->aaba)やaaba(->aaaba)のパターンでWAとなります。
そのため両端のaの個数を比較して場合分けすることを考えます。
- 左端のaが右端のaよりも多い場合（
aaba）、どう操作しても回文にはなりえません。 - 左端のaと右端のaが同じ数の場合（
abaやabca）、もともとの文字列の回分判定すればよいです。 - 左端のaが右端のaよりも少ない場合（
abaa）、左端に少ない数だけのaを追加して回文判定をします。
回分判定は文字列を反転させたものがもとの文字列と同じかどうかを判定します。
文字列の反転は[::-1]を使うと簡単です
S = input()
a_left = 0
for s in S:
if s == "a":
a_left += 1
else:
break
a_right = 0
for s in S[::-1]:
if s == "a":
a_right += 1
else:
break
if a_left > a_right: # aabaなど
print("No")
elif a_left == a_right: # abaやabcaなど （下のelse文だけでも対応できます）
if S == S[::-1]:
print("Yes")
else:
print("No")
else:
SS = "".join(["a" * (a_right - a_left), S]) # baやabcaaなど
if SS == SS[::-1]:
print("Yes")
else:
print("No")
D - LR insertion
逆から考えるという方針を思いつけば解ける問題です。
もしくは左と右に分割する方針でも解くことができます。
本番では思いつきませんでしたが、両方とも汎用的な考察手法なので次回は使いたいです。
from collections import deque
N = int(input())
S = input()
ans = deque()
ans.append(N)
for i in range(N - 1, -1, -1):
if S[i] == "L":
ans.append(i)
else:
ans.appendleft(i)
print(*ans)
N = int(input())
S = input()
L = []
R = []
for i, s in enumerate(S):
if s == "L":
R.append(i)
else:
L.append(i)
print(*(L + [N] + R[::-1]))
類題
前と後ろに分割する方針が似ています。
E - Skiing
本番ではBellman-Ford法を使ってTLEでした。
制約が厳しいのでDijkstra法を使いたい気持ちになります。
そこですべての辺のコストをどうにか非負の値にするため考察します。
以下のH0からH3までの標高とスコアの推移を考えます。
右の数式の黒色の箇所が正のスコア、オレンジ色の箇所が負のスコアですが、こちらを展開するとうまく打ち消し合い、最終的には始点H0と終点H3の差分にコストを引いたものになります。
そして末尾のコストのH[1]-H[0]は正の値となります。
もう一例考えてみます。
こちらはH3に標高2のケースを追加したものです。
上と同様に展開すると、最終的には始点H0と終点H4の差分にコストを引いたものになります。
そして末尾のコストの(H[1]-H[0]) + (H[3]-H[2])は正の値となります。
ここで求めたい値を考えると、末尾の正の値のコストを最小化することとなります。
それぞれの辺について辺のコストをH[u]-H[v] (H[u]>H[v]のとき)と持っておきます。
逆方向は計算に寄与しないので0で補完します。
このような操作をすることで、各辺のコストが非負のグラフが得られます。
あとは得られたグラフについてDijkstra法でH[0]を始点とする最短経路問題を解きます。
得られた答えをdist、終点をH[i]とおくと、H[0] - H[i] - dist[i]の最大値が求める答えとなります。
import heapq
INF = float("inf")
N, M = list(map(int, input().split()))
H = list(map(int, input().split()))
G = [[] for _ in range(N)]
for _ in range(M):
u, v = map(int, input().split())
u, v = u - 1, v - 1
if H[u] > H[v]:
G[v].append([u, (H[u] - H[v])])
G[u].append([v, 0])
else:
G[v].append([u, 0])
G[u].append([v, (H[v] - H[u])])
def dijkstra(s):
dist = [INF] * N
dist[s] = 0
seen = [0] * N
h = [(0, s)]
while h:
_, u = heapq.heappop(h)
seen[u] = 1
for v, cost in G[u]:
if seen[v] == 0 and dist[v] > dist[u] + cost:
dist[v] = dist[u] + cost
heapq.heappush(h, (dist[v], v))
return dist
dist = dijkstra(0)
ans = 0
for i in range(N):
ans = max(ans, H[0] - H[i] - dist[i])
print(ans)
Discussion