ARC087 D: FT Robot

arc087.contest.atcoder.jp

解き方

  • 以下の2つを前計算する
    • x方向に動ける距離:x_0, x_1, ..., x_n
    • y方向に動ける距離:y_0, y_1, ..., y_n
  • 以下のdpを埋める
    • dp[a] := x座標の絶対値をaとすることができる最大の移動回数
  • 同様にyも埋めて、dp[x] = n, dp[y] = nとなるかで判定
  • 移動は正方向、負方向どちらにも動いてよいが、最初のx_0だけは正方向にしか動けないので、座標変換する

github.com