AOJ（問題集）18

AIZU ONLINE JUDGE: Programming Challenge
　

0170 Lunch

until (n = $<.gets.to_i).zero?
  data = n.times.map {$<.gets.split}.map {|a, *b| [a] + b.map(&:to_i)}
  selected = []
  all = [*0...n]
  
  solve = ->(left, order) {
    return if data[order.last][2] < (all - order).map {|i| data[i][1]}.sum
    if left.empty?
      selected << order
    else
      left.each {|i| solve.(left - [i], order + [i])}
    end
  }
  all.each {|i| solve.(all - [i], [i])}
  
  result = selected.sort_by do |order|
    w = order.map {|i| data[i][1]}
    [*1..order.size].zip(w).map {|a, b| a * b}.sum / w.sum.to_f
  end.first
  puts result.map {|i| data[i][0]}
end

3.74秒。バックトラック法。もっといい方法があるらしい。検索してみても C++ とかの奴らは全然参考にならない。
また tnakao さんの回答を見る。驚愕。とりあえず（自己流に書き直して）コードを掲載してみる。

until (n = io.gets.to_i).zero?
  data = n.times.map {io.gets.split}.map {|a, *b| [a] + b.map(&:to_i)}
  wsum0 = data.map {|a| a[1]}.sum
  
  memo = []
  check = ->(bits, wsum) {
    return memo[bits] if memo[bits]
    return [0, []] if bits.zero?
    min_gw = Float::INFINITY
    min_ids = []
    
    n.times do |i|
      b = 1 << i
      if (bits & b).nonzero?
        name, w, s = data[i]
        if s >= wsum - w
          gw0, ids0 = check.(bits & ~b, wsum - w)
          gw = gw0 + wsum
          if gw < min_gw
            min_gw = gw
            min_ids = [i] + ids0
          end
        end
      end
    end
    memo[bits] = [min_gw, min_ids]
  }
  gw, ids = check.((1 << n) - 1, wsum0)
  
  puts ids.map {|i| data[i][0]}
end

なるほど、最後からやっていくわけか…。(n - 1) 個の場合の min を求めておいて、n 個の min を出す。動的計画法だな。これは思いつかなかった。すごい。
　

0171 Dice Puzzle

table = 
[[1, 2, 3, 4, 5, 6], [4, 2, 1, 6, 5, 3], [2, 6, 3, 4, 1, 5], [5, 1, 3, 4, 6, 2],
 [3, 2, 6, 1, 5, 4], [1, 3, 5, 2, 4, 6], [1, 4, 2, 5, 3, 6], [6, 2, 4, 3, 5, 1],
 [2, 3, 1, 6, 4, 5], [5, 4, 1, 6, 3, 2], [4, 1, 5, 2, 6, 3], [4, 6, 2, 5, 1, 3],
 [6, 5, 3, 4, 2, 1], [3, 6, 5, 2, 1, 4], [2, 4, 6, 1, 3, 5], [3, 1, 2, 5, 6, 4],
 [5, 3, 6, 1, 4, 2], [1, 5, 4, 3, 2, 6], [2, 1, 4, 3, 6, 5], [5, 6, 4, 3, 1, 2],
 [6, 4, 5, 2, 3, 1], [6, 3, 2, 5, 4, 1], [3, 5, 1, 6, 2, 4], [4, 5, 6, 1, 2, 3]]
Table = table.map {|i| i.map(&:pred)} 
Dirs = [[2, 4, 5], [1, 2, 5], [3, 4, 5], [1, 3, 5],
        [2, 4, 0], [1, 2, 0], [3, 4, 0], [1, 3, 0]]
Touch = [[2, 1, 4], [0, 3, 5], [0, 3, 6], [2, 1, 7],
         [6, 5, 0], [4, 7, 1], [4, 7, 2], [6, 5, 3]]

def each_position(dice, d_num)
  Dirs[d_num].each do |fix_po|
    Table.select {|od| od[fix_po] == fix_po}.each do |order|
      yield order.map {|i| dice[i]}
    end
  end
end

until (s = $<.gets.chomp) == "0"
  dices = [s.chars]
  7.times {dices << $<.gets.chomp.chars}
  ok = false
  
  try = ->(cube, memo, d_num) {
    if d_num == 8
      ok = true
    else
      ([*0..7] - cube).each do |nxt|
        each_position(dices[nxt], d_num) do |d1|
          f = Dirs[d_num].map.with_index do |dir, i|
            d2 = memo[Touch[d_num][i]]
            next unless d2
            d1[dir] == d2[5 - dir].swapcase
          end.compact.all?
          try.(cube + [nxt], memo + [d1], d_num + 1) if f
        end
      end
    end
  }
  Table.each {|order| try.([0], [order.map {|j| dices[0][j]}], 1)}
  
  puts ok ? "YES" : "NO"
end

42秒で時間オーバー。
　

0173 Haunted House

9.times do
  name, a, b = $<.gets.split
  a, b = a.to_i, b.to_i
  puts "#{name} #{a + b} #{200 * a + 300 * b}"
end

0174 Badminton

until (rec = $<.gets.chomp) == "0"
  record = rec.chars.drop(1)
  a = b = 0
  loop do
    (record.shift == "A") ? a += 1 : b += 1
    if record.empty?
      (a > b) ? a += 1 : b += 1
      break
    end
  end
  puts "#{a} #{b}"
end

0175 Quaternary Notation

until (n = $<.gets.to_i) == -1
  puts n.to_s(4)
end

Ruby 楽すぎるな。
　

0176 What Color?

table = %w(black blue lime aqua red fuchsia yellow white)

until (rgb = $<.gets.chomp) == "0"
  color = rgb[1..-1].chars.each_slice(2).map {|a| a.join.to_i(16)}
  idx = [0, 0xff].repeated_permutation(3).map.with_index do |tc, i|
    [3.times.map {|i| (tc[i] - color[i]) ** 2}.sum, i]
  end.sort.first.last
  puts table[idx]
end

ちょっと Ruby らしく圧縮しすぎて却ってわかりにくいかも。
　

0177 Distance Between Two Cities

require 'matrix'
include Math

R = 6378.1

until (given = $<.gets.split.map(&:to_f)) == [-1] * 4
  a, b, c, d = given.map {|i| i / 180 * PI}
  rot = ->(θ, n) {
    vx = [cos(θ) + n[0] * n[0] * (1 - cos(θ)),
          n[0] * n[1] * (1 - cos(θ)) - n[2] * sin(θ),
          n[2] * n[0] * (1 - cos(θ)) + n[1] * sin(θ)]
    vy = [n[0] * n[1] * (1 - cos(θ)) + n[2] * sin(θ),
          cos(θ) + n[1] * n[1] * (1 - cos(θ)),
          n[1] * n[2] * (1 - cos(θ)) - n[0] * sin(θ)]
    vz = [n[2] * n[0] * (1 - cos(θ)) - n[1] * sin(θ),
          n[1] * n[2] * (1 - cos(θ)) + n[0] * sin(θ),
          cos(θ) + n[2] * n[2] * (1 - cos(θ))]
    Matrix[vx, vy, vz]
  }
  calc = ->(θ, φ) {
    po = Vector[1, 0, 0]
    po = rot.(θ, [0, 0, 1]) * po
    n = po.cross(Vector[0, 0, 1])
    rot.(φ, n) * po
  }
  
  x1 = calc.(b, a)
  x2 = calc.(d, c)
  c = (x1 + x2) / 2
  θ = atan2((x1 - c).norm, c.norm) * 2
  puts (R * θ).round
end

Ruby 便利だ…。
　

0178 TETORIS

テトリス。

W = 5

until (n = $<.gets.to_i).zero?
  field = []
  
  n.times do
    d, p, q = $<.gets.split.map(&:to_i)
    if d == 1
      block = ((1 << p) - 1) << W + 1 - p - q
      if field.empty?
        field = [block]
      else
        i = field.size - 1
        while (field[i] & block).zero?
          i -= 1
          break if i < 0
        end
        i += 1
        field[i] ||= 0
        field[i] |= block
      end
    else
      block = 1 << W - q
      if field.empty?
        p.times {field.push(block)}
      else
        i = field.size - 1
        while (field[i] & block).zero?
          i -= 1
          break if i < 0
        end
        p.times do
          i += 1
          field[i] ||= 0
          field[i] |= block
        end
      end
    end
    
    field.delete_at(i) while (i = field.index(31))
  end
  
  puts field.map {|a| a.to_s(2)}.join.count("1") 
end

圧倒的に速いですぞ、これは。
　

0179 Mysterious Worm

color = %w(r g b)

until (worm = io.gets.chomp) == "0"
  queue = [[worm, 0]]
  appear = [worm]
  catch :jump do
    while (worm = queue.shift)
      worm, t = worm.first.chars, worm.last
      if color.map {|c| worm.all? {|a| a == c}}.any?
        puts t
        throw :jump
      else
        (worm.size - 1).times do |i|
          tmp = worm.dup
          next if tmp[i] == tmp[i + 1]
          c = (color - [tmp[i], tmp[i + 1]]).first
          tmp[i] = c
          tmp[i + 1] = c
          tmp = tmp.join
          next if appear.include?(tmp)
          appear << tmp
          queue << [tmp, t + 1]
        end
      end
    end
    puts "NA"
  end
end

幅優先探索なのだけれど、42秒で時間オーバー。
他の人の回答を見る。

table = {"rg"=>"bb", "gr"=>"bb", "gb"=>"rr", "bg"=>"rr", "br"=>"gg", "rb"=>"gg"}

neighbours = ->(worm) {
  len = worm.length
  result = []
  c0 = worm[0]
  
  (1...len).each do |i|
    c = worm[i]
    pair = c0 + c
    if table[pair]
      worm0 = worm.dup
      worm0[i - 1, 2] = table[pair]
      result << worm0
    end
    c0 = c
  end
  result
}

until (worm = $<.gets.strip) == "0"
  queue = [worm]
  dists = {worm => 0}
  dist = "NA"
  
  n = worm.length
  goal = ["r" * n, "g" * n, "b" * n]
  
  while (worm = queue.shift)
    if goal.include?(worm)
      dist = dists[worm]
      break
    end
    
    neighbours.(worm).each do |worm0|
      unless dists[worm0]
        dists[worm0] = dists[worm] + 1
        queue << worm0
      end
    end
  end
  
  puts dist
end

これだと 0.85秒でクリア。考え方は自分のとそんなにちがわない。何がちがうのかな。シンプルさがちがうのだな。
これを参考に、自分のを書き直してみる。

table = {"rg"=>"bb", "gr"=>"bb", "gb"=>"rr", "bg"=>"rr", "br"=>"gg", "rb"=>"gg"}

until (worm = $<.gets.chomp) == "0"
  queue = [worm]
  dist = {worm => 0}
  n = worm.size
  catch :jump do
    while (worm = queue.shift)
      goal = ["r" * n, "g" * n, "b" * n]
      if goal.include?(worm)
        puts dist[worm]
        throw :jump
      else
        (n - 1).times do |i|
          tmp = worm.dup
          pair = worm[i, 2]
          next unless table[pair]
          tmp[i, 2] = table[pair]
          next if dist[tmp]
          dist[tmp] = dist[worm] + 1
          queue << tmp
        end
      end
    end
    puts "NA"
  end
end

これだと 0.77秒でクリア。うーん、勉強になるなあ。