[ABC348 D] Medicines on Grid

https://atcoder.jp/contests/abc348/tasks/abc348_d

BFS + DFS または、ダイクストラ法な問題。

問題を要約する

• 勇者は移動するたび HP が 1 減る
• 宿屋に泊まると HP が回復する
• ゴールまで移動できるか？

回復は加算ではないので減るなら泊まらないほうがいい。ゴール地点で HP が 0 はセーフとする。

解法1. 宿屋の有向グラフ

概要

このマップから、

	0	1	2	3
0	S 1(3)		2(5)
1	壁		4(1)	壁
2	壁	3(1)
3			壁	G

スタートとゴールを含めた宿屋の有向グラフを作って、

スタートからゴールが繋がっているなら Yes とする。

有向グラフの作り方

まずスタートとゴールを含めた宿屋たちの配列を用意する。次にすべての組み合わせで届く範囲に辺を張る。「届く範囲」は BFS で歩数を調べ、その数が移動元の HP 以下であれば到達可能な場所だとわかる。

たとえば (0, 0) の宿1からの歩数は次のようになり、

	0	1	2	3
0	0	1	2	3
1		2	3
2		3	4	5
3	5	4		6

HP は 3 なので3歩目までの範囲にある頂点にだけに辺を張れる。つまり6歩必要なゴールには届かず Start 宿1 宿2 宿3 宿4 の5つには辺を張れる。

なぜ BFS か？

DFS で基点の右マスから出発して基点の左に戻ってくるのをイメージする。このとき基点の左マスは最短1歩のはずだが遠回りしているので最短でも5歩になる。だから消去法で DFS は適さない。最短何歩でいけるか知りたいときは徐々に広げていく BFS を使う。

スタートからゴールへの接続判定

こちらは逆にスタートから遠く離れたゴールにいち速く到達できる可能性がある DFS の方が適している。

Ruby で解くのが難しい？

以上の美しい解法を実装すると TLE になってしまう。

• 配列のかわりに連想配列を使わない
• 配列はあらかじめ想定のサイズを確保する
• 移動できるマスの範囲チェックを何度も行わない

などに気をつけたがだめだった。

あと、スタート地点が宿屋でなければ即 No として、頂点にスタート地点を含めないようにする(あまり気の進まない)方法もあるがやっても効果はなかった。

コード (TLE)

開く

H, W = gets.split.map(&:to_i)                         # => [4, 4]
Field = H.times.collect { gets.strip }                # => ["S...", "#..#", "#...", "..#T"]
N = gets.to_i                                         # => 4
RCE = N.times.collect { gets.split.collect(&:to_i) }  # => [[1, 1, 3], [1, 3, 5], [3, 2, 1], [2, 3, 1]]

Array.class_eval do
  def x = self[0]
  def y = self[1]
end

AROUND = (-1..1).to_a.repeated_permutation(2).find_all { |e| e.sum.abs == 1 }

Route = Array.new(W) { Array.new(H) { [] } }
Field.each.with_index do |row, y|
  row.each_char.with_index do |cell, x|
    case cell
    when "S"
      Start = [x, y]
    when "T"
      Goal = [x, y]
    end

    # セルから行ける隣接セルがすぐにわかるようにもしておく
    # Route[from] = [to1, to2, ...]
    if cell != "#"
      AROUND.each do |e|
        vx = x + e.x
        vy = y + e.y
        if 0 <= vx && vx < W && 0 <= vy && vy < H
          if Field[vy][vx] != "#"
            Route[x][y] << [vx, vy]
          end
        end
      end
    end
  end
end

Route                                                 # => [[[[1, 0]], [], [], [[1, 3]]], [[[0, 0], [1, 1], [2, 0]], [[1, 0], [1, 2], [2, 1]], [[1, 1], [1, 3], [2, 2]], [[0, 3], [1, 2]]], [[[1, 0], [2, 1], [3, 0]], [[1, 1], [2, 0], [2, 2]], [[1, 2], [2, 1], [3, 2]], []], [[[2, 0]], [], [[2, 2], [3, 3]], [[3, 2]]]]
Start                                                 # => [0, 0]
Goal                                                  # => [3, 3]

