C - Colorful Beans
問題
考えたこと
各色の最小値をdictに保存します。そこから最大値を求めれば終わりです。
ACコード
c.py
from collections import defaultdict
n = int(input())
d = defaultdict(lambda: float("inf"))
for _ in range(n):
a, c = map(int, input().split())
if d[c] > a:
d[c] = a
print(max(d.values()))
D - Medicines on Grid
問題
考えたこと
どの薬から自分以外のどの薬までいけるかを考えればうまくいきます。手順としては各薬をスタートにしてBFSを行い、ある薬において、距離がスタート地点の薬のエネルギー以下になっていればその薬までたどり着けます。入力例1で上記のグラフを作ってみましょう！
入力例1:
まず、どこに$S,T,E$があるか整理してみましょう。整理した結果が図１です。
図１をもとに$(1, 1), (1, 3), (3, 2)$の薬でどのマスまでいけるか考えたのが、図２です。
図２を見ると、どの薬同士がつながっているかわかると思います。列挙してみると
\begin{align}
(1, 1)&: (1, 3), (2, 3), (3, 2) \\
(1, 3)&: (1, 1), (2, 3), (3, 2) \\
(3, 2)&: \\
(2, 3)&: (1, 3) \\
\end{align}
となっています。しかし、このグラフのままではゴールとつながってないので探索できません。なので、ゴールにエネルギー0を置くことにします。そうすると、
\begin{align}
(1, 1)&: (1, 3), (2, 3), (3, 2) \\
(1, 3)&: (1, 1), (2, 3), (3, 2), (4, 4) \\
(3, 2)&: \\
(2, 3)&: (1, 3) \\
\end{align}
となり、有向グラフがうまく張れました。また、有向グラフをDFSやBFSで探索するにはスタートとゴールがわかっていないとできないので、その情報は各自持っておきましょう。
ACコード
d.py
from collections import deque, defaultdict
h, w = map(int, input().split())
S = [input() for _ in range(h)]
n = int(input())
# E[薬の位置]=置き換えることができるエネルギー量
E = dict()
for _ in range(n):
r, c, e = map(int, input().split())
r -= 1
c -= 1
E[(r, c)] = e
# Gを作成後に再度スタートからゴールまで探索するためsi,sj, gi,gjに各頂点の情報を保存
for i in range(h):
for j in range(w):
if S[i][j] == "S":
si, sj = i, j
# スタート地点に薬がおいてなければNo
if E.get((si, sj), -1) == -1:
exit(print("No"))
if S[i][j] == "T":
gi, gj = i, j
# Eを各頂点としてグラフを作るため、ゴールの頂点を追加
E[(gi, gj)] = 0
# 四方向への移動
dij = [(-1, 0), (1, 0), (0, -1), (0, 1)]
G = defaultdict(list)
# 各薬からどの薬までいけるかBFSで確かめる
# G[(現在地の薬の頂点)]=[(行先の薬の頂点), ...]
for rc1, e1 in E.items():
dist = [[-1 for _ in range(w)] for _ in range(h)]
pos_i, pos_j = rc1
dist[pos_i][pos_j] = 0
que = deque([(pos_i, pos_j)])
while que:
pos_i, pos_j = que.popleft()
for di, dj in dij:
if 0 <= (nex_i := pos_i + di) < h and 0 <= (nex_j := pos_j + dj) < w:
if S[nex_i][nex_j] != "#" and dist[nex_i][nex_j] == -1:
dist[nex_i][nex_j] = dist[pos_i][pos_j] + 1
que.append((nex_i, nex_j))
# 各薬から自分を除いたe以下の距離まで到達できる薬同士で辺をつなげる
for rc2, _ in E.items():
ti, tj = rc2
if dist[ti][tj] == -1 or dist[ti][tj] > e1 or rc1 == rc2:
continue
G[rc1].append(rc2)
que = deque([(si, sj)])
visited = {(si, sj)}
# 作成したグラフを探索、queをstackとして扱えばDFSとなる
while que:
pos = que.pop()
for next in G[(pos)]:
if next in visited:
continue
visited.add(next)
que.append(next)
print("Yes" if (gi, gj) in visited else "No")