ABC289 D問題 Step Up Robot

動的計画法の基本問題

$i$ 段目にのぼることが可能かどうかを配列 $dp[i]$ に記録していきます。
ロボットは上にしか進めないので、下の段から順に可能かどうかを確定してゆくことができます。

「 $i$ 段目に到達可能なら、 $i+A_1, i+A_2, \cdots, i+A_N$ 段目に到達可能」
または、
「 $i-A_1, i-A_2, \cdots, i-A_N$ 段目のいずれかに到達可能なら、 $i$ 段目に到達可能」
と考えますが、この問題では $B_i$ 段から先に進めなくなるため、前者の考え方を拡張して、
「 $i$ 段目に到達可能かつ $B_i$ に該当しないなら、 $i+A_1, i+A_2, \cdots, i+A_N$ 段目に到達可能」
としてみます。

コード例 (Julia)

function solve()

  # 入力
  readInts() =  parse.(Int,split(readline()))
  readInt()  =  parse(Int,readline())

  # 入力データ
  N = readInt()
  A = readInts()
  M = readInt()
  B = readInts()
  X = readInt()

  # モチが設置されている段
  mochi = falses(X)
  for i=1:M
    mochi[B[i]] = true
  end

  dp = falses(X)
  # 0段目からの最初の動作でのぼることができる段
  for i=1:N
    if A[i] <= X
      dp[A[i]] = true
    end
  end

  # 下の段から、のぼることができる段の dp を true に設定
  for i=1:X
    if dp[i] && ! mochi[i]
      for j=1:N
        k = i + A[j]
        if k <= X
          dp[k] = true
        end
      end
    end
  end

  # X段目にのぼることができたか
  if dp[X]
    println("Yes")
  else
    println("No")
  end

end  # function solve

# main
solve()