AOJ(問題集)10
AIZU ONLINE JUDGE: Programming Challenge
0091 Blur
L = 10 table = [[[0, 0], [0, 1], [-1, 1], [1, 1], [0, 2], [-1, 2], [-2, 2], [1, 2], [2, 2], [0, 3], [-1, 3], [1, 3], [0, 4]], [[0, 0], [1, 0], [2, 0], [0, 1], [1, 1], [2, 1], [0, 2], [1, 2], [2, 2]], [[0, 0], [0, 1], [-1, 1], [1, 1], [0, 2]]] n = $<.gets.to_i cloth = $<.readlines.map {|l| l.split.map(&:to_i)} copy = ->(ary) { ary.map {|l| l.dup} } form = ->(x, y, i) { case (j = 3 - i) when 1 then "#{x} #{y + 1} #{j}" when 2 then "#{x + 1} #{y + 1} #{j}" when 3 then "#{x} #{y + 2} #{j}" else nil end } try = ->(place, field, co, order = []) { # にじみがあるまでスキップ x = y = nil loop do return false if place >= L * L x, y = place % L, place / L break if field[y][x].nonzero? place += 1 end result = false # 大、中、小の滴を順に試す table.each_with_index do |drip, i| tmp = copy.(field) catch(:jump) do # 滴を試す(適合しなければ大域脱出で次の滴へ) drip.each do |po| x1, y1 = x + po[0], y + po[1] throw(:jump) if x1 < 0 or x1 >= L or y1 >= L or tmp[y1][x1].zero? tmp[y1][x1] -= 1 end # 滴が適合した場合の処理 co -= 1 prc = form.(x, y, i) if co.zero? if tmp.flatten.map(&:zero?).all? return order + [prc] #解が発見された場合(一気にリターン) else co += 1 throw(:jump) end end result = try.(place, tmp, co, order + [prc]) return result if result co += 1 end end result } puts try.(0, cloth, n)
よくこんなのできたな。いまのところ Ruby で解けたのは 5人だけで、タイムは自分が最速。うれしい。
0092 Square Searching
until (n = $<.gets.to_i).zero? field = Array.new(n) {$<.gets.chomp} max = 0 check = ->(x, y, num) { num.times do |i| num.times do |j| return false if x + j >= n or y + i >= n return false if field[y + i][x + j] == "*" end end true } (0...n * n).each do |i| x, y = i % n, i / n (max + 1..n - x).each do |width| max = width if check.(x, y, width) end end puts max end
これだと時間オーバー。ちょっと素朴すぎるか。
高速化に挑戦。チェックをビット演算に切り替える。
until (n = $<.gets.to_i).zero? field = Array.new(n) {$<.gets.chomp} field.map! {|st| eval("0b" + st.gsub(/\./, "0").gsub(/\*/, "1"))} max = 0 n.times do |y| l = field[y] break unless n - y > max (n - y).times do |i| l |= field[y + i] if l.to_s(2).rjust(n, "0").include?("0" * (i + 1)) max = i + 1 if i + 1 > max end end end puts max end
いちおう通ったけれども、3.91秒もかかってしまった。判定時にわざわざ文字列に直しているのがよくないのだけれど。
判定時に文字列を使わないバージョンも作ってみたのだが、余計に遅くなってしまった。正解者の結果を見ると 3.91秒というのは真ん中くらいで、そんなに悪い数字ではなかったようだ。Ruby だとしようがないのね。
0093 Leap Year
stack = [] until (years = $<.gets.split.map(&:to_i)) == [0, 0] is_uruu = ->(year) { (year % 4).zero? and ((year % 100).nonzero? or (year % 400).zero?) } result = (years.first..years.last).map {|i| is_uruu.(i) ? i : nil}.compact result << "NA" if result.empty? stack << result.join("\n") end print stack.join("\n\n") + "\n"
0094 Calculation of Area
a, b = $<.gets.split.map(&:to_i) printf "%.5f\n", a * b / 3.305785
0095 Surf Smelt Fishing Contest
$<.gets data = $<.readlines.map {|l| l.split.map(&:to_i)}.sort_by(&:last) max = data.last.last num = data.select {|a| a.last == max}.sort_by(&:first).first.first puts "#{num} #{max}"
sort_by
を sort
と書くタイポがあって、なかなか気づけなかった。
0096 Sum of 4 Integers II
L = 1000 @memo = {} def doit(s, n = 1) return (s <= L) ? 1 : 0 if n == 4 key = [s, n] return @memo[key] if @memo.has_key?(key) co = 0 a = (s <= L) ? s : L (0..a).each do |i| co += doit(s - i, n + 1) end @memo[key] = co end $<.readlines.map(&:to_i).each do |s| puts doit(s) end
これだと時間オーバー。メモ化はしているのだけれど、もっと工夫しないといけない。
L = 1000 memo = {} f1 = ->(n) {(n ** 3 + 6 * n ** 2 + 11 * n + 6) / 6} f2 = ->(n) {(n ** 2 + 3 * n + 2) / 2} f3 = ->(n) {n + 1} f = ->(s, n) { case n when 1 then f1.(s) when 2 then f2.(s) when 3 then f3.(s) when 4 then 1 else nil end } doit = ->(s, n = 1) { co = 0 return f.(s, n) if s <= L return 0 if n == 4 key = [s, n] return memo[key] if memo.has_key?(key) (0..L).each do |i| co += doit.(s - i, n + 1) end memo[key] = co } $<.readlines.map(&:to_i).each do |s| puts doit.(s) end
これも時間オーバーだが、正しい答えを出すようだ。これがひな型になる。
f1 = ->(n) {(n ** 3 + 6 * n ** 2 + 11 * n + 6) / 6} f2 = ->(n) { n1 = n - 1000 (335337002 + 1004001 * n1 + 998 * n1 ** 2 - n1 ** 3) / 2 } f3 = ->(n) { n1 = n - 2001 (1337336000 - 4002 * n1 - 1999 * n1 ** 2 + n1 ** 3) / 2 } f4 = ->(n) { n1 = n - 3002 (999999000 - 2999999 * n1 + 3000 * n1 ** 2 - n1 ** 3) / 6 } $<.readlines.map(&:to_i).each do |s| result = case s when 0..1000 then f1.(s) when 1001..2001 then f2.(s) when 2002..3002 then f3.(s) when 3003..4000 then f4.(s) end puts result end
ほとんどインチキ。瞬殺である。WolframAlpha に助けを借りたのはナイショ。
他の人の回答。
MAX_SUM = 4000 MAX_I = 1000 K = 4 $sn_cache = Array.new(K + 1) {[]} def check_sum(k, n) unless $sn_cache[k][n] count = 0 max_i = [MAX_I, n].min (0..max_i).each do |i| count += check_sum(k - 1, n - i) end $sn_cache[k][n] = count end $sn_cache[k][n] end $sn_cache[1] = Array.new(MAX_I + 1, 1) + Array.new(MAX_SUM - MAX_I, 0) while (line = gets) n = line.chomp.to_i puts check_sum(K, n) end
これで 0.81秒なのだが、自分の最初の答えとよく似ている。しかし、自分のだと 6.51秒で時間オーバー。どこがちがうのだろう。
わかった、メモ化の際の配列の作り方がちがっているのだ。ハッシュを多重配列に直す。
L = 1000 @memo = Array.new(3) {[]} def doit(s, n = 1) return (s <= L) ? 1 : 0 if n == 4 return @memo[n - 1][s] if @memo[n - 1][s] co = 0 a = (s <= L) ? s : L (0..a).each do |i| co += doit(s - i, n + 1) end @memo[n - 1][s] = co end $<.readlines.map(&:to_i).each do |s| puts doit(s) end
これだけのことで 0.83秒で解けた。うーん、めっちゃ勉強になるなあ。
この最後のコードがいちばん好きだな。
なお、メモ化をハッシュにして、キーを key = "#{s},#{n}"
という感じにしてやってもまあまあいけて、2.25秒で出来た。しかし、数字でいける場合はやはり配列が速いのは当り前か。
0097 Sum of Integers II
L = 100 @memo = Array.new(9) {Array.new(101) {[]}} def solve(num, start, sum) return 0 if sum < 0 or start > L return (start <= sum and sum <= L) ? 1 : 0 if num == 1 a = @memo[num - 1][start][sum] return a if a co = 0 lim = [L, (2 * sum - num ** 2 + num) / (2 * num)].min (start..lim).each do |i| co += solve(num - 1, i + 1, sum - i) end @memo[num - 1][start][sum] = co end until (a = $<.gets.split.map(&:to_i)) == [0, 0] puts solve(a.first, 0, a.last) end
1.11秒かかった。lim を求めるのは少し凝ってみた。lim = [L, sum].min
とやるより少し効率がよい。
0098 Maximum Sum Sequence II
matrix = Array.new(n = $<.gets.to_i) {$<.gets.split.map(&:to_i)} max = -Float::INFINITY memo = {} try = ->(x, y, w, h) { return 0 if x >= n or y >= n or w <= 0 or h <= 0 key = "#{x},#{y},#{w},#{h}" return memo[key] if memo[key] if h == 1 and w == 1 num = matrix[y][x] else try.(x, y + 1, w, h - 1) try.(x, y , w, h - 1) try.(x + 1, y, w - 1, h) try.(x , y, w - 1, h) num = try.(x, y, 1, 1) + try.(x + 1, y, w - 1, 1) + try.(x, y + 1, 1, h - 1) + try.(x + 1, y + 1, w - 1, h - 1) end max = num if num > max memo[key] = num } try.(0, 0, n, n) puts max
メモ化しても時間オーバー。
他の人の回答(参照)を見る。コードは自分の好みに改変してあります。
n = $<.gets.to_i matrix = (1..n).map { $<.gets.split.map(&:to_i) } # 各行の数字を左から加算していった配列 accum = matrix.map {|row| row.inject([0]) {|s, x| s + [s[-1] + x]} } max = 0 [*1..n].repeated_combination(2) do |i, j| sum = 0 (0..n - 1).each do |k| sum += accum[k][j] - accum[k][i - 1] max = sum if sum > max sum = 0 if sum < 0 end end matrix.flatten! puts matrix.any? {|x| x >= 0} ? max : matrix.max
瞬殺。うーん、すごい、これは思いつかなかった。でもあらかじめ数字を加算しておいた配列を作るのいうのは、確かに時々見る手法。
0099 Surf Smelt Fishing Contest II
Node = Struct.new(:key, :value, :left, :right) class Tree def initialize @root = nil end def insert(key, value) unless @root @root = Node.new(key, value) return end node = @root while node if key < node.key if node.left node = node.left else node.left = Node.new(key, value) break end elsif key > node.key if node.right node = node.right else node.right = Node.new(key, value) break end else if block_given? node.value = yield(key, node.value, value) else node.value = value end break end end end def []=(key, value) insert(key, value) end def search(key) node = @root while node if key < node.key node = node.left elsif key > node.key node = node.right else return node end end nil end def [](key) search(key)&.value end def delete(key) delete_min = ->(node) { return node.right unless node.left node.left = delete_min.(node.left) node } search_min = ->(node) { node = node.left while node.left node } del = ->(node) { if node if key == node.key if node.left.nil? return node.right elsif node.right.nil? return node.left else min_node = search_min.(node.right) node.key = min_node.key node.value = min_node.value node.right = delete_min.(node.right) end elsif key < node.key node.left = del.(node.left) else node.right = del.(node.right) end end node } @root = del.(@root) end def maximum search_max = ->(node) { node = node.right while node.right node } raise "error" unless @root node = search_max.(@root) raise "error" unless node node.key end end n, q = $<.gets.split.map(&:to_i) entry = [] fish_num = Hash.new(0) t = Tree.new delete = ->(fish, member) { t[fish] -= [member] t.delete(fish) if t[fish].empty? } q.times do member, fs = $<.gets.split.map(&:to_i) tmp = fish_num[member] fish_num[member] += fs t.insert(fish_num[member], [member]) {|k, v1, v2| v1 + v2} if entry.include?(member) delete.(tmp, member) else entry << member end max_fish = t.maximum puts "#{t[max_fish].sort.first} #{max_fish}" end
惜しい、22課題中21課題までいって時間オーバー(9秒99)。二分探索木を実装して頑張った。しかしこれではダメのようだから、平衡二分探索木を実装しないといけないのか。
いや、シンプルに考え直してみる。
fish = Hash.new(0) max = 0 max_fishers = [] selected_fisher = nil n, q = $<.gets.split.map(&:to_i) q.times do a, v = $<.gets.split.map(&:to_i) fish[a] += v if v > 0 if fish[a] > max max = fish[a] puts "#{a} #{max}" max_fishers = [a] selected_fisher = a elsif fish[a] == max max_fishers << a puts "#{selected_fisher = max_fishers.min} #{max}" else puts "#{selected_fisher} #{max}" end else if fish[a] - v == max if max_fishers.size == 1 max = fish.values.max max_fishers = fish.keys.select {|k| fish[k] == max} puts "#{selected_fisher = max_fishers.min} #{max}" else max_fishers.delete(a) puts "#{selected_fisher = max_fishers.min} #{max}" end else puts "#{selected_fisher} #{max}" end end end