🐸

[ABC037 D] 経路

2024/04/18に公開

Ruby

グリッド上で移動経路の総数を求める問題。

問題を要約する

四方に進める
ただし自分のマスより大きい方にだけ進める
移動経路は全部で何通りあるか？

例1でシミュレーション

元のマップから、

	0	1	2
0	1	4	5
1	2	4	9

DP の表を作る。

	0	1	2
0	7	3	2
1	3	2	1

値の意味は、

(2, 1) の 9 から移動できるのは自分のところだけなので 1
(2, 0) の 5 から移動できるのは下の 9 だけなので自分を含めて 2
(0, 0) の 1 から移動できるのは右と下なので自分(1) + 右(3) + 下(3) で 7

なのでメモ化再帰が適している。

値の合計が答え 18 になる。

実装方針

任意のマスから進めたときの移動経路数をわかるようにしておく
それを、すべての場所から開始して合計を返す

実装 (AC)

1633 ms

H, W = gets.split.collect(&:to_i)
A = H.times.collect { gets.split.collect(&:to_i) }.transpose

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 }

# 移動できる場所を調べて有向グラフ化しておく
G = Array.new(W) { Array.new(H) { [] } }
W.times do |x|
  H.times do |y|
    AROUND.each do |e|
      vx = x + e.x
      vy = y + e.y
      if 0 <= vx && vx < W && 0 <= vy && vy < H
        if A[x][y] < A[vx][vy]
          G[x][y] << [vx, vy]
        end
      end
    end
  end
end

# 大きな値を丸めて TLE を回避するため
if true
  MOD = 1000000007
  # MOD = 998244353

  Integer.prepend Module.new {
    def +(other) = super.modulo(MOD)
    def *(other) = super.modulo(MOD)
  }

  [Array, Enumerable].each do |klass|
    klass.class_eval do
      def sum(init = 0, &block)
        if block
          collect(&block).reduce(init, :+)
        else
          reduce(init, :+)
        end
      end
    end
  end
end

######## ここまで事前準備 ########

# 任意のマスから進めたときの移動経路数をわかるようにしておく
dp = Array.new(W) { Array.new(H) }
dfs = -> (x, y) { dp[x][y] ||= G[x][y].sum { |to| dfs[*to] }.next }

# それを、すべての場所から開始して合計を返す
p W.times.sum { |x| H.times.sum { |y| dfs[x, y] } }  # => 18

[応用] 最長パスを求める

EDPC G - Longest Path のように最長パスを求める場合は、最後の三行を次に置き換えるだけでよい。

dp = Array.new(W) { Array.new(H) }
dfs = -> (x, y) { dp[x][y] ||= G[x][y].collect { |to| dfs[*to].next }.max || 0 }
W.times.flat_map { |x| H.times.collect { |y| dfs[x, y] } }.max  # => 3

このようにグリッドであっても有向グラフ化すればコードはほぼ同じになる。

[ABC037 D] 経路

問題を要約する

例1でシミュレーション

実装方針

実装 (AC)

[応用] 最長パスを求める

関連

Discussion