################ ここまでは同じ ################

# Start と Goal を含めた宿屋の配列を作る
av = RCE.collect { |y, x, hp| [[x.pred, y.pred], hp] }
Nodes = [[Start, 0], *av, [Goal, 0]]                  # => [[[0, 0], 0], [[0, 0], 3], [[2, 0], 5], [[1, 2], 1], [[2, 1], 1], [[3, 3], 0]]

# Start と Goal が何番目をわかりやすくしておく
StartIndex = 0                                        # => 0
GoalIndex  = Nodes.size.pred                          # => 5

# from を基点とした歩数の地図 distance を返す
def bfs(from)
  distance = Array.new(W) { Array.new(H, Float::INFINITY) }
  distance[from.x][from.y] = 0
  queue = [from]
  while from = queue.shift
    Route[from.x][from.y].each do |to|
      v = distance[from.x][from.y] + 1
      if v < distance[to.x][to.y]
        distance[to.x][to.y] = v
        queue << to
      end
    end
  end
  distance
end

# スタートとゴールを含む宿屋たちで有向グラフを作る
# G[from] → [to1, to2, ...]
G = Array.new(Nodes.size) { [] }
Nodes.each.with_index do |(from, hp), a|
  # ゴールから逆走するのは無駄なので省ける
  if a == GoalIndex
    next
  end
  distance = bfs(from)          # これを呼びすぎなのが TLE の原因か(？)
  Nodes.each.with_index do |(to, _), b|
    # 同じ宿に進んでもゴールにたどりつけないのはわかっているので省ける
    if a == b
      next
    end
    # from にある宿屋(a)から hp 歩以内で to にある宿屋(b)に辿りつけるなら辺とする
    if distance[to.x][to.y] <= hp
      G[a] << b
    end
  end
end

# この時点で有向グラフ G を見れば 5 には 2 からしか行けないことなどがわかる
G                                                     # => [[1], [0, 2, 3, 4], [0, 1, 3, 4, 5], [], [2], []]

# 続いて G を見て StartIndex から GoalIndex に行けるか調べる
visited = Array.new(G.size)
visited[StartIndex] = true
queue = [StartIndex]
while from = queue.shift
  if from == GoalIndex
    break
  end
  G[from].each do |to|
    if !visited[to]
      visited[to] = true
      queue.unshift(to)         # DFS
    end
  end
end

ans = visited[GoalIndex]                              # => true
puts ans ? "Yes" : "No"

解法2. ダイクストラ法

概要

• スタート地点からコスト(HP)を更新できるなら移動する
• 途中で宿屋があったら(かつ現状よりよくなるなら)泊まる
• コスト(HP)が高いセルから進めていく

これを拡張グラフでのダイクストラ法、略して拡張ダイクストラ法と呼ぶらしいのだがよくわかっていない。

通過点の HP が広がっていく様子

開く

	0	1	2	3
0	3	2
1
2
3

	0	1	2	3
0	3	2	1
1		1
2
3

	0	1	2	3
0	3	4	5	4
1		1	4
2
3

	0	1	2	3
0	3	4	5	4
1		3	4
2			3
3

	0	1	2	3
0	3	4	5	4
1		3	4
2		2	3	2
3

	0	1	2	3
0	3	4	5	4
1		3	4
2		2	3	2
3				1

(3, 3) のゴールに辿り着いたので探索を打ち切っている。

優先度付きキューは必須？

公式の模範解答(C++)では二通りの実装が紹介されていて、優先度付きキューを使わないと 105 ms で使うと 8 ms だった。一方、Ruby では使わないと TLE で、使って 321 ms なので、優先度付きキューは必須といえる。

とはいえ、他の方の提出を拝見すると優先度付きキューを使わずに、しかも優先度付きキュー使ったときより速い謎のアルゴリズムで通していたので、まだまだ工夫の余地はあるのだろう。

コード (AC)

開く

321 ms

H, W = gets.split.map(&:to_i)                             # => [4, 4]
Field = H.times.collect { gets.strip }                    # => ["S...", "#..#", "#...", "..#T"]
N = gets.to_i                                             # => 4
RCE = N.times.collect { gets.split.collect(&:to_i) }      # => [[1, 1, 3], [1, 3, 5], [3, 2, 1], [2, 3, 1]]

Array.class_eval do
  def x = self[0]
  def y = self[1]
end

AROUND = (-1..1).to_a.repeated_permutation(2).find_all { |e| e.sum.abs == 1 }

Route = Array.new(W) { Array.new(H) { [] } }
Field.each.with_index do |row, y|
  row.each_char.with_index do |cell, x|
    case cell
    when "S"
      Start = [x, y]
    when "T"
      Goal = [x, y]
    end

    # セルから行ける隣接セルがすぐにわかるようにもしておく
    # Route[from] = [to1, to2, ...]
    if cell != "#"
      AROUND.each do |e|
        vx = x + e.x
        vy = y + e.y
        if 0 <= vx && vx < W && 0 <= vy && vy < H
          if Field[vy][vx] != "#"
            Route[x][y] << [vx, vy]
          end
        end
      end
    end
  end
end

Route                                                     # => [[[[1, 0]], [], [], [[1, 3]]], [[[0, 0], [1, 1], [2, 0]], [[1, 0], [1, 2], [2, 1]], [[1, 1], [1, 3], [2, 2]], [[0, 3], [1, 2]]], [[[1, 0], [2, 1], [3, 0]], [[1, 1], [2, 0], [2, 2]], [[1, 2], [2, 1], [3, 2]], []], [[[2, 0]], [], [[2, 2], [3, 3]], [[3, 2]]]]
Start                                                     # => [0, 0]
Goal                                                      # => [3, 3]

################ ここまでは同じ ################

# 宿屋マップ
# INN[x][y] → HP
INN = Array.new(W) { Array.new(H) }
RCE.each { |y, x, hp| INN[x.pred][y.pred] = hp }

# 体力マップ
# hp_map[x][y] → HP
hp_map = Array.new(W) { Array.new(H, -Float::INFINITY) }  # => [[-Infinity, -Infinity, -Infinity, -Infinity], [-Infinity, -Infinity, -Infinity, -Infinity], [-Infinity, -Infinity, -Infinity, -Infinity], [-Infinity, -Infinity, -Infinity, -Infinity]]
hp_map[Start.x][Start.y] = 0

if defined? PriorityQueue
  # AC するには優先度付きキューが必要
  queue = PriorityQueue.new { |_, _, hp| -hp } # 降順
else
  # ただのキューでも解けるが test_11.txt だけが TLE になる
  queue = []
end
queue << [*Start, 0]

until queue.empty?
  x, y, hp = queue.shift

  # (x, y) に hp で来てみたが、もっと多い体力で来れている場合は何もしない
  if hp_map[x][y] > hp
    next
  end

  # ここに宿屋があって今より回復できるなら泊まる
  if e = INN[x][y]
    if hp < e
      hp = e
      hp_map[x][y] = hp
    end
  end

  # 体力がまだ残っているなら一つ減らして次に行けるセルの体力よりも多いなら移動する
  # (体力が多いと移動できる範囲が広がるため)
  if hp > 0
    hp -= 1
    Route[x][y].each do |tx, ty|
      if hp_map[tx][ty] < hp
        hp_map[tx][ty] = hp
        queue << [tx, ty, hp]
      end
    end
  end

  # ゴールに辿りつけるのがわかれば途中で終わってもいい
  # これで 100 ms ほど速くなる
  if !hp_map.dig(*Goal).infinite?
    break
  end
end

ans = !hp_map.dig(*Goal).infinite?                        # => true
puts ans ? "Yes" : "No"

参考

• https://www.youtube.com/watch?v=EPWq-Fsjk6g&t=3255s
• https://qiita.com/hyouri/items/464ddba0c44d0c55012f#d問題
• https://atcoder.jp/contests/abc348/submissions/52159603
• https://atcoder.jp/contests/abc348/submissions/52093884
• https://atcoder.jp/contests/abc348/editorial/9705