AOJ（問題集）13

AIZU ONLINE JUDGE: Programming Challenge
　

0120 Patisserie

@memo = {}

def length(circles)
  return @memo[circles] if @memo[circles]
  l = case (s = circles.size)
      when 0 then 0
      when 1 then 0
      when 2
        r1, r2 = circles.first, circles.last
        Math.sqrt((r1 + r2) ** 2 - (r1 - r2) ** 2)
      else
        s1 = s / 2
        length(circles[0..s1]) + length(circles[s1..-1])
      end
  @memo[circles] = l
end

$<.readlines.map {|l| l.split.map(&:to_i)}.each do |w, *r|
  minimum = Float::INFINITY
  result = "NA"
  r.permutation do |circles|
    l = circles.first + length(circles) + circles.last
    minimum = [minimum, l].min
    if minimum <= w
      result = "OK"
      break
    end
  end
  puts result
end

時間オーバー。まるで思いつかない。こういうパッキングの問題は決まった解法がないらしい。
他の人の回答を見た。

#!ruby -pal
$c={}
def f l,*a
a[0]?($c[a.sort<<l]||=a.map{f(*a.rotate!)+(4*a[0]*l)**0.5}.min):l
end
m,*r=$F.map &:to_i
$_=r.any?{f(*r.rotate!)+r[0]<=m}?:OK:"NA"

???
読めるように書き直してもわからない。

$c = {}

def f(l, *a)
  if a[0]
    $c[a.sort << l] ||= a.map{ f(*a.rotate!) + (4 * a[0] * l) ** 0.5 }.min
  else
    l
  end
end

while (a = $<.gets)
  m, *r = a.split.map(&:to_i)
  puts r.any? {f(*r.rotate!) + r[0] <= m} ? "OK" : "NA"
end

ははあ、なるほど、並び方の順番は結果に関係なくて、ただ両端のみ関係するのか。そうなのかな。だから rotate でやっているのね。ふーむ、よく考えてみよう。決して自明ではないと思う。
しかしこのコード超すごいな。これでメモ化までやっているとは。圧倒的なコード量の少なさだ。
ちなみにこの問題、Ruby では四人しか正解できていない。
　

0121 Seven Puzzle

A = [*0..7]
memo = {A=>0}

stack = [A + [0]]
check = [A.join.to_i]

while (board = stack.shift)
  swap = ->(a, b) {
    tmp = board.dup
    tmp[a], tmp[b] = tmp[b], tmp[a]
    tmp
  }
  move = case (i = board.index(0))
         when 0 then [1, 4]
         when 1, 2 then [i - 1, i + 1, i + 4]
         when 3 then [2, 7]
         when 4 then [0, 5]
         when 5, 6 then [i - 1, i + 1, i - 4]
         when 7 then [3, 6]
         end
  move.each do |j|
    nxt = swap.(i, j)
    a = nxt[0, 8].join.to_i
    next if check.include?(a)
    nxt[8] += 1
    memo[nxt[0, 8]] = nxt[8]
    check << a
    stack << nxt
  end
end

$<.readlines.map {|a| a.split.map(&:to_i)}.each do |given|
  puts memo[given]
end

2.05秒かかった。最初苦し紛れで書いたのがヒントになった。あらかじめ全パターンを計算しておくという方法。ちなみに全パターンは 20160 通りある。
他の人の回答を参考にして、modify したバージョン。

A = "01234567"
memo = {A=>0}

stack = [[A, 0]]
table = [[1, 4], [0, 2, 5], [1, 3, 6], [2, 7],
         [0, 5], [4, 6, 1], [5, 7, 2], [3, 6]].freeze

while (board = stack.shift)
  swap = ->(a, b) {
    tmp = board.first.dup
    tmp[a], tmp[b] = tmp[b], tmp[a]
    [tmp, board.last]
  }
  i = board.first.index("0")
  table[i].each do |j|
    nxt = swap.(i, j)
    next if memo[nxt.first]
    nxt[1] += 1
    memo[nxt.first] = nxt.last
    stack << nxt
  end
end

$<.readlines.map {|a| a.split.join}.each do |given|
  puts memo[given]
end

これだと 0.16秒。Array を String に替え、冗長な部分を削った（不必要な check[] を無くした）。
　

0122 Summer of Pyonkichi

L = 10
movable = [[-1, -2], [0, -2], [1, -2],
           [-1,  2], [0,  2], [1,  2],
           [-2, -1], [-2, 0], [-2, 1],
           [ 2, -1], [ 2, 0], [ 2, 1]]

until (a = $<.gets.split.map(&:to_i)) == [0, 0]
  px, py = a
  n = $<.gets.to_i
  result = "NA"
  sprinkler = $<.gets.split.map(&:to_i).each_slice(2).to_a
  
  try = ->(x, y, i = 0) {
    if i == n
      result = "OK"
    else
      s = sprinkler[i]
      movable.each do |dx, dy|
        nx = x + dx
        ny = y + dy
        check = ->{
          nx.between?(s[0] - 1, s[0] + 1) && ny.between?(s[1] - 1, s[1] + 1)
        }
        next if nx < 0 or nx >= L or ny < 0 or ny >= L
        try.(nx, ny, i + 1) if check.()
      end
    end
  }
  
  try.(px, py)
  puts result
end

コーディングは楽ではないけれど、バックトラック法とわかっているから助かる。
　

0123 Speed Skating Badge Test

table = [[35.5, 71.0, :AAA], [37.5, 77.0, :AA], [40.0, 83.0, :A], [43.0, 89.0, :B],
         [50.0, 105.0, :C], [55.0, 116.0, :D], [70.0, 148.0, :E]]

$<.readlines.map {|l| l.split.map(&:to_f)}.each do |a, b|
  catch :jump do
    table.each do |ta, tb, cname|
      if a < ta and b < tb
        puts cname
        throw :jump
      end
    end
    puts "NA"
  end
end

ひさしぶりに極簡単。ホッとするなあ。
　

0124 League Match Score Sheet

result = []
until (n = $<.gets.to_i).zero?
  teams = Array.new(n) do
    name, *nums = $<.gets.split
    po = nums.map(&:to_i).zip([3, 0, 1]).inject(0) {|acc, i| acc + i[0] * i[1]}
    [name, po]
  end.sort {|a, b| b[1] <=> a[1]}
  result << teams.map {|a| a.join(",") + "\n"}.join
end
puts result.join("\n")

0125 Day Count

require 'date'

until (a = $<.gets.split.map(&:to_i)).index {|i| i < 0}
  puts (Date.new(*a[3, 3]) - Date.new(*a[0, 3])).to_i
end

標準添付ライブラリを使うというインチキ。
　

0126 Puzzle

数独ソルバではなくて、数独チェッカーみたいなもの。

L = 9
T = L / 3

def check(line)
  co = Hash.new(0)
  line.each {|num| co[num] += 1}
  (0...L).select {|i| co[line[i]] > 1}
end

def square
  L.times {|i| yield(i % T, i / T)}
end

result = []

$<.gets.to_i.times do
  field = Array.new(L) {$<.gets.split.map(&:to_i)}
  marked = []
  
  field.each_with_index do |row, i|
    marked += check(row).map {|j| i * L + j}
  end
  L.times do |i|
    col = Array.new(L) {|j| field[j][i]}
    marked += check(col).map {|k| k * L + i}
  end
  square do |x, y|
    sx, sy = x * T, y * T
    block = Array.new(L) {|i| field[sy + i / T][sx + i % T]}
    marked += check(block).map {|i| (sy + i / T) * L + sx + i % T}
  end
  
  result << field.flatten.map.with_index do |num, i|
    str = (marked.include?(i) ? "*" : " ") + num.to_s
    str + ((i % L == L - 1) ? "\n" : "")
  end.join
end

puts result.join("\n")

意外とむずかしい。というか面倒くさい。
　

0127 Pocket Pager Input

table = {"61"=>"z", "62"=>".", "63"=>"?", "64"=>"!", "65"=>" "}
25.times {|i| table["#{i / 5 + 1}#{i % 5 + 1}"] = (97 + i).chr}

$<.readlines.map(&:chomp).each do |cipher|
  catch :jump do
    text = ""
    i = 0
    while i < cipher.size
      a = table[cipher[i, 2]]
      unless a
        puts "NA"
        throw :jump
      end
      text += a
      i += 2
    end
    puts text
  end
end

0128 Abacus

そろばん。

L = 5
table = Array.new(10) {|i| [i / 5, i % 5]}

r = $<.readlines.map {|l| l.chomp.rjust(L, "0").chars.map(&:to_i)}.map do |given|
  soroban = given.map do |place|
    high, low = table[place]
    ((high.zero? ? "* =" : " *=") + "*" * low + " " + "*" * (4 - low)).chars
  end
  soroban.transpose.map {|l| l.join + "\n"}.join
end.join("\n")

print r

0129 Hide-and-Seek Supporting System

かくれんぼう。

require 'matrix'

until (num = $<.gets.to_i).zero?
  circles = Array.new(num) do
    x, y, r = $<.gets.split.map(&:to_r)
    [Vector[x, y], r]
  end
  
  $<.gets.to_i.times do
    tx, ty, sx, sy = $<.gets.split.map(&:to_r)
    ta  = Vector[tx, ty]
    oni = Vector[sx, sy]
    v = ta - oni
    n = Vector[v[1], -v[0]].normalize
    
    f = circles.map do |o, r|
      pos1 = (oni - o).norm < r
      pos2 = (ta  - o).norm < r
      if pos1 and pos2
        false
      elsif !pos1 and !pos2
        s, t = Matrix.columns([v, -n]).lup.solve(o - oni).to_a
        s.between?(0, 1) and t.abs <= r
      else
        true
      end
    end.any?
    
    puts f ? "Safe" : "Danger"
  end
end

1.28秒かかった。他の人は瞬殺だけれど、それでも Ruby で解けているのは 3人しかいませんよ。自慢自慢。