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

AtCoder Beginner Contest 005

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

AtCoder Beginer Contest 005 - D

  解説

領域(長方形)ごとの最大の美味しさ度はどうやって求めるか?

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

  • 右下まで必ず使う長方形を全通り列挙する O(n^2)
    • その長方形の美味しさの合計を列挙する O(1)
  • 各長方形を全通り列挙する O(n^4)
    • その長方形の美味しさの合計を列挙する O(1)

全てのたこ焼きの数に対して、最大値が求められる

各長方形を全通り列挙する O(n^4)
長方形をすべて列挙?ここをまずどうするか、とりあえず 0...N までの配列を2つ用意してそれぞれに対して組み合わせを求めてみる

+ サンプルコード

右下まで必ず使う長方形を全通り列挙する O(n^2)
N-1を先に含ませておいて、それ以外を選んでくる

なんか、具体的な動的計画法の式が解説にないぞい!困るぞい!

  満点解法の解説

(具体的な方針) 競技プログラミングをするんだよ - ABC#005 より

  • 典型的な領域分割?分割統治?の問題です。子問題を解くことで大問題を解くことができ全パターンを高速に計算できます。
    • dp[i][j][w][h] を座標(i~i+w,j~j+h)の領域で焼いたときのたこ焼きのおいしさの合計と定義する
  • hについて
    • h の取りうる値は N-i までのはず
    • dp[i][j][0][h] = dp[i][j][0][h-1] + dp[i+h][j][0][0] ( 0 < h < N-i )
  • wについて
    • w の取りうる値は N-j までのはず
    • dp[i][j][w][h] = dp[i][j][w-1][h] + dp[i][j+w][0][h] ( 0 < w < N-j )

(手順)

  • 領域の最大値を保持する連想配列 max_v を用意する、KEYが領域の面積でVALが領域の価値(おいしさ)の合計値
  • 1 x 1 の領域をすべて探索して、連想配列に領域面積=1の場合の最大値を格納する
    • O(N ^ 2)
  • 1 x h, 1 x w の領域をすべて探索して、連想配列に領域面積=1 x h, 1 x wの場合の最大値を格納する
    • O(N ^ 2)
  • h x w の領域をすべて探索して、連想配列に領域面積=h x wの場合の最大値を格納する
    • O(N ^ 4)
lines = $stdin.read
array = lines.split("\n")
 
N = array[0].to_i
D = array[1..N].map{|s| s.split(" ").map(&:to_i)}
Q = array[N+1].to_i
P = array[N+2..Q+N+1].map(&:to_i)
 
I = J = W = H = N
 
dp = Array.new(I).map{
  Array.new(J).map{
    Array.new(W).map{
      Array.new(H, 0)
    }
  }
}
 
max_v = {}
 
for i in 0..N-1
  for j in 0..N-1
    dp[i][j][0][0] = D[i][j]
    max_v[1] = dp[i][j][0][0] if max_v[1].to_i < dp[i][j][0][0]
  end
end
 
for i in 0..N-1
  for j in 0..N-1
    for h in 1...N-i
      dp[i][j][0][h] = dp[i][j][0][h-1] + dp[i+h][j][0][0]
      max_v[h+1] = dp[i][j][0][h] if max_v[h+1].to_i < dp[i][j][0][h]
      #puts "dp[#{i}][#{j}][0][#{h}] = #{dp[i][j][0][h]}"
    end
    for w in 1...N-j
      dp[i][j][w][0] = dp[i][j][w-1][0] + dp[i][j+w][0][0]
      max_v[w+1] = dp[i][j][w][0] if max_v[w+1].to_i < dp[i][j][w][0]
      #puts "dp[#{i}][#{j}][#{w}][0] = #{dp[i][j][w][0]}"
    end
  end
end
 
 
for i in 0..N-1
  for j in 0..N-1
    for h in 1...N-i
      for w in 1...N-j
        dp[i][j][w][h] = dp[i][j][w-1][h] + dp[i][j+w][0][h]
        max_v[(w+1)*(h+1)] = dp[i][j][w][h].to_i if max_v[(w+1)*(h+1)].to_i < dp[i][j][w][h].to_i
        #puts "dp[#{i}][#{j}][#{w}][#{h}] = #{dp[i][j][w][h]}"
      end
    end
  end
end
 
P.each do |ps|
   puts max_v.select{|k,v| k <= ps}.max_by{|k,v| v}.last
end
お名前: コメント: