[ABC176 D] Wizard in Maze

https://atcoder.jp/contests/abc176/tasks/abc176_d

Ruby で通すのが難しかった 0-1 BFS 問題。

考え方

• 魔法で飛んだ場合の移動コストを 1 としたグラフと見なす
• ダイクストラ法で歩いたり飛んだり歩いたりする
• ゴールまでの総コストが答え

解き方

コストが二種類に限られるので 0-1 BFS を使うと効率的になる。

Ruby での解き方

一つの両端キューを用いた 0-1 BFS では余裕がない。二つの単方向キューを用いて「順番にいま見ているキューが空になるまで回す」とした方がいい。

「歩く」のと「飛ぶ」のを同時平行で行ってしまうと、飛んだ場合のコストを歩く場合のコストで上書きする頻度が高くなり、計算に無駄が生じるのだと思われる。

普通の実装 (TLE)

基本形

徒歩と飛行の範囲を別々にする方法。

コード

H, W = gets.split.collect(&:to_i)   # => [4, 4]
CYX = gets.split.collect(&:to_i)    # => [1, 1]
DYX = gets.split.collect(&:to_i)    # => [4, 4]
S = H.times.collect { gets.strip }  # => ["..#.", "..#.", ".#..", ".#.."]

CXY = CYX.collect(&:pred).reverse   # => [0, 0]
DXY = DYX.collect(&:pred).reverse   # => [3, 3]

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

  def around_each(around)
    around.each do |e|
      v = self + e
      if Field[v]
        yield v
      end
    end
  end

  def inspect
    [x, y].inspect
  end
end

# 歩いていける範囲
AROUND0 = (-1..1).to_a.repeated_permutation(2).find_all { |e| e.sum.abs == 1 }.collect { |e| V[*e] }

# 飛んでいける範囲
AROUND1 = (-2..2).to_a.repeated_permutation(2).reject { |e| e.all?(&:zero?) }.collect { |e| V[*e] }

Field = {}
H.times do |y|
  W.times do |x|
    Field[V[x, y]] = S[y][x] == "."
  end
end

START = V[*CXY]                     # => [0, 0]
GOAL  = V[*DXY]                     # => [3, 3]

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

queue = []
queue << START

while from = queue.shift
  # 歩く場合
  from.around_each(AROUND0) do |to|
    v = d[from] + 0
    if v < d[to]
      d[to] = v
      queue.unshift(to)         # 左から
    end
  end

  # 飛ぶ場合
  from.around_each(AROUND1) do |to|
    v = d[from] + 1
    if v < d[to]
      d[to] = v
      queue << to               # 右から
    end
  end
end

p d[GOAL].infinite? ? -1 : d[GOAL]  # => 1

[変化1] 移動処理の共通化

飛行範囲に徒歩範囲を含むので上下左右に飛んだ場合のみコストを0とする方法。

コード

H, W = gets.split.collect(&:to_i)   # => [4, 4]
CYX = gets.split.collect(&:to_i)    # => [1, 1]
DYX = gets.split.collect(&:to_i)    # => [4, 4]
S = H.times.collect { gets.strip }  # => [[".", ".", "#", "."], [".", ".", "#", "."], [".", "#", ".", "."], [".", "#", ".", "."]]

CXY = CYX.collect(&:pred).reverse   # => [0, 0]
DXY = DYX.collect(&:pred).reverse   # => [3, 3]

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 = (e.x.abs + e.y.abs) == 1 ? 0 : 1 # 上下左右のときだけコスト0とする
        yield v, cost
      end
    end
  end

  def inspect
    [x, y].inspect
  end
end

# 飛んでいける範囲に歩いていける範囲は含まれるため飛んでいける範囲だけあればよい
AROUND = (-2..2).to_a.repeated_permutation(2).reject { |e| e.all?(&:zero?) }.collect { |e| V[*e] }

Field = {}
H.times do |y|
  W.times do |x|
    Field[V[x, y]] = S[y][x] == "."
  end
end

START = V[*CXY]                     # => [0, 0]
GOAL  = V[*DXY]                     # => [3, 3]

d = Hash.new(Float::INFINITY)   # distance
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

p d[GOAL].infinite? ? -1 : d[GOAL]  # => 1

効率性重視の実装 (AC)

TLE を回避するために行なったこと

• ベクトルをキーにして連想配列にアクセスしない
  • 致命的に遅いので x, y 値で直接二次元配列にアクセスさせる
• 二つのキューを用意する
  • これによってキューの前後どちらに入れるかは関係なくなるはずだが、なぜかコスト0用の queue0 には unshift で入れる深さ優先探索型にした方が約 50 ms 速くなる
• 順番にいま見ているキューが空になるまで回す (重要)
  • これだけで約 500 ms 速くなる
• 飛んで行ける範囲から歩いていける範囲を除外する
  • 5x5 の 25 マスから上下左右の 4 マスは見る必要がない
  • これで約 80 ms 速くなる
• 探索中にはベクトルオジェクトを生成しない
  • 普通の問題だとここまでする必要はないがここまでしないとだめだった

コード

1344 ms

H, W = gets.split.collect(&:to_i)             # => [4, 4]
CYX = gets.split.collect(&:to_i)              # => [1, 1]
DYX = gets.split.collect(&:to_i)              # => [4, 4]
C = H.times.collect { gets.strip.chars }      # => [[".", ".", "#", "."], [".", ".", "#", "."], [".", "#", ".", "."], [".", "#", ".", "."]]

