ABC348のA~E問題をpythonで解説していきます。今回のC問題は平和でしたね(・∀・)
A - Penalty Kick
問題
高橋君はサッカーの試合で $N$ 回ペナルティキックを蹴ります。
高橋君は $i$ 回目のペナルティキックでは、$i$ が $3$ の倍数の場合は失敗し、それ以外の場合は成功します。
高橋君がペナルティキックを蹴ったときの結果を出力してください。
考察
問題文の通り、3の倍数回目のペナルティキックではx、それ以外はoとすればよい。
コード
N = int(input())
ans = []
for i in range(1, N + 1):
if i % 3 == 0: # 3の倍数回目ならば失敗
ans.append("x")
else:
ans.append("o")
print("".join(ans))
B - Farthest Point
問題
$xy$ 平面上に $1$ から $N$ までの番号が付いた $N$ 個の点があります。点 $i$ は座標 $(X_i, Y_i)$ にあり、相異なる $2$ 点の座標は異なります。
各点について、その点からの距離が最大である点を求めてその点の番号を出力してください。 ただし、距離が最大である点が複数ある場合はその中で最も番号が小さい点の番号を出力してください。
ここで、距離はユークリッド距離、すなわち $(x_1,y_1)$ と $(x_2,y_2)$ に対し、この $2$ 点間の距離が $\sqrt{(x_1-x_2)^{2}+(y_1-y_2)^{2}}$ であるものとして定められています。
考察
各点について、ユークリッド距離が最大である点を求める、もし複数あるならば、最も番号が小さい点を選ぶ、ということなので、各点において、番号が小さい順に点を見ていき、距離の最大値が更新されたらそれをansとすればよい。ここで、ユークリッド距離の大小の比較において、平方根をとっても取らなくても結果は変わらないため、今回は誤差を嫌って平方根をとらないことにした。
コード
N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]
INF = float("inf")
for i in range(N):
max_dist = -INF
xi, yi = XY[i]
for j in range(N):
xj, yj = XY[j]
dist = (xi - xj) ** 2 + (yi - yj) ** 2 # 平方根をとらない
if max_dist < dist:
ans = j + 1
max_dist = dist
print(ans)
C - Colorful Beans
問題
$N$ 種類のビーンズが $1$ 粒ずつあります。 $i$ 種類目のビーンズはおいしさが $A_i$ で色が $C_i$ です。ビーンズは混ぜられており、色でしか区別することができません。
あなたはビーンズの色を $1$ つ選び、その色のビーンズをどれか $1$ 粒食べます。ビーンズの色をうまく選ぶことで、食べる可能性のあるビーンズのおいしさの最小値を最大化してください。
考察
辞書を使って、各色のビーンズの美味しさの最小値を記録、その後それらの最大値を出力する。今回はdefaultdict用い、初期値を無限大とした。
コード
from collections import defaultdict
N = int(input())
INF = float("inf")
beans = defaultdict(lambda: INF) # 初期値無限大
for _ in range(N):
a, c = map(int, input().split())
beans[c] = min(beans[c], a) # 色ごとに最小値を更新
print(max(beans.values()))
D - Medicines on Grid
問題
$H$ 行 $W$ 列のグリッドがあります。上から $i$ 行目、左から $j$ 列目のマス目を $(i, j)$ と表します。各マスの状態は文字 $A_{i,j}$ で表され、意味は以下の通りです。
-
.: 空きマス。 -
#: 障害物。 -
S: 空きマスかつスタート地点。 -
T: 空きマスかつゴール地点。
高橋君は、今いるマスから上下左右に隣り合う空きマスへ、エネルギーを $1$ 消費して移動することができます。ただし、エネルギーが $0$ の状態で移動することはできず、またグリッドの外へ移動することはできません。
グリッドには合計で $N$ 個の薬があります。$i$ 番目の薬は空きマス $(R_i, C_i)$ にあり、使うとエネルギーを $E_i$ にすることができます。必ずしもエネルギーが増えるとは限らないことに注意してください。高橋君は自分のいるマスにある薬を使うことができます。使った薬はなくなります。
高橋君ははじめエネルギー $0$ の状態でスタート地点にいて、ゴール地点まで移動したいです。これが可能かどうか判定してください。
考察
今回は薬を取る度に全マス更新し直しても$O(NHW)$で間に合うため、単純なBFSでも解けるが、後学のために優先度付きキューを用いた方法で実装する。これは、最も残りエネルギーが高いマスから更新を進めていくものであり、適当にマスを選んで更新していくよりも、更新回数を減らすことが期待できる。(解説によると、実際に計算量が減っている証明はできていないそうだが、テストケースではこちらの方が高速で動作する)
あとは、ゴールマスにたどり着ければYes、そうでなければNoと出力すればよい。
コード
import heapq
dxdy = ((0, 1), (0, -1), (1, 0), (-1, 0)) # 上下右左
H, W = map(int, input().split())
MAP = [list(input()) for _ in range(H)]
energy = [[0] * W for _ in range(H)]
N = int(input())
for _ in range(N):
r, c, e = map(int, input().split())
r -= 1
c -= 1
energy[r][c] = e
for i in range(H):
for j in range(W):
if MAP[i][j] == "S":
sy, sx = i, j
elif MAP[i][j] == "T":
gy, gx = i, j
dist = [[-1] * W for _ in range(H)]
pq = []
heapq.heappush(pq, (-energy[sy][sx], sy, sx))
while pq:
d, y, x = heapq.heappop(pq)
d *= -1
if dist[y][x] > d:
continue
dist[y][x] = d
if dist[y][x] == 0:
continue
for dx, dy in dxdy:
nx = x + dx
ny = y + dy
if 0 <= nx < W and 0 <= ny < H and MAP[ny][nx] != "#":
if ny == gy and nx == gx:
print("Yes")
exit()
if dist[ny][nx] >= dist[y][x] - 1:
continue
dist[ny][nx] = max(dist[y][x] - 1, energy[ny][nx])
heapq.heappush(pq, (-dist[ny][nx], ny, nx))
print("No")
E - Minimize Sum of Distances
問題
$N$ 頂点からなる木が与えられます。頂点は $1$ から $N$ までの番号がついており、 $i$ 番目の辺は頂点 $A_i, B_i$ を結んでいます。
長さ $N$ の正整数列 $C = (C_1, C_2, \ldots ,C_N)$ が与えられます。$d(a, b)$ を頂点 $a, b$ の間にある辺の数とし、 $x = 1, 2, \ldots ,N$ に対して $\displaystyle f(x) = \sum_{i=1}^{N} (C_i \times d(x, i))$ とします。$\displaystyle \min_{1 \leq v \leq N} f(v)$ を求めてください。
考察
説明のために入力例1を例に挙げる。
まず思考の過程として、$C_i$が一番大きな頂点との距離を最小にするために、$f(4)$を考えるが、出力例1にもある通り、これは最小ではない。ここから、貪欲に最小となる頂点$v$を決めるのは無理そうだと考える。
そうなると、後はそれぞれの頂点について、$f(v)$を高速に求めることで最小値を求める全探索的手法を考えるが、これは、$f(1)$をあらかじめ求めておくことで可能であることが考察するとわかる。具体的には、まず$f(1)$を求めると、下図のような状態になる。
ここから、隣の頂点2の$f(2)$を求める手順は以下となる。
これを実装する関係上、下図のようなmemoをdfsで作成した。
コード
import sys
from types import GeneratorType
from collections import deque
sys.setrecursionlimit(int(1e7)) # 再起上限解放
def bootstrap(f, stack=[]): # 再帰高速化用、yieldを使う
def wrappedfunc(*args, **kwargs):
if stack:
return f(*args, **kwargs)
else:
to = f(*args, **kwargs)
while True:
if type(to) is GeneratorType:
stack.append(to)
to = next(to)
else:
stack.pop()
if not stack:
break
to = stack[-1].send(to)
return to
return wrappedfunc
N = int(input())
adj = [[] for _ in range(N)]
for _ in range(N - 1):
a, b = map(int, input().split())
a -= 1
b -= 1
adj[a].append(b)
adj[b].append(a)
C = list(map(int, input().split()))
# f(1)を求める
dist = [N + 10] * N
q = deque([(0, 0)])
while q:
d, node = q.popleft()
dist[node] = d
for nxt in adj[node]:
if dist[nxt] > dist[node] + 1:
dist[nxt] = dist[node] + 1
q.append((dist[nxt], nxt))
ans = [-1] * N
ans[0] = 0
for i in range(N):
ans[0] += dist[i] * C[i]
# memoの作成
memo = [-1] * N
@bootstrap
def dfs(pre, node):
if memo[node] != -1:
yield memo[node]
res = C[node]
for nxt in adj[node]:
if pre == nxt:
continue
tmp = yield dfs(node, nxt)
res += tmp
memo[node] = res
yield res
dfs(-1, 0)
SUM = sum(C)
# f(node)とmemoを基に、f(nxt)をO(1)で求める
@bootstrap
def dfs2(node, now):
for nxt in adj[node]:
if ans[nxt] != -1:
continue
ans[nxt] = now - memo[nxt] + (SUM - memo[nxt])
yield dfs2(nxt, ans[nxt])
yield None
dfs2(0, ans[0])
print(min(ans))