Zenn
🚲

[ARC005 C] 器物損壊！高橋君 (0-1 BFS)

2024/03/11に公開
Ruby
AtCoder
競プロ
ダイクストラ法
幅優先探索
tech

https://atcoder.jp/contests/arc005/tasks/arc005_3

ダイクストラ法の負担を軽減した 0-1 BFS を用いる問題。

解き方

最初に考えたのが「堀を壊した回数をインクリメントし 2 を超えた場合それ以上進まない」とする方法だが、これではうまくいかなかった。

正しくは、

  1. 堀への辺の重みを 1 としたグラフと見なす
  2. ダイクストラ法で探索する
  3. ゴールのコストが 2 以下かを判定する

としないといけない。

0-1 BFS

ただ、この問題では単純にダイクストラ法を用いると TLE になる。[1]

そこでコストは 0 か 1 と決まっているので、優先度付きキューに入れるときに 0 と 1 をそれぞれ前後どちらに入れるかを決めておけば、並び換える必要がなくなり TLE を回避できる。コストが 2 つに限定されているときにだけ使える技である。

これを 0-1 BFS[2] と呼ぶ。ここでいう BFS とは Breadth な幅優先探索ではなく、幅優先探索をベースとした最良優先探索 (Best-First Search) の略である。

なお、ダイクストラ法は幅優先探索(BFS)をベースにした最良優先探索(BFS)なので、ダイクストラ法に対して BFS と言われた場合、たぶん後者だとは思うけど正確にはどっちのことを指しているのかわからん、というややこしい問題がある。

参考:

https://betrue12.hateblo.jp/entry/2018/12/08/000020

2 を超えた場合それ以上進まない (WA)

最初に自力で考えたこの方法は何がダメなんだろうか？ visited を使用して二度目の訪問を避けるため、より低コストで到達可能であっても更新されない、ということだろうか。

コード
H, W = gets.split.collect(&:to_i)   # => [4, 5]
C = H.times.collect { gets.strip }  # => ["s####", "....#", "#####", "#...g"]

V = Data.define(:x, :y) do
  def +(v)
    self.class.new(x + v.x, y + v.y)
  end

  def inspect
    [x, y].inspect
  end

  def around_each
    AROUND.each do |e|
      v = self + e
      if Field[v]
        cost = Field[v] == "#" ? 1 : 0
        yield v, cost
      end
    end
  end
end

AROUND = (-1..1).to_a.repeated_permutation(2).find_all { |e| e.sum.abs == 1 }.collect { |e| V[*e] }

Field = {}
H.times do |y|
  W.times do |x|
    v = V[x, y]
    Field[v] = C[y][x]
    if Field[v] == "s"
      START = v
    end
    if Field[v] == "g"
      GOAL = v
    end
  end
end

queue = []
queue << [START, 0]

ans = "NO"
visited = {}
until queue.empty?
  from, count = queue.shift
  if count <= 2 && !visited[from]
    visited[from] = true
    if from == GOAL
      ans = "YES"
      break
    end
    from.around_each do |to, cost|
      queue << [to, count + cost]
    end
  end
end

ans                                 # => "YES"
puts ans

普通の実装 (TLE)

基本形

なるべく共通化したシンプルな実装になる。

コード
H, W = gets.split.collect(&:to_i)   # => [4, 5]
C = H.times.collect { gets.strip }  # => ["s####", "....#", "#####", "#...g"]

V = Data.define(:x, :y) do
  def +(v)
    self.class.new(x + v.x, y + v.y)
  end

  def around_each
    AROUND.each do |e|
      v = self + e
      if Field[v]
        cost = Field[v] == "#" ? 1 : 0
        yield v, cost
      end
    end
  end
end

AROUND = (-1..1).to_a.repeated_permutation(2).find_all { |e| e.sum.abs == 1 }.collect { |e| V[*e] }

Field = {}
H.times do |y|
  W.times do |x|
    v = V[x, y]
    Field[v] = C[y][x]
    if Field[v] == "s"
      START = v
    end
    if Field[v] == "g"
      GOAL = v
    end
  end
end

d = Hash.new(Float::INFINITY)
d[START] = 0

queue = []
queue << START

