ABC405 D - Escape Route
https://atcoder.jp/contests/abc405/tasks/abc405_d
コンテスト中に AC できましたが、この問題だけで 35 分もかかってしまい、パフォーマンスが 874 と低くなってしまいました。レートもガタ落ちです。あと 10 分早ければパフォーマンスが 100 上がっていたようなのでもっと早く解けるようにしたいところです。しっかり復習して理解を深めておくため、記事にしました。解説というよりも感想の要素が大きな記事です。
コンテスト中の自分の動き
非常口が複数あるので、最短距離を求めるのなら多始点 BFS だと思いました。これは 2024 年 12 月の ABC383-C で出題されており、当時は知らなくて解けませんでした。復習済みなので今回はこの発想がすんなり出てきました。
しかし経路復元の方法で悩んでしまいました。「個々のマスから最短でたどり着ける非常口を調べ、それぞれのマスについてその非常口までの経路を調べる」ということを考えていました。これをすると BFS を最大 $ 10^6 $ 回やらないといけなくなるので計算量オーバーです。
そこで思いついたのが「各マスごとに最短で辿り着ける非常口とそこまでの最短距離を保持する BFS」でした。経路についてはその後もう一度全てのマスを見て「隣接するマスの中に同じ非常口を目的とし、最短距離が1小さいマスがあればそちらに矢印を向ける」ようにすることで求めました。
これにより正解することができました。ただ、時間はものすごくかかりました。書きながら明らかに手が動いていなかったのを自覚していました。コードが複雑になったとはいえ、この程度で手が止まってしまうようではいけません。
まずかった点の考察
結局のところ僕の考え方は「最短で辿り着ける非常口」が無駄でした。最短距離を求めるときは非常口から各マスへ向けて探索しているのに、なぜか経路を求めるときには逆に各マスから非常口へと辿ろうとしてしまっていました。こうなってしまった原因には多始点 BFS への理解が足りないことが挙げられます。多始点 BFS によって求まる最短距離の値が何を表しているのかがよくわかっていなかったのではないでしょうか。そもそも多始点 BFS が正しく動作する理由や仕組みも理解できていない気がします。
もう一つには経路復元への苦手意識が挙げられます。なるべく避けたい気持ちからこれを使わない方法を考えてしまったのではないでしょうか。苦手意識にとらわれず適切な解法を選べるようになるか、苦手そのものをなくせるようになりたいものです。
さらにいえば実装が遅かったのもダメです。最短となる非常口の情報を載せるといってもそんなに難しくはないはずです。直接の改善にはなりませんが、BFS によるグリッド探索のテンプレを作っておくことにしました。いくら書き慣れていても一から書くよりは既存のものをコピペ改変した方が速いでしょうし、既にあるコードを見ながら書き換える形の方が今回のような改変（どこの非常口までの距離なのかという情報を BFS に載せる）はイメージしやすい気がします。
その他、グリッド問題が苦手な自覚もあります。個人的にはいわゆる数学問題よりも苦手な気がします。
実装
せっかくなので僕がコンテスト中に行った「隣接マスに距離が1小さいものがあればそちらに矢印を向ける」という方針でやってみます。同じくコンテスト中に採った「最短で辿り着ける非常口」という方針の方は無駄なので忘れます。
まず多始点 BFS により各マスについて最寄り非常口への最短距離を求めておきます。その後に全てのマスを見て矢印をつけていきます。
H, W = map(int, input().split())
S = [[" " for _ in range(W+1)] for _ in range(H+1)]
E = [] # 非常口の一覧
for i in range(1, H+1):
line = input()
for j in range(1, W+1):
S[i][j] = line[j-1]
if S[i][j] == "E":
E.append((i, j))
# BFS
## 準備
from collections import deque
que = deque([])
INF = 10**20
dist = [[INF for _ in range(W+1)] for _ in range(H+1)]
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1] # グリッドの始点が左上として、それぞれ上下左右。 ["^", "v", "<", ">"]
## 初期化
for e in E:
que.append(e)
dist[e[0]][e[1]] = 0
## 探索
while (que):
q = que.popleft()
x, y = q[0], q[1]
for d in range(4):
nx, ny = x + dx[d], y + dy[d]
if 1 <= nx <= H and 1 <= ny <= W and S[nx][ny] != "#":
if dist[nx][ny] > dist[x][y] + 1:
dist[nx][ny] = dist[x][y] + 1
que.append((nx, ny))
# 隣に自分よりも dist が 1 小さいマスがあればそちらへの矢印を入れる
arrows = ["^", "v", "<", ">"]
for i in range(1, H+1):
for j in range(1, W+1):
if S[i][j] == "E":
print("E", end="")
elif dist[i][j] == INF:
print("#", end="")
else:
for d in range(4):
nx, ny = i + dx[d], j + dy[d]
if 1 <= nx <= H and 1 <= ny <= W and S[nx][ny] != "#":
if dist[nx][ny] == dist[i][j] - 1:
print(arrows[d], end="") # 上下左右それぞれに変数 d と arrows が対応する
break
print("")
実装2
公式解説のやり方でもやっておきました。要するに「多始点 BFS」+「経路復元」ですね。
H, W = map(int, input().split())
S = [[" " for _ in range(W+1)] for _ in range(H+1)]
E = [] # 非常口の一覧
for i in range(1, H+1):
line = input()
for j in range(1, W+1):
S[i][j] = line[j-1]
if S[i][j] == "E":
E.append((i, j))
# BFS
## 準備
from collections import deque
que = deque([])
INF = 10**20
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1] # 上、下、左、右
arrows = ["v", "^", ">", "<"] # 下、上、右、左 （dx, dy と逆にする）
dist = [[INF for _ in range(W+1)] for _ in range(H+1)]
ans = [["#" for _ in range(W+1)] for _ in range(H+1)]
## 初期化
for e in E:
que.append(e)
dist[e[0]][e[1]] = 0
ans[e[0]][e[1]] = "E"
## 探索
while (que):
q = que.popleft()
x, y = q[0], q[1]
for d in range(4):
nx, ny = x + dx[d], y + dy[d]
if 1 <= nx <= H and 1 <= ny <= W and S[nx][ny] != "#":
if dist[nx][ny] > dist[x][y] + 1:
dist[nx][ny] = dist[x][y] + 1
ans[nx][ny] = arrows[d] # 来た方向への矢印を入れる
que.append((nx, ny))
# 答えの出力
for i in range(1, H+1):
for j in range(1, W+1):
print(ans[i][j], end="")
print("")