AtCoder Beginner Contest 005

1年超の間を空けて取り組んだD問題がやっと解けたので、とりあえずソースコードだけ記しておきます。

abc005.contest.atcoder.jp

www.slideshare.net

A - おいしいたこ焼きの作り方

x, y = gets.split.map(&:to_i)
puts y / x

B - おいしいたこ焼きの食べ方

n = gets.to_i
t = []
n.times { t << gets.to_i }
puts t.min

C - おいしいたこ焼きの売り方

t = gets.to_i
n = gets.to_i
a = gets.split.map(&:to_i)
m = gets.to_i
b = gets.split.map(&:to_i)
if n < m
  puts 'no'
  exit
end
res = 0
b.each do |_b|
  a.each_with_index do |_a, i|
    if _a <= _b && _b - t <= _a
      res += 1
      a.slice!(0..i)
      break
    end
  end
end
puts res == m ? 'yes' : 'no'

D - おいしいたこ焼きの焼き方

def maximize_score
    # 各マスの右下までの面積を求める
    (@N - 1).downto(0) {|x|
        (@N - 1).downto(0) {|y|
            @to_bottom_right[y][x] = @D[y][x] + @to_bottom_right[y][x + 1] \
            + @to_bottom_right[y + 1][x] - @to_bottom_right[y + 1][x + 1]
        }
    }
    # 幅・高さ・x座標・y座標ごとに定めた長方形内の合計値を求める
    1.upto(@N) {|w|
        1.upto(@N) {|h|
            0.upto(@N - 1) {|x|
                break if x + w > @N 
                0.upto(@N - 1) {|y|
                    break if y + h > @N 
                    tmp = @to_bottom_right[y][x] - @to_bottom_right[y + h][x] \
                    - @to_bottom_right[y][x + w] + @to_bottom_right[y + h][x + w]
                    @max_each_area[h * w] = [tmp, @max_each_area[h * w]].max
                }
            }
        }
    }
end
 
@N = gets.to_i
@D = []
@N.times{ @D << gets.split.map(&:to_i) }
@Q = gets.to_i
@P = []
@Q.times{ @P << gets.to_i }
 
@max_each_area = Array.new(@N * @N + 1, 0)
@to_bottom_right = Array.new(@N + 1){ Array.new(@N + 1, 0) }
 
maximize_score
@P.each {|p| puts @max_each_area[0..p].max }