ABC291 F問題 Teleporter and Closed off

atcoder.jp

通れない都市があるという制約を考えないとき

移動は一方向で逆方向には進まないため、番号が小さな都市から順に「都市1から都市iに移動するまでのテレポート回数の最小値」を決定する動的計画法が使えます。
都市 i から 都市 i+k に直接移動可能であれば、
　dp[i+k] = min(dp[i+k], dp[i] + 1)
と、最小値を更新する計算を進めていきます。

通れない都市があるという制約

に対して都市 k を通らずに都市 1 から 都市 N へ移動することが求められています。
k の値ごとに動的計画法の計算をすると時間がかかるため、工夫が必要です。

都市1からだけでなく、都市Nから逆方向に「都市iから都市Nに移動するまでのテレポート回数の最小値」dp2 を求めておきます。

都市 i から 都市 i+k に直接移動可能であれば、この移動を含んだ都市1から都市Nに移動するまでのテレポート回数の最小値は、
dp[i] + 1 + dp2[i+k]
になります。
この移動は、 i+1, i+2,...,i+k-1 の都市を通らない移動です。
直接移動できる都市のペアについてのループを回して、テレポート回数の最小値を更新していくと、答えが求められます。

コード例 (Julia)

function solve()

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

  N,M = readInts()

  BIG = N+1   # 大きな数で初期化して、そのまま変わらければ到達不可能と判断する

  S = Vector{String}(undef,N)

  teleport = falses(N,M)

  for i=1:N
    S[i] = readline()
    for j=1:M
      if S[i][j] == '1'
        teleport[i,j] = true
      end
    end
  end

  # 都市 1 からの最小移動回数

  dp_forward = fill(BIG,N)

  dp_forward[1] = 0

  for i=1:N-1
    for j=1:M
      if i+j > N
        continue
      end
      if teleport[i,j]
        if dp_forward[i+j] > dp_forward[i] + 1
           dp_forward[i+j] = dp_forward[i] + 1
        end
      end
    end
  end


  # 都市 N までの最小移動回数

  dp_backward = fill(BIG,N)

  dp_backward[N] = 0

  for i=N:-1:1
    for j=1:M
      if i-j < 1
        continue
      end
      if teleport[i-j,j]
        if dp_backward[i-j] > dp_backward[i] + 1
           dp_backward[i-j] = dp_backward[i] + 1
        end
      end
    end
  end


  # 途中の都市を通過しないときの最小移動回数

  ans = fill(BIG,N)

  for i=1:N-1
    for j=2:M
      if i+j > N
        continue
      end
      if teleport[i,j]
        # 都市 i から 都市 i+j に直接移動するときの都市1から都市Nまでの最小移動回数
        p = dp_forward[i] + dp_backward[i+j] + 1

        # この移動でスキップする都市について、最小移動回数を更新
        for k = i+1:i+j-1
          if ans[k] > p
             ans[k] = p
          end
        end
      end
    end
  end

  for k = 2:N-1
    if ans[k] == BIG
      # 到達不可能
      print(-1)
    else
      print(ans[k])
    end
    if k < N-1
      print(" ")
    end
  end
  println()

end  # function solve

# main
solve()