AtCoder Beginer Contest 005 - D
- 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