トップ 差分 一覧 ソース 検索 ヘルプ RSS ログイン

AtCoder Beginner Contest 004

[競技プログラミング,競プロ解説]

AtCoder Beginer Contest 004 - D

  解説

マーブルの移動距離はどのようにして出すか?

  • どのマーブルを右に、どのマーブルを左に・・・と考 えるのは非常に面倒!
    • 最後の状態だけ考えて、そこから、その状態にするのに必要な手数を考えたい。
    • 単純に、移動距離を足し算してあげればOK!
  • 動的計画法の場合
    • 適当な4次元配列dpを用意する
    • dp[今見ている場所][赤の残り数][緑の残り数][青の残り 数]
    • これに対して、「この状況になるための最小の移動 数」を格納してあげるような、計算の省略を行う。

  満点解法の解説

(方針) 解説スライドより

  • 動的計画法の場合
    • 適当な2次元配列dpを用意する
    • dp[今見ている場所][マーブルの残り数]
    • これに対して、「この状況になるための最小の移動数」を格納してあげるような、計算の省略を行う。
    • マーブルの残り数に対して、移動量の計算が変わるので注意!

(より具体的な方針) はやくプロになりたい - ABC 004 より

  • dp[pos][remain]を「0からposまでの箱を使ってマーブルを配置したときに必要な最小の移動数」として動的計画法を行う(ただしposは-400を0とするようにずらしてある)
    • 初期化はdp[i][R+G+B]=0、その他は大きい数。
    • 漸化式はdp[i][j] = min(dp[i-1][j], dp[i-1][j+1] + cost(i, j))
    • cost(i, j)はj個残っているときにi番目の箱に入れるための最小の移動数を表す。左から順に入れているので、残りの数によってどの色を入れるのが移動数最小になるのかは一意に定まり、その色の箱の位置とposの差の絶対値が移動量になる。

詳細に

プログラムのデータ仕様
マーブル自体は、(R,G,B) = (4,3,2)と貰っていれば、R,R,R,R,G,G,G,B,Bのように隙間なく並ぶのがマーブルの置き方の最終型のはず 要はその最終型になるように、マーブルの置き方を探索している
  • 動的計画法の表の設定内容について
    • 下記のような表を考える
  • マーブルの最左端を表す数値を行、各マーブルのインデックスを列に取る集計表
    • マーブルの合計値は当然, R+G+B で求められる
i (= pos) \ j (= remain) 0 1 2 3 4 5 6 7 8 9 10
0
1
2
3
...
997
998
999
1000
プログラムの動作仕様
表の動作がけっこうテクニカルな気がする
  • (R,G,B) = (17,2,34) のとき
    • R+G+B = 53

(1) 初期化

  • 全部INFで埋める
  • その後 R+G+B の合計値の列だけ 0埋めする
i (= pos) \ j (= remain) 0 1 2 3 ... 45 46 47 48 49 50 51 52 53 54 55 ... 998 999 1000
0 INF INF INF INF INF INF INF INF INF INF INF INF 0 INF INF INF INF INF INF INF
1 INF INF INF INF INF INF INF INF INF INF INF INF 0 INF INF INF INF INF INF INF
2 INF INF INF INF INF INF INF INF INF INF INF INF 0 INF INF INF INF INF INF INF
3 INF INF INF INF INF INF INF INF INF INF INF INF 0 INF INF INF INF INF INF INF
... INF INF INF INF INF INF INF INF INF INF INF INF 0 INF INF INF INF INF INF INF
997 INF INF INF INF INF INF INF INF INF INF INF INF 0 INF INF INF INF INF INF INF
998 INF INF INF INF INF INF INF INF INF INF INF INF 0 INF INF INF INF INF INF INF
999 INF INF INF INF INF INF INF INF INF INF INF INF 0 INF INF INF INF INF INF INF
1000 INF INF INF INF INF INF INF INF INF INF INF INF 0 INF INF INF INF INF INF INF

(2) 漸化式をもとに表を埋める

  • 漸化式は dp[i][j] = min(dp[i-1][j], dp[i-1][j+1] + cost(i, j)) なので
    • 1行目にて dp[1][53] = min(dp[1-1][53], dp[1-1][53+1] + cost(1,53))
    •       dp[1][53] = min(dp[0][53] , dp[0][54] + 399)
    •       dp[1][53] = min(INF , 399)
    •       dp[1][53] = 399
    • という風に、右から埋まっていく
  • 漸化式の形は01ナップサック問題に近い、01ナップサック問題は dp[i][j] = max(dp[i-1][j], dp[i-1][j-s] + v)

+ クリックで53×615の表を展開

Rubyに落とし込む

lines = $stdin.read
array = lines.split("\n")
 
R,G,B = array[0].split(" ").map(&:to_i)
INF   = 1 << 25
dp    = Array.new(1000).map{ Array.new(1000, 0) }
total = R+G+B
 
def cost(pos, remain)
  if remain >= G+B
    (400-pos).abs
  elsif remain >= B
    (500-pos).abs
  else
    (600-pos).abs
  end
end
 
for i in 0...1000
  for j in 0...1000
    dp[i][j] = INF
  end
end
for i in 0...1000
  dp[i][total] = 0
end
 
for i in 1...1000
  for j in 0...total
    dp[i][j] = [ dp[i-1][j], dp[i-1][j+1] + cost(i,j) ].min
  end
  # p dp[i].take(total)
end
 
ans = INF
for i in 0...1000
  ans = [ans, dp[i][0]].min
end
 
puts ans
atcoder-abc004.png
お名前: コメント: