ABC348のPythonメモ（A～D）


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

https://atcoder.jp/contests/abc348

# A Penalty Kick
https://atcoder.jp/contests/abc348/tasks/abc348_a
## 問題概要
* 整数$N$が与えられるよ
* 3の倍数なら`"x"`,そうでないなら`"o"`を並べて出力してね

## 制約
* $1 \leq N \leq 100$

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

## 解答
```python
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

https://atcoder.jp/contests/abc348/tasks/abc348_b
## 問題概要
* 平面上に、$N$個の点があるよ
  * 座標被りはないよ
* それぞれの点について、一番遠い点を求めてね
  * 一番遠い点が複数ある場合は、番号が小さいものを出力してね

## 制約
* $2 \leq N \leq 100$
* $-1000 \leq X_i,Y_i \leq 1000$

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

## 解答
```python
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
https://atcoder.jp/contests/abc348/tasks/abc348_c

## 問題概要

* $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の降順でソートしてあげて、
* 末尾の項目の美味しさ＝最小値が最大の美味しさ！
## 解答
```python
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
https://atcoder.jp/contests/abc348/tasks/abc348_d

## 問題概要
* $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)$に着た時…
    * 以前来た時よりもエネルギーが少ない状態なら、そこからの探索は必要無いね
      * それより先へ行けることを知っているので
    * 以前来た時よりもエネルギーが多い状態でこれたなら、そこからの探索は必要ですね
      * さらに先へ行ける可能性があるので
## 解答
```python
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')

```