while from = queue.shift
  from.around_each do |to, cost|
    v = d[from] + cost
    if v < d[to]
      d[to] = v
      if cost == 0
        queue.unshift(to)
      else
        queue.push(to)
      end
    end
  end
end

ans = d[GOAL] <= 2 ? "YES" : "NO"   # => "YES"
puts ans

[変化1] なるべく条件別に分ける

(この問題ではここまで分ける必要はないが)もし移動範囲も条件も異なる場合には、全体で分離した方がわかりやすい場合もある。

コード
H, W = gets.split.collect(&:to_i)         # => [4, 5]
C = H.times.collect { gets.strip.chars }  # => [["s", "#", "#", "#", "#"], [".", ".", ".", ".", "#"], ["#", "#", "#", "#", "#"], ["#", ".", ".", ".", "g"]]

V = Data.define(:x, :y) do
  def +(v)
    self.class.new(x + v.x, y + v.y)
  end

  def around_each0
    AROUND.each do |e|
      v = self + e
      if Field[v] && Field[v] != "#"
        yield v
      end
    end
  end

  def around_each1
    AROUND.each do |e|
      v = self + e
      if Field[v] && Field[v] == "#"
        yield v
      end
    end
  end
end

AROUND = (-1..1).to_a.repeated_permutation(2).find_all { |e| e.sum.abs == 1 }.collect { |e| V[*e] }

Field = {}
H.times do |y|
  W.times do |x|
    v = V[x, y]
    Field[v] = C[y][x]
    if Field[v] == "s"
      START = v
    end
    if Field[v] == "g"
      GOAL = v
    end
  end
end

d = Hash.new(Float::INFINITY)
d[START] = 0

queue = []
queue << START

while from = queue.shift
  # コスト 0 の場合
  from.around_each0 do |to|
    v = d[from]
    if v < d[to]
      d[to] = v
      queue.unshift(to)
    end
  end

  # コスト 1 の場合
  from.around_each1 do |to|
    v = d[from] + 1
    if v < d[to]
      d[to] = v
      queue.push(to)
    end
  end
end

ans = d[GOAL] <= 2 ? "YES" : "NO"         # => "YES"
puts ans

[変化2] 複数のキューを用意する

二つのキューを使って一つ目のキューから処理していく方法で、冗長に感じるかもしれないが、この方法であればキューをさらに増やすことができるため、3種類のコストを持つ 0-1-2 BFS にも対応できる。

コード
H, W = gets.split.collect(&:to_i)         # => [4, 5]
C = H.times.collect { gets.strip.chars }  # => [["s", "#", "#", "#", "#"], [".", ".", ".", ".", "#"], ["#", "#", "#", "#", "#"], ["#", ".", ".", ".", "g"]]

V = Data.define(:x, :y) do
  def +(v)
    self.class.new(x + v.x, y + v.y)
  end

  def around_each0
    AROUND.each do |e|
      v = self + e
      if Field[v] && Field[v] != "#"
        yield v
      end
    end
  end

  def around_each1
    AROUND.each do |e|
      v = self + e
      if Field[v] && Field[v] == "#"
        yield v
      end
    end
  end
end

AROUND = (-1..1).to_a.repeated_permutation(2).find_all { |e| e.sum.abs == 1 }.collect { |e| V[*e] }

Field = {}
H.times do |y|
  W.times do |x|
    v = V[x, y]
    Field[v] = C[y][x]
    if Field[v] == "s"
      START = v
    end
    if Field[v] == "g"
      GOAL = v
    end
  end
end

d = Hash.new(Float::INFINITY)
d[START] = 0

queue0 = []
queue1 = []
queue0 << START

until queue0.empty? && queue1.empty?
  # コスト 0 の場合
  if from = queue0.shift
    queue1 << from              # コスト0で行けるならコスト1の場合もあとで試す
    from.around_each0 do |to|
      v = d[from]
      if v < d[to]
        d[to] = v
        queue0 << to
      end
    end
  end

  # コスト 1 の場合
  if queue0.empty?
    if from = queue1.shift
      from.around_each1 do |to|
        v = d[from] + 1
        if v < d[to]
          d[to] = v
          queue0 << to          # 堀を壊したので再度低コストで探索する
        end
      end
    end
  end
end

ans = d[GOAL] <= 2 ? "YES" : "NO"         # => "YES"
puts ans

優先度付きキュー版 (TLE)

普通のダイクストラ法でも解けるが時間が間に合わない。

コード
H, W = gets.split.collect(&:to_i)             # => [6, 6]
Field = H.times.collect { gets.strip.chars }  # => [[".", ".", ".", ".", ".", "s"], ["#", "#", "#", ".", ".", "."], ["#", "#", "#", ".", ".", "."], ["#", "#", "#", "#", "#", "#"], [".", ".", ".", "#", "#", "#"], ["g", ".", "#", "#", "#", "#"]]

V = Data.define(:x, :y) do
  def +(v)
    self.class.new(x + v.x, y + v.y)
  end

  def inspect
    [x, y].inspect
  end

  def around_each
    AROUND.each do |e|
      v = self + e
      if 0 <= v.y && v.y < H && 0 <= v.x && v.x < W
        cost = Field[v.y][v.x] == "#" ? 1 : 0
        yield v, cost
      end
    end
  end
end

AROUND = (-1..1).to_a.repeated_permutation(2).find_all { |e| e.sum.abs == 1 }.collect { |e| V[*e] }

H.times do |y|
  W.times do |x|
    v = V[x, y]
    if Field[y][x] == "s"
      START = v
    end
    if Field[y][x] == "g"
      GOAL = v
    end
  end
end

d = Array.new(W) { Array.new(H, Float::INFINITY) }
heap = Heap.new { |e| d[e.x][e.y] }

d[START.x][START.y] = 0
heap << START

while from = heap.pop
  from.around_each do |to, cost|
    v = d[from.x][from.y] + cost
    if v < d[to.x][to.y]
      d[to.x][to.y] = v
      heap << to
    end
  end
end

ans = d[GOAL.x][GOAL.y] <= 2 ? "YES" : "NO"   # => "YES"
puts ans

効率性重視の実装 (AC)

座標の範囲内チェックで Field[v] を Field.dig(v.y, v.x) に置き換えてずいぶんハマった。Ruby で配列に対する負のインデックスが反対側を参照してくれるのは非常に便利だが、このケースに限っては想定外だった。

コード
608 ms
H, W = gets.split.collect(&:to_i)             # => [6, 6]
Field = H.times.collect { gets.strip.chars }  # => [[".", ".", ".", ".", ".", "s"], ["#", "#", "#", ".", ".", "."], ["#", "#", "#", ".", ".", "."], ["#", "#", "#", "#", "#", "#"], [".", ".", ".", "#", "#", "#"], ["g", ".", "#", "#", "#", "#"]]

V = Data.define(:x, :y) do
  def +(v)
    self.class.new(x + v.x, y + v.y)
  end

  def inspect
    [x, y].inspect
  end

  def around_each
    AROUND.each do |e|
      v = self + e
      if 0 <= v.y && v.y < H && 0 <= v.x && v.x < W
        cost = Field[v.y][v.x] == "#" ? 1 : 0
        yield v, cost
      end
    end
  end
end

AROUND = (-1..1).to_a.repeated_permutation(2).find_all { |e| e.sum.abs == 1 }.collect { |e| V[*e] }

H.times do |y|
  W.times do |x|
    case Field[y][x]
    when "s"
      START = V[x, y]
    when "g"
      GOAL = V[x, y]
    end
  end
end

d = Array.new(W) { Array.new(H, Float::INFINITY) }
d[START.x][START.y] = 0

queue = []
queue << START

while from = queue.shift
  from.around_each do |to, cost|
    v = d[from.x][from.y] + cost
    if v < d[to.x][to.y]
      d[to.x][to.y] = v
      if cost == 0
        queue.unshift(to)
      else
        queue.push(to)
      end
    end
  end
end

ans = d[GOAL.x][GOAL.y] <= 2 ? "YES" : "NO"   # => "YES"
puts ans
脚注

  1. C++ や Rust では速すぎてダイクストラ法で通ってしまうと思われる ↩︎

  2. 01-BFS 表記もあるようだが海外も含めると 0-1 BFS と書くのが一般的なようだ ↩︎

Discussion