トヨタ自動車プログラミングコンテスト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')