ABC348のPythonメモ（A～D）

トヨタ自動車プログラミングコンテスト2024#4（AtCoder Beginner Contest 348）の解答、思考まとめメモ残し！

A Penalty Kick

問題概要

• 整数$N$が与えられるよ
• 3の倍数なら"x",そうでないなら"o"を並べて出力してね

制約

• $1 \leq N \leq 100$

思考

• Fizz Buzzだ！！！
• 1~Nまでループで回して、3で割れるかどうかの判定をすれば良しですね

解答

N = int(input())

ans_L = []

for i in range(1, N + 1):
    if i % 3 == 0:
        ans_L.append("x")
    else:
        ans_L.append("o")

print("".join(ans))

B Farthest Point

問題概要

• 平面上に、$N$個の点があるよ
  • 座標被りはないよ
• それぞれの点について、一番遠い点を求めてね
  • 一番遠い点が複数ある場合は、番号が小さいものを出力してね

制約

• $2 \leq N \leq 100$
• $-1000 \leq X_i,Y_i \leq 1000$

思考

• 頂点の数が少ないね！
  • 全頂点それぞれに対して、全頂点の距離を調べても間に合うね！
• ルート取ると小数出ちゃってちょっと嫌…
  • ルート取らなくても比較できるので、ルート取らずに2乗の和の状態で比較！
• 頂点番号小さい順に比較しているので、距離が同じ場合は頂点更新されないのでヨシ！

解答

N = int(input())
pos_X = [0] * N
pos_Y = [0] * N

for i in range(N):
    pos_X[i], pos_Y[i] = map(int, input().split())

for s in range(N):
    dist = 0
    max_dist_idx = None

    for g in range(N):
      tmp_dist = abs(pos_X[s] - pos_X[g]) ** 2 + abs(pos_Y[s] - pos_Y[g]) ** 2
      if dist < tmp_dist:
          dist = tmp_dist
          max_dist_idx = g

    print(max_dist_idx + 1)

C Colorful Beans

問題概要

• $N$種類のビーンズが1粒ずつあるよ
• $i$種類目のビーンズは、美味しさが$A_i$で色が$C_i$だよ
• ビーンズは色でしか区別できないよ
• ビーンズの色を1つ決めて、その色のビーンズをどれか1粒食べるよ
• 食べる可能性のあるビーンズの美味しさの最小値を、最大化してね

制約

• $1 \leq N \leq 2\times 10^5$
• $1 \leq A_i \leq 10^9$
• $1 \leq C_i \leq 10^9$

思考

• 文法的に二分探索雰囲気醸し出してるけど…
• 全部のビーンズを見ていって、色ごとに「最小値」を出してあげて、
• 最小値が一番大きいものを教えてあげたらヨシ！
• 「最小値」を小さい方向に更新していきたいので、defaultdictの初期値を$10^{18}$に指定！
• d[i]:=$i$色のビーンズの美味しさの最小値
• 辞書を、x[1]:=valueの降順でソートしてあげて、
• 末尾の項目の美味しさ＝最小値が最大の美味しさ！

解答

N = int(input())
d = defaultdict(lambda: 10**18)
for i in range(N):
    A, C = map(int, input().split())
    d[C] = min(d[C], A)

d = sorted(d.items(), key=lambda x: x[1])
print(d[-1][1])

D Medicines on Grid

問題概要

• $H$行$W$列のグリッドが与えられるよ
  • 空きマス、障害物、スタート地点、ゴール地点があったりするよ
• 高橋くんはエネルギー0でスタート地点にいるよ
• 高橋くんは1マス移動するのにエネルギーを1使うよ
• グリッド上の空きマスに、$N$個の薬がおいてあるよ
  • 薬$i$を使うと、エネルギーを$E_i$にすることができるよ
  • 1度使った薬はなくなるよ
  • 使わなくても良いよ
• 高橋くんはスタート地点からゴールまで行ける？

制約

• $1 \leq H,W \leq 200$
• $1 \leq N \leq 300$

思考

• ゴールはGじゃなくてTであることに注意!!!!!!!!!!
• とりあえず、スタート地点に薬が無いと一歩も動けないので…強制的にNoで…スタート地点の薬は飲むものとして…
• 今のエネルギーが600000とかあるなら、エネルギーを2にしちゃう薬なんかは飲みたくないので、飲まないケースもありそう…？
• 一旦初手薬飲んでエネルギーチャージしてから高橋くんが動き出すとして…
• 途中でエネルギーが増える薬を飲んだ時…
  • そこから新たに動き出したい…ね？
  • 常にエネルギーが一番多い地点から、「どこまで行けるか」を確認したい
    • ダイクストラっぽく、heapqでエネルギーの多い順に状態を取ってあげたい
  • 逆に、ある地点$(h,w)$に着た時…
    • 以前来た時よりもエネルギーが少ない状態なら、そこからの探索は必要無いね
      • それより先へ行けることを知っているので
    • 以前来た時よりもエネルギーが多い状態でこれたなら、そこからの探索は必要ですね
      • さらに先へ行ける可能性があるので

解答

H, W = map(int, input().split())
grid_L = []
for i in range(H):
    grid_L.append(input())

sx, sy = -1, -1
gx, gy = 10**18, 10**18
for i in range(H):
    for j in range(W):
        if grid_L[i][j] == "S": sx, sy = i, j
        if grid_L[i][j] == "T": gx, gy = i, j

N = int(input())
energy_d = [[0] * W for _ in range(H)]

for i in range(N):
    R, C, E = map(int, input().split())
    R -= 1
    C -= 1
    energy_d[R][C] = E

hq = [(-energy_d[sx][sy], sx, sy)]
dp = [[-1] * W for _ in range(H)]

while hq:
    e, x, y = heappop(hq)
    e = -e
    if e == 0: continue

    for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        nx, ny = x + dx, y + dy
        if nx < 0 or H <= nx or ny < 0 or W <= ny or grid_L[nx][ny] == "#": continue

        ne = max(e - 1, energy_d[nx][ny])
        if dp[nx][ny] >= ne: continue

        dp[nx][ny] = ne
        heappush(hq, (-ne, nx, ny))

if dp[gx][gy] == -1:
    print('No')
else:
    print('Yes')