AtCoder Beginner Contest 005

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

AtCoder Beginer Contest 005 - D

• AtCoder Beginer Contest 005 - D おいしいたこ焼きの焼き方
  • 四角形の中身を任意の大きさの長方形に分けて、その中身を合計しておく
  • また動的計画法みたいです

  解説

• AtCoder Beginner Contest 005 解説

• 参考サイト
  • 競技プログラミングをするんだよ - ABC#005

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

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

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

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

各長方形を全通り列挙する O(n^4)

長方形をすべて列挙？ここをまずどうするか、とりあえず 0...N までの配列を２つ用意してそれぞれに対して組み合わせを求めてみる

width  = (0...N).to_a
height = (0...N).to_a

width.combination(2) do |w|
  height.combination(2) do |h|
    puts "width: #{w}, height: #{h}"
  end
end

width: [0, 1], height: [0, 1]
width: [0, 1], height: [0, 2]
width: [0, 1], height: [1, 2]
width: [0, 2], height: [0, 1]
width: [0, 2], height: [0, 2]
width: [0, 2], height: [1, 2]
width: [1, 2], height: [0, 1]
width: [1, 2], height: [0, 2]
width: [1, 2], height: [1, 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 の領域をすべて探索して、連想配列に領域面積＝１の場合の最大値を格納する
  • 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