Field = C.collect { |e| e.collect { |e| e == "." } }

CXY = CYX.collect(&:pred).reverse             # => [0, 0]
DXY = DYX.collect(&:pred).reverse             # => [3, 3]

V = Data.define(:x, :y) do
  def to_a = deconstruct
end

# 歩く範囲 (上下左右)
AROUND0 = (-1..1).to_a.repeated_permutation(2).find_all { |e| e.sum.abs == 1 }.collect { |e| V[*e] }

# 飛ぶ範囲 (5x5=25マスとするのではなく、中央と歩いていける範囲は除外しておく)
AROUND1 = (-2..2).to_a.repeated_permutation(2).reject { |e| e.all?(&:zero?) }.collect { |e| V[*e] } - AROUND0

START = V[*CXY]                               # => #<data V x=0, y=0>
GOAL  = V[*DXY]                               # => #<data V x=3, y=3>

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

queue0 = []                     # 歩く用
queue1 = []                     # 飛ぶ用

queue0 << START.to_a

def around_each(bx, by, around)
  around.each do |v|
    x = bx + v.x
    y = by + v.y
    if 0 <= x && x < W && 0 <= y && y < H
      if Field[y][x]            # 通れるか？
        yield x, y
      end
    end
  end
end

until queue0.empty?
  # 歩く場合
  until queue0.empty?           # 歩く場合のみで全探索する(重要)
    fx, fy = queue0.shift
    queue1 << [fx, fy]          # 歩いて行けならあとでそこから飛んでみる
    around_each(fx, fy, AROUND0) do |x, y|
      v = d[fx][fy]
      if v < d[x][y]
        d[x][y] = v
        queue0.unshift([x, y])  # BFS (push) より DFS (unshift) にした方が 50ms 速い
      end
    end
  end

  # 飛ぶ場合
  until queue1.empty?           # 飛ぶ場合のみで全探索する(重要)
    fx, fy = queue1.shift
    around_each(fx, fy, AROUND1) do |x, y|
      v = d[fx][fy] + 1
      if v < d[x][y]
        d[x][y] = v
        queue0 << [x, y]        # 飛んで行けるならあとでそこから歩いてみる
      end
    end
  end
end

p d.dig(*GOAL).infinite? ? -1 : d.dig(*GOAL)  # => 1

両端キューを使って通したい場合 (AC)

移動処理を共通化すると両端キューを使ってもぎりぎり通る。

コード

1823 ms

H, W = gets.split.collect(&:to_i)             # => [4, 4]
CYX = gets.split.collect(&:to_i)              # => [1, 1]
DYX = gets.split.collect(&:to_i)              # => [4, 4]
C = H.times.collect { gets.strip.chars }      # => [[".", ".", "#", "."], [".", ".", "#", "."], [".", "#", ".", "."], [".", "#", ".", "."]]

Field = C.collect { |e| e.collect { |e| e == "." } }

CXY = CYX.collect(&:pred).reverse             # => [0, 0]
DXY = DYX.collect(&:pred).reverse             # => [3, 3]

V = Data.define(:x, :y) do
  def to_a = deconstruct
end

# 飛んでいける範囲に歩いていける範囲は含まれるため飛んでいける範囲だけあればよい
AROUND = (-2..2).to_a.repeated_permutation(2).find_all { |e| e.any?(&:nonzero?) }.collect { |e| V[*e] }

START = V[*CXY]                               # => #<data V x=0, y=0>
GOAL  = V[*DXY]                               # => #<data V x=3, y=3>

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

queue = []
queue << START.to_a

def around_each(bx, by)
  AROUND.each do |v|
    x = bx + v.x
    y = by + v.y
    if 0 <= x && x < W && 0 <= y && y < H
      if Field[y][x]            # 通れるか？
        cost = (v.x.abs + v.y.abs) == 1 ? 0 : 1 # 上下左右のときだけコスト0とする
        yield x, y, cost
      end
    end
  end
end

until queue.empty?
  fx, fy = queue.shift
  around_each(fx, fy) do |x, y, cost|
    v = d[fx][fy] + cost
    if v < d[x][y]
      d[x][y] = v
      if cost == 0
        queue.unshift([x, y])
      else
        queue.push([x, y])
      end
    end
  end
end

p d.dig(*GOAL).infinite? ? -1 : d.dig(*GOAL)  # => 1

気になったこと

Ruby の Data が Struct と比べて使いにくいように感じる。

Struct.new(:x, :y)[1, 2].to_a             # => [1, 2]
Data.define(:x, :y)[1, 2].to_a rescue $!  # => #<NoMethodError: undefined method `to_a' for #<data x=1, y=2>>

to_a がないので dig(*object) などとして使いたい場合に少し躓いた。

類題

https://zenn.dev/megeton/articles/4901378ee66567

参考

• https://ntk-ta01.hatenablog.com/entry/2020/08/23/113117
• https://twitter.com/kyopro_friends/status/1297498840753303555?s=20
• https://note.com/omotiti/n/nb4feb3c59932
• https://atcoder.jp/contests/abc176/submissions/35568963
• https://www.youtube.com/watch?v=Vuit2jRweek&t=5784s