AtCoder（AtCoder Beginners Selection）

AtCoder Beginners Selection - AtCoder
　

PracticeA - はじめてのあっとこーだー（Welcome to AtCoder）

a = gets.to_i
b, c = gets.split.map(&:to_i)
s = gets
 
print "#{a + b + c} #{s}"

ABC086A - Product

a, b = gets.split.map(&:to_i)
puts (a * b).odd? ? "Odd" : "Even"

ABC081A - Placing Marbles

puts gets.chomp.count("1")

ABC081B - Shift only

def calc(ary, co)
  return co unless ary.all?(&:even?)
  calc(ary.map {|i| i / 2}, co + 1)
end

gets
given = gets.split.map(&:to_i)
puts calc(given, 0)

ABC087B - Coins

table = [500, 100, 50]
coins = 3.times.map {gets.to_i}
x = gets.to_i
memo = Array.new(4) {[]}

try = ->(i, yen) {
  return memo[i][yen] if memo[i][yen]
  return 1 if yen.zero?
  return 0 if i >= 3
  co = 0
  (0..coins[i]).each do |n|
    yen1 = yen - table[i] * n
    break if yen1 < 0
    co += try.(i + 1, yen1)
  end
  memo[i][yen] = co
}
puts try.(0, x)

ABC083B - Some Sums

n, a, b = gets.split.map(&:to_i)
puts (1..n).select {|i| i.to_s.bytes.map {|b| b - 48}.inject(&:+).between?(a, b)}
           .inject(&:+)

ABC088B - Card Game for Two

n = io.gets.to_i
cards = io.gets.split.map(&:to_i).sort
diff = 0

(0...n).each do |i|
  if i.even?
    diff += cards[n - 1 - i]
  else
    diff -= cards[n - 1 - i]
  end
end
puts diff

ABC085B - Kagami Mochi

n = gets.to_i
puts n.times.map {gets.to_i}.uniq.size

ABC085C - Otoshidama

n, y = gets.split.map(&:to_i)

limit1 = [y / 10000, n].min
(0..limit1).each do |b1|
  yen1 = y - 10000 * b1
  limit2 = [yen1 / 5000, n - b1].min
  (0..limit2).each do |b2|
    b3 = n - b1 - b2
    if yen1 == 5000 * b2 + 1000 * b3
      puts "#{b1} #{b2} #{b3}"
      exit
    end
  end
end
puts "-1 -1 -1"

これで 0.216秒。
よりよい方法がよく考えたらわかった。

n, y = gets.split.map(&:to_i)

limit1 = [y / 10000, n].min
(0..limit1).each do |b1|
  x = y / 1000 - n - 9 * b1
  if x >= 0 and (x % 4).zero?
    b2 = x / 4
    b3 = n - b1 - b2
    if b3 >= 0 and 10000 * b1 + 5000 * b2 + 1000 * b3 == y
      puts "#{b1} #{b2} #{b3}"
      exit
    end
  end
end
puts "-1 -1 -1"

これで 0.009秒。
　

ABC049C - 白昼夢 / Daydream

table = %w(dream dreamer erase eraser).map(&:reverse)
s = gets.chomp.reverse
result = "YES"

until s.length.zero?
  catch :jump do
    table.each do |word|
      n = word.length
      if s[0, n] == word
        s = s[n..-1]
        throw :jump
      end
    end
    result = "NO"
    s = ""
  end
end
puts result

ABC086C - Traveling

n = gets.to_i
plans = n.times.map {gets.split.map(&:to_i)}

f = plans.all? do |t, x, y|
  d = x.abs + y.abs
  if t < d
    false
  else
    t.odd? ? d.odd? : d.even?
  end
end
puts f ? "Yes" : "No"

AOJ（問題集）19

AIZU ONLINE JUDGE: Programming Challenge
　

0180 Demolition of Bridges

until (given = $<.gets.split.map(&:to_i)) == [0, 0]
  n, m = given
  bridges = m.times.map {$<.gets.split.map(&:to_i)}.sort_by(&:last)
  city = Array.new(n, false)
  city[0] = true
  appearance = 1
  total_cost = 0
  
  while appearance < n
    bridges.each_index do |i|
      a, b, cost = bridges[i]
      if city[a] or city[b]
        if !city[a]
          city[a] = true
          appearance += 1
          total_cost += cost
        elsif !city[b]
          city[b] = true
          appearance += 1
          total_cost += cost
        end
        bridges.delete_at(i)
        break
      end
    end
  end
  
  puts total_cost
end

「0072 Carden Lantern」とほぼ同じ問題（最小全域木を求める）。ここで使ったのは「プリム法」というらしい。
　

0181 Bookshelf

Limit = 1500000

until (given = $<.gets.split.map(&:to_i)) == [0, 0]
  m, n = given
  book = n.times.map {$<.gets.to_i}
  narrowest = Limit
  pool = []
  
  try = ->(from, h, pool) {
    return if !pool.empty? and pool.last > narrowest
    if h > m
      if from == n
        a = pool.max
        narrowest = a if a < narrowest
      end
    else
      width = 0
      (from...n).each do |i|
        width += book[i]
        try.(i + 1, h + 1, pool + [width])
      end
      if narrowest == Limit
        a = pool.max
        narrowest = a if a < narrowest
      end
    end
  }
  try.(0, 1, [])
  puts narrowest
end

7.73秒で時間オーバー。

until (given = $<.gets.split.map(&:to_i)) == [0, 0]
  m, n = given
  books = n.times.map {$<.gets.to_i}
  smallest = 1500000
  m = n if n < m
  
  if m == 1
    puts books.sum
    next
  end
  
  [*1..n - 1].combination(m - 1) do |sep|
    i = 0
    shelf = []
    sep.each do |j|
      shelf << books[i...j]
      i = j
    end
    shelf << books[i..-1]
    
    len = shelf.map {|a| a.sum}.max
    smallest = len if len < smallest
  end
  puts smallest
end

10秒で時間オーバー。
他の人の回答を見る。

Limit = 1500000

until (given = $<.gets.split.map(&:to_i)) == [0, 0]
  m, n = given
  books = n.times.map {$<.gets.to_i}
  memo = Array.new(m + 1) {[]}
  
  shelf = ->(h, from) {
    return 0 if from >= n
    return memo[h][from] if memo[h][from]
    
    if h == 1
      width = books[from...n].sum
      return memo[h][from] = width
    end
    
    narrowest = Limit
    width = 0
    to = n - h + 1
    
    (from..to).each do |i|
       width1 = shelf.(h - 1, i)
       wider = [width, width1].max
       narrowest = wider if narrowest > wider
       
       width += books[i]
       break if narrowest <= width
    end
    memo[h][from] = narrowest
  }
  
  puts shelf.(m, 0)
end

0.06秒ですよ。すごいなあ。
いやこれ、2分探索の典型的な問題なのだった。

Limit = 1500000

until (given = $<.gets.split.map(&:to_i)) == [0, 0]
  m, n = given
  books = n.times.map {$<.gets.to_i}
  
  f = ->(width) {
    need = 1
    sum = 0
    books.each do |book|
      return false if book > width
      sum += book
      if sum > width
        need += 1
        sum = book
      end
    end
    need <= m    
  }
  
  l = 1
  r = Limit
  
  while l <= r
    mid = l + (r - l) / 2
    if !f.(mid)
      l = mid + 1
    else
      r = mid - 1
    end
  end
  puts l
end

0.04秒で正解なのだが、バグって死んだ。「まめめも」参照。2分探索超むづかしい。
Ruby の組み込みメソッドを使ってみた。

Limit = 1500000

until (given = $<.gets.split.map(&:to_i)) == [0, 0]
  m, n = given
  books = n.times.map {$<.gets.to_i}
  
  f = ->(width) {
    need = 1
    sum = 0
    books.each do |book|
      return false if book > width
      sum += book
      if sum > width
        need += 1
        sum = book
      end
    end
    need <= m    
  }
  puts (1..Limit).bsearch {|width| f.(width)}
end

0183 Black-and-White

loop do
  board = Array.new(3)
  break if (board[0] = $<.gets.chomp) == "0"
  board[1] = $<.gets.chomp
  board[2] = $<.gets.chomp
  
  check = ->(c) {
    gl = c * 3
    return true if board.map {|b| b == gl}.any?
    return true if 3.times.map {|i| board.map {|b| b[i]}.join == gl }.any?
    return true if board[0][0] + board[1][1] + board[2][2] == gl 
    return true if board[0][2] + board[1][1] + board[2][0] == gl
    false
  }
  str = case
        when check.("b") then "b"
        when check.("w") then "w"
        else "NA"
        end
  puts str
end

0184 Tsuruga Castle

table = 6.times.map {|i| [i * 10, (i + 1) * 10 - 1]} + [[60, 120]]

until (n = $<.gets.to_i).zero?
  count = Array.new(7, 0)
  n.times.map {$<.gets.to_i}.each do |age|
    idx = table.index {|a, b| age.between?(a, b)}
    count[idx] += 1
  end
  puts count
end

0185 Goldbach's Conjecture II

N = 1000000

sieve = [*0..N]
2.upto(Math.sqrt(N).to_i) do |i|
  next if sieve[i].zero?
  2.upto(N / i) {|j| sieve[i * j] = 0}
end
sieve = sieve[2..-1].reject {|x| x.zero?}

def prime?(n)
  return false if n < 2
  return true  if n == 2 or n == 3
  return false if (n % 2).zero? or (n % 3).zero?
  i, step = 5, 2
  guard = Math.sqrt(n).to_i
  while i <= guard
    return false if (n % i).zero?
    i += step
    step = 6 - step
  end
  true
end

until (n = $<.gets.to_i).zero?
  co = 0
  i = 0
  loop do
    a = sieve[i]
    break if a > n / 2
    co += 1 if prime?(n - a)
    i += 1
  end
  puts co
end

1.49秒かかった。標準添付ライブラリの Prime クラスを使うより高速な素数判定をしている。
さらに高速に。うまくエラトステネスの篩を使えばもっと速い。

N = 1000000

sieve = Array.new(N + 1, 0)
2.upto(Math.sqrt(N).to_i) do |i|
  next if sieve[i].nonzero?
  2.upto(N / i) {|j| sieve[i * j] = 1}
end

num = (2..N).select {|i| sieve[i].zero?}

until (n = $<.gets.to_i).zero?
  co = 0
  num.each do |a|
    b = n - a
    break if a > b
    co += 1 if sieve[b].zero?
  end
  puts co
end

これで 0.26秒。
　

0186 Aizu Chicken

until (given = $<.gets.split.map(&:to_i)) == [0]
  q1, b, c1, c2, q2 = given
  limit = [q2, b / c1].min
  str = "NA"
  limit.downto(1) do |aizu|
     tori = (b - aizu * c1) / c2
     if tori >= 0 and aizu + tori >= q1
       str = "#{aizu} #{tori}"
       break
     end
  end
  puts str
end

これ、簡単そうなのにわからなかった。ここを参考にした。
　

0187 Stoning Fortune

require 'matrix'

def cross(x1, y1, x2, y2, x3, y3, x4, y4)
  a = Matrix[[x2 - x1, x3 - x4], [y2 - y1, y3 - y4]].lup.solve([x3 - x1, y3 - y1]) rescue nil
  return false unless a
  s, t = a[0], a[1]
  f = ((0 <= s and s <= 1) and (0 <= t and t <= 1))
  f ? Vector[x1 + s * (x2 - x1), y1 + s * (y2 - y1)] : false
end

until (given = $<.gets.split.map(&:to_i)) == [0] * 4
  x, y = [], []
  x[0], y[0], x[1], y[1] = given
  x[2], y[2], x[3], y[3] = $<.gets.split.map(&:to_i)
  x[4], y[4], x[5], y[5] = $<.gets.split.map(&:to_i)
  p1 = cross(x[0], y[0], x[1], y[1], x[2], y[2], x[3], y[3]) 
  p2 = cross(x[2], y[2], x[3], y[3], x[4], y[4], x[5], y[5]) 
  p3 = cross(x[4], y[4], x[5], y[5], x[0], y[0], x[1], y[1])
  str = "kyo"
  if p1 and p2 and p3
    v1 = p2 - p1
    v2 = p3 - p1
    s = Rational((v1[0] * v2[1] - v1[1] * v2[0]).abs, 2)
    if s.nonzero?
      idx = nil
      [Float::INFINITY, 1_900_000, 1_000_000, 100_000, 0].each_cons(2).with_index do |a, i|
        idx = i if a[1] <= s and s < a[0]
      end
      str = %w(dai-kichi chu-kichi kichi syo-kichi)[idx]
    end
  end
  puts str
end

つまらぬバグを取るのが大変だった。f = true and false は false なのだけれど、f = true になるのか。
　

0188 Search

until (n = $<.gets.to_i).zero?
  a = n.times.map {$<.gets.to_i}
  k = $<.gets.to_i
  co = 0
  
  f = ->(from, to) {
    return co if from > to
    mid = (from + to) / 2
    co += 1
    return co if a[mid] == k
    (a[mid] < k) ? f.(mid + 1, to) : f.(from, mid - 1)
  }
  puts f.(0, n - 1)
end

2分探索はどうもよくわからない。
　

0189 Convenient Location

until (n = $<.gets.to_i).zero?
  e = n.times.map {$<.gets.split.map(&:to_i)}
  edges = (e.map {|a, b, c| [[a, b], c]} + e.map {|a, b, c| [[b, a], c]}).to_h
  h = Hash.new([])
  edges.keys.each {|a, b| h[a] += [b]}
  
  try = ->(start) {
    shortest = Hash.new(Float::INFINITY)
    done = h.keys.map {|k| [k, false]}.to_h
    shortest[start] = 0
    
    loop do
      u = nil
      h.each_key do |node|
        next if done[node]
        u = node if !u or shortest[node] < shortest[u]
      end
      break unless u
      done[u] = true
      
      h[u].each do |v|
        if (a = shortest[u] + edges[[u, v]]) < shortest[v]
          shortest[v] = a
        end
      end
    end
    
    shortest.values.sum
  }
  puts h.keys.map {|k| [try.(k), k]}.sort.first.reverse.join(" ")
end

ダイクストラ法。

ffmpeg で mp3 ファイルの編集

$ ffmpeg -i 09.mp3 -t 124 -af "afade=t=out:st=120:d=3" 僕の中の少年.mp3

全部で 124秒、先頭から 120 秒でフェイドアウト、フェイドアウトの時間は 3秒。

AOJ（ALDS）その2

AIZU ONLINE JUDGE: Programming Challenge
　

ALDS1_9_A Complete Binary Tree

#完全二分木
$<.gets
given = [nil] + $<.gets.split.map(&:to_i)
a = nil
 
given.drop(1).each_with_index do |key, i|
  j = i + 1
  str = "node #{j}: key = #{key}, "
  str += "parent key = #{a}, " if (a = given[j / 2])
  str += "left key = #{a}, "   if (a = given[j * 2])
  str += "right key = #{a}, "  if (a = given[j * 2 + 1])
  puts str
end

ALDS1_9_B Maximum Heap

#最大ヒープ
h = $<.gets.to_i
given = [nil] + $<.gets.split.map(&:to_i)
 
max_heapify = ->(i) {
  l, r = i * 2, i * 2 + 1
  largest = (l <= h and given[l] > given[i]) ? l : i
  largest = r if r <= h and given[r] > given[largest]
  unless largest == i
    given[i], given[largest] = given[largest], given[i]
    max_heapify.(largest)
  end
}
 
(h / 2).downto(1) {|i| max_heapify.(i)}
puts given.drop(1).map {|i| " #{i}"}.join

ALDS1_9_C Priority Queue

#優先度付きキュー
class MaxHeap
  def initialize
    @heap = [nil]
    @size = 0
  end
   
  def insert(key)
    @heap << key
    @size += 1
    up_heap(@size / 2)
  end
   
  def up_heap(i)
    return if i.zero?
    l, r = i * 2, i * 2 + 1
    largest = (l <= @size and @heap[l] > @heap[i]) ? l : i
    largest = r if r <= @size and @heap[r] > @heap[largest]
    unless largest == i
      @heap[i], @heap[largest] = @heap[largest], @heap[i]
      up_heap(i / 2)
    end
  end
   
  def remove_root
    a = @heap[1]
    @heap[1] = @heap.pop
    @size -= 1
    down_heap(1)
    a
  end
   
  def down_heap(i)
    return if i > @size
    l, r = i * 2, i * 2 + 1
    largest = (l <= @size and @heap[l] > @heap[i]) ? l : i
    largest = r if r <= @size and @heap[r] > @heap[largest]
    unless largest == i
      @heap[i], @heap[largest] = @heap[largest], @heap[i]
      down_heap(largest)
    end
  end
end
 
 
h = MaxHeap.new
 
$<.readlines.map {|l| l.chomp.split}.each do |command|
  case command[0]
  when "insert" then h.insert(command[1].to_i)
  when "extract" then puts h.remove_root
  when "end" then break
  else raise "error"
  end
end

ALDS1_10_A Fibonacci Number

#フィボナッチ数列
fib = Enumerator.new do |y|
  a, b = 1, 1
  loop do
    y << a
    a, b = b, a + b
  end
end
 
puts fib.take($<.gets.to_i + 1).last

Ruby/Opal サンプル

コード。Ruby 部分のみ。

require 'native'

d = Native(`document`)
area = d.getElementById("text")
button = d.getElementById("start")
interval = Native(`window.setInterval`)

z, d = zd = ["ズン", "ドコ"]
st = ""
line = []
f = false

zundoko = ->{
  return if f
  line << zd[rand(2)]
  line = line.last(5)
  st += line.last
  area.textContent = st
  if line == [z, z, z, z, d]
    area.textContent = st + "　キ・ヨ・シ！"
    f = true
  end
}

start = ->{interval.call(zundoko, 1000)}
button.addEventListener("click", start)

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秒でクリア。うーん、勉強になるなあ。

AOJ（問題集）17

AIZU ONLINE JUDGE: Programming Challenge
　

0160 Delivery Fee

table = [[60, 2, 600], [80, 5, 800], [100, 10, 1000],
         [120, 15, 1200], [140, 20, 1400], [160, 25, 1600]]

until (n = $<.gets.to_i).zero?
  result = n.times.map {$<.gets.split.map(&:to_i)}.map do |x, y, h, w|
    idx = table.index {|d| x + y + h <= d[0] and w <= d[1]}
    idx ? table[idx].last : 0
  end.sum
  puts result
end

0161 Sport Meet

until (n = $<.gets.to_i).zero?
  result = n.times.map {$<.gets.split.map(&:to_i)}.map do |id, *d|
    [id, d.each_slice(2).map {|m, s| 60 * m + s}.sum]
  end.sort {|a, b| a[1] <=> b[1]}.map(&:first)
  puts result[0], result[1], result[-2]
end

0162 Hamming Numbers

L = 1000000

table = []
(0..19).each do |a|
  table << (x1 = 2 ** a)
  (1..12).each do |b|
    table << (x2 = 3 ** b)
    y1 = x1 * x2
    table << y1 if y1 <= L
    (1..8).each do |c|
      table << (x3 = 5 ** c)
      y2 = x2 * x3
      y3 = x1 * x3
      y4 = y1 * x3
      table << y2 if y2 <= L
      table << y3 if y3 <= L
      table << y4 if y4 <= L
    end
  end
end
table.uniq!.sort!

until (n = $<.gets.chomp) == "0"
  m, n = n.split.map(&:to_i)
  a = table.bsearch_index {|x| x >= m}
  b = table.bsearch_index {|x| x > n}
  b = b ? b : table.size
  puts b - a
end

0163 Highway Toll

toll = [[0, 300, 500, 600, 700, 1350, 1650],
        [0, 0, 350, 450, 600, 1150, 1500],
        [0, 0, 0, 250, 400, 1000, 1350],
        [0, 0, 0, 0, 250, 850, 1300],
        [0, 0, 0, 0, 0, 600, 1150],
        [0, 0, 0, 0, 0, 0, 500]]
S, E = 17 * 60 + 30, 19 * 60 + 30

until (d = $<.gets.to_i).zero?
  h, m = $<.gets.split.map(&:to_i)
  td = h * 60 + m
  a = $<.gets.to_i
  h, m = $<.gets.split.map(&:to_i)
  ta = h * 60 + m
  
  d, a = a, d if d > a
  f = if (a == 6 and d == 1) or (a == 7 and d <= 3)
    false
  elsif td.between?(S, E) or ta.between?(S, E)
    true
  else
    false
  end
  
  result = toll[d - 1][a - 1]
  result /= 2 if f
  puts ((result / 50.0).ceil * 50).to_i
end

td, ta が S と E の間にあればよいということがなかなかわからなかった。
　

0164 Ohajiki Game

until (n = $<.gets.to_i).zero?
  ary = $<.gets.split.map(&:to_i)
  ohajiki = 32
  loop do
    ohajiki -= (ohajiki - 1) % 5
    puts ohajiki
    a = ary.first
    if ohajiki <= a
      ohajiki = 0
    else
      ohajiki -= a
    end
    puts ohajiki
    break if ohajiki.zero?
    ary.rotate!
  end
end

0165 Lottery

MP = 999983

sieve = [*0..MP]
2.upto(Math.sqrt(MP).to_i) do |i|
  next if sieve[i].zero?
  2.upto(MP / i) {|j| sieve[i * j] = 0}
end
sieve = sieve[2..-1].reject {|x| x.zero?}

until (n = $<.gets.to_i).zero?
  account = n.times.map do
    p, m = $<.gets.split.map(&:to_i)
    s = sieve.bsearch_index {|i| i >= p - m}
    e = sieve.bsearch_index {|i| i > p + m} || sieve.size
    prize = e - s
    prize.zero? ? -1 : prize - 1
  end.sum
  puts account
end

0166 Area of Polygon

until (m = $<.gets.to_i).zero?
  poly1 = (m - 1).times.map {$<.gets.to_i}
  poly1 << 360 - poly1.sum
  n = $<.gets.to_i
  poly2 = (n - 1).times.map {$<.gets.to_i}
  poly2 << 360 - poly2.sum
  
  area1 = poly1.map {|i| Math.sin(i / 180.0 * Math::PI)}.sum
  area2 = poly2.map {|i| Math.sin(i / 180.0 * Math::PI)}.sum
  
  result = case
           when area1 == area2 then 0
           when area1 > area2  then 1
           else 2
           end
  puts result
end

0167 Bubble Sort

def bubble_sort(ary)
  n = ary.size
  co = 0
  (n - 1).downto(1) do |i|
    i.times do |j|
      if ary[j] > ary[j + 1]
        ary[j], ary[j + 1] = ary[j + 1], ary[j]
        co += 1
      end
    end
  end
  co
end

until (n = $<.gets.to_i).zero?
  puts bubble_sort(n.times.map {$<.gets.to_i})
end

0168 Kannondou

@memo = {}

def count(n)
  return @memo[n] if @memo[n]
  result = case n
           when 1 then 1
           when 2 then 2
           when 3 then 4
           else
             count(n - 1) + count(n - 2) + count(n - 3)
           end
  @memo[n] = result
end

until (n = $<.gets.to_i).zero?
  days = Rational(count(n), 10).ceil
  puts Rational(days, 365).ceil
end

0169 Blackjack

def calc(hand)
  i = hand.count(1)
  hand = hand - [1]
  point = 0
  while (a = hand.pop)
    point += case a
             when 2..9 then a
             else 10
             end
  end
  point1 = point2 = point + i
  point2 = point + 10 + i if i > 0
  if point2 <= 21
    point2
  elsif point1 <= 21
    point1
  else
    0
  end
end

until (n = $<.gets.chomp) == "0"
  puts calc(n.split.map(&:to_i))
end

AOJ（問題集）16

AIZU ONLINE JUDGE: Programming Challenge
　

0150 Twin Prime

N = 10007

sieve = [*0..N]
2.upto(Math.sqrt(N).to_i) do |i|
  next if sieve[i].zero?
  2.upto(N / i) {|j| sieve[i * j] = 0}
end
sieve = sieve[2..-1].reject {|x| x.zero?}

until (n = $<.gets.to_i).zero?
  idx = sieve.index {|i| i > n} - 1
  i = 0
  i += 1 until sieve[idx - i] - sieve[idx - i - 1] == 2
  puts "#{sieve[idx - i - 1]} #{sieve[idx - i]}"
end

N = 10000 ではダメなことになかなか気づかなかった。
　

0151 Grid

def count(line)
  line.chunk {|i| i.nonzero?}.select(&:first).map {|l| l.last.size}.max || 0
end

until (n = $<.gets.to_i).zero?
  field = n.times.map {$<.gets.chomp.chars.map(&:to_i)}
  
  max_l = field.map {|l| count(l)}.max
  max_l = [field.transpose.map {|l| count(l)}.max, max_l].max
  l = n - 1
  n.times do |i|
    line = (i + 1).times.map {|j| field[i - j][j]}
    tmp1 = count(line)
    line = (i + 1).times.map {|j| field[l - i + j][l - j]}
    tmp2 = count(line)
    line = (i + 1).times.map {|j| field[i - j][l - j]}
    tmp3 = count(line)
    line = (i + 1).times.map {|j| field[l - i + j][j]}
    tmp4 = count(line)
    max_l = [tmp1, tmp2, tmp3, tmp4, max_l].max
  end
  
  puts max_l
end

0.50秒。素朴にやった。まあまあか。
　

0152 Bowling

until (m = $<.gets.to_i).zero?
  result = m.times.map do
    id, *score = $<.gets.split.map(&:to_i)
    th = 0
    
    final_point = 10.times.map do |i|
      if i == 9
        if score[th] == 10 or score[th, 2].sum == 10
          score[th, 3].sum
        else
          score[th, 2].sum
        end
      elsif score[th] == 10
        th += 1
        10 + score[th, 2].sum
      elsif score[th, 2].sum == 10
        th += 2
        10 + score[th]
      else
        th += 2
        score[th - 2, 2].sum
      end
    end.sum
    
    [id, final_point]
  end.sort {|a, b| (b[1] <=> a[1]).nonzero? || a[0] <=> b[0]}
  puts result.map {|a| a.join(" ")}
end

複数キーのソートはここを参考にしました。
　

0153 Triangle and Circle

def perpendicular_foot(a, b, p)
  s = Rational((p - a).dot(b - a), (b - a).dot(b - a))
  h = a + (b - a) * s
  [s, (h - p).norm]
end

def triangle_inside(a, b, c, p)
  s, t = Matrix.columns([b - a, c - a]).lup.solve(p - a).to_a
  s > 0 and t > 0 and 0 < s + t and s + t < 1
end

until (p1 = $<.gets.split.map(&:to_i)) == [0, 0]
  p1 = Vector[*p1]
  p2 = Vector[*$<.gets.split.map(&:to_i)]
  p3 = Vector[*$<.gets.split.map(&:to_i)]
  c  = Vector[*$<.gets.split.map(&:to_i)]
  r = $<.gets.to_i
  
  f1 = (p1 - c).norm
  f2 = (p2 - c).norm
  f3 = (p3 - c).norm
  
  g1 = (f1 <= r and f2 >= r) or (f1 >= r and f2 <= r)
  g2 = (f2 <= r and f3 >= r) or (f2 >= r and f3 <= r)
  g3 = (f3 <= r and f1 >= r) or (f3 >= r and f1 <= r)
  
  s, l = perpendicular_foot(p1, p2, c)
  h1 = (0 <= s and s <= 1) and (f1 >= r and f2 >= r) and l <= r
  e1 = l >= r and f1 > r and f2 > r
  s, l = perpendicular_foot(p2, p3, c)
  h2 = (0 <= s and s <= 1) and (f2 >= r and f3 >= r) and l <= r
  e2 = l >= r and f2 > r and f3 > r
  s, l = perpendicular_foot(p3, p1, c)
  h3 = (0 <= s and s <= 1) and (f3 >= r and f1 >= r) and l <= r
  e3 = l >= r and f3 > r and f1 > r
  
  e0 = triangle_inside(p1, p2, p3, c)
  
  result = if e0 and e1 and e2 and e3
    "a"
  elsif f1 <= r and f2 <= r and f3 <= r
    "b"
  elsif g1 or g2 or g3 or h1 or h2 or h3
    "c"
  else
    "d"
  end
  
  puts result
end

Wrong Answer.

require 'matrix'

def perpendicular_foot(a, b, p)
  s = Rational((p - a).dot(b - a), (b - a).dot(b - a))
  h = a + (b - a) * s
  (h - p).norm
end

def triangle_inside(a, b, c, p)
  s, t = Matrix.columns([b - a, c - a]).lup.solve(p - a).to_a
  s > 0 and t > 0 and 0 < s + t and s + t < 1
end

until (p1 = $<.gets.split.map(&:to_i)) == [0, 0]
  p1 = Vector[*p1]
  p2 = Vector[*$<.gets.split.map(&:to_i)]
  p3 = Vector[*$<.gets.split.map(&:to_i)]
  c  = Vector[*$<.gets.split.map(&:to_i)]
  r = $<.gets.to_i
  
  f1 = (p1 - c).norm
  f2 = (p2 - c).norm
  f3 = (p3 - c).norm
  
  l = perpendicular_foot(p1, p2, c)
  h1 = l > r
  e1 = l >= r and f1 > r and f2 > r
  l = perpendicular_foot(p2, p3, c)
  h2 = l > r
  e2 = l >= r and f2 > r and f3 > r
  l = perpendicular_foot(p3, p1, c)
  h3 = l > r
  e3 = l >= r and f3 > r and f1 > r
  
  e0 = triangle_inside(p1, p2, p3, c)
  
  result = if e0 and e1 and e2 and e3
    "a"
  elsif f1 <= r and f2 <= r and f3 <= r
    "b"
  elsif f1 > r and f2 > r and f3 > r and h1 and h2 and h3 
    "d"
  else
    "c"
  end
  
  puts result
end

Wrong Answer.

require 'matrix'

def perpendicular_foot(a, b, p)
  s = Rational((p - a).dot(b - a), (b - a).dot(b - a))
  h = a + (b - a) * s
  (h - p).norm
end

def triangle_inside(a, b, c, p)
  s, t = Matrix.columns([b - a, c - a]).lup.solve(p - a).to_a
  s > 0 and t > 0 and 0 < s + t and s + t < 1
end

until (p1 = $<.gets.split.map(&:to_i)) == [0, 0]
  p1 = Vector[*p1]
  p2 = Vector[*$<.gets.split.map(&:to_i)]
  p3 = Vector[*$<.gets.split.map(&:to_i)]
  c  = Vector[*$<.gets.split.map(&:to_i)]
  r = $<.gets.to_i
  
  f1 = (p1 - c).norm
  f2 = (p2 - c).norm
  f3 = (p3 - c).norm
  
  h1 = perpendicular_foot(p1, p2, c)
  h2 = perpendicular_foot(p2, p3, c)
  h3 = perpendicular_foot(p3, p1, c)
  
  e0 = triangle_inside(p1, p2, p3, c)
  
  result = if h1 >= r and h2 >= r and h3 >= r and e0 
    "a"
  elsif h1 > r and h2 > r and h3 > r and !e0
    "d"
  elsif f1 <= r and f2 <= r and f3 <= r
    "b"
  else
    "c"
  end
  
  puts result
end

Wrong Answer.

require 'matrix'

def perpendicular_foot(a, b, p)
  s = Rational((p - a).dot(b - a), (b - a).dot(b - a))
  h = a + (b - a) * s
  (h - p).dot(h - p)
end

def triangle_inside(a, b, c, p)
  s, t = Matrix.columns([b - a, c - a]).lup.solve(p - a).to_a
  s > 0 and t > 0 and 0 < s + t and s + t < 1
end

until (p1 = $<.gets.split.map(&:to_i)) == [0, 0]
  p1 = Vector[*p1]
  p2 = Vector[*$<.gets.split.map(&:to_i)]
  p3 = Vector[*$<.gets.split.map(&:to_i)]
  c  = Vector[*$<.gets.split.map(&:to_i)]
  r = $<.gets.to_i ** 2
  
  f1 = (p1 - c).dot(p1 - c)
  f2 = (p2 - c).dot(p2 - c)
  f3 = (p3 - c).dot(p3 - c)
  
  h1 = perpendicular_foot(p1, p2, c)
  h2 = perpendicular_foot(p2, p3, c)
  h3 = perpendicular_foot(p3, p1, c)
  
  e0 = triangle_inside(p1, p2, p3, c)
  
  result = if f1 <= r and f2 <= r and f3 <= r
    "b"
  elsif f1 > r and f2 > r and f3 > r
    min_h = [h1, h2, h3].min
    if e0 and min_h >= r
      "a"
    elsif !e0 and min_h > r
      "d"
    else
      "c"
    end
  else
    "c"
  end
  
  puts result
end

Wrong Answer.
　

0154 Sum of Cards

until (m = $<.gets.to_i).zero?
  cards = m.times.map {$<.gets.split.map(&:to_i)}
  ln = cards.map {|a, b| a * b}.sum
  table = [0]
  cards.each do |a, b|
    table = table.flat_map do |num|
      (b + 1).times.map {|i| num + a * i}
    end
  end
  
  $<.gets.to_i.times do
    puts table.count($<.gets.to_i)
  end
end

20.9秒もかかったのに accept された。
他の人の回答を見てみた。

until (m = $<.gets.to_i).zero?
  cards = m.times.map {$<.gets.split.map(&:to_i)}
  memo = Array.new(cards.size + 1) {[]}
  $<.gets.to_i.times do
    count = ->(i, left) {
      return memo[i][left] if memo[i][left]
      if i >= cards.length
        co = left.zero? ? 1 : 0
      else
        co = 0
        a, b = cards[i]
        (b + 1).times do |j|
          nxt = left - a * j
          break if nxt < 0
          co += count.(i + 1, nxt)
        end
      end
      memo[i][left] = co
    }
    puts count.(0, $<.gets.to_i)
  end
end

0.07秒…。何でこれに気づかない…。
　

0155 Spider Jin

until (n = $<.gets.to_i).zero?
  buildings = n.times.map {$<.gets.split.map(&:to_i)}
  sg = $<.gets.to_i.times.map {$<.gets.split.map(&:to_i)}
  table = Hash.new {|h, k| h[k] = {}}
  buildings.combination(2) do |a, b|
    ida, xa, ya = a
    idb, xb, yb = b
    dist = (xa - xb) ** 2 + (ya - yb) ** 2
    next if dist > 50 ** 2
    table[ida][idb] = Math.sqrt(dist)
    table[idb][ida] = Math.sqrt(dist)
  end
  h = table.map {|k, v| [k, v.keys]}.to_h
  
  sg.each do |s, g|
    shortest = Hash.new(Float::INFINITY)
    pred = {}
    done = h.keys.map {|k| [k, false]}.to_h
    shortest[s] = 0
    
    loop do
      u = nil
      h.each_key do |node|
        next if done[node]
        u = node if !u or shortest[node] < shortest[u]
      end
      break unless u
      done[u] = true
      
      h[u].each do |v|
        if (a = shortest[u] + table[u][v]) < shortest[v]
          shortest[v] = a
          pred[v] = u
        end
      end
    end
    
    result = if pred[g]
      order = []
      while g
        order.unshift(g)
        g = pred[g]
      end
      order.join(" ")
    else
      "NA"
    end
    puts result
  end
end

ダイクストラ法。
　

0156

until (a = io.gets.split.map(&:to_i)) == [0, 0]
  n, m = a
  field = m.times.map {io.gets.chomp.chars}
  i = field.flatten.index("&")
  
  numbering = ->(x, y, num) {
    type = field[y][x]
    queue = [[x, y]]
    while (a = queue.shift)
      x0, y0 = a
      field[y0][x0] = num
      [[1, 0], [0, -1], [-1, 0], [0, 1]].each do |dx, dy|
        x1 = x0 + dx
        y1 = y0 + dy
        return num if x1 < 0 or x1 >= n or y1 < 0 or y1 >= m
        next if field[y1][x1] != type
        next if ![".", "#", "&"].include?(field[y1][x1])
        queue << [x1, y1]
      end
    end
    false
  }
  
  catch :jump do
    x, y = i % n, i / n
    [[1, 0], [0, -1], [-1, 0], [0, 1]].each do |dx, dy|
      x1 = x + dx
      y1 = y + dy
      if x1 < 0 or x1 >= n or y1 < 0 or y1 >= m
        puts 0
        throw :jump
      else
        num = (field[y1][x1] == "#") ? 0 : 1
        num = numbering.(x1, y1, num)
        if num
          puts 0
          throw :jump
        end
      end
    end
    
    puts -1
  end
  puts field.map(&:join)
end

考え中。
　

0157 Russian Dolls

until (n = $<.gets.to_i).zero?
  ichiro = n.times.map {$<.gets.split.map(&:to_i)}
            .sort {|a, b| (b[0] <=> a[0]).nonzero? || b[1] <=> a[1]}
  m = $<.gets.to_i
  jiro = m.times.map {$<.gets.split.map(&:to_i)}
          .sort {|a, b| (b[0] <=> a[0]).nonzero? || b[1] <=> a[1]}
  
  memo = {}
  
  try = ->(h, r, ichi, ji) {
    key = "#{h},#{r},#{ichi},#{ji}"
    return memo[key] if memo[key]
    return 0 if ichi >= n and ji >= m
    co1 = co2 = 0
    if ichiro[ichi]
      if h > ichiro[ichi][0] and r > ichiro[ichi][1]
        co1 = 1 + try.(ichiro[ichi][0], ichiro[ichi][1], ichi + 1, ji)
      else
        co1 = try.(h, r, ichi + 1, ji)
      end
    end
    if jiro[ji]
      if h > jiro[ji][0] and r > jiro[ji][1]
        co2 = 1 + try.(jiro[ji][0], jiro[ji][1], ichi, ji + 1)
      else
        co2 = try.(h, r, ichi, ji + 1)
      end
    end
    memo[key] = (co1 > co2) ? co1 : co2
  }
  puts try.(Float::INFINITY, Float::INFINITY, 0, 0)
end

これで 0.14秒。自力で考えたオレはえらいが、これは DAG（閉路なし有向グラフ）の最長経路問題なのだった。
なので、動的計画法で解くのがふつうらしい。こんな感じ。

until (n = $<.gets.to_i).zero?
  dolls = n.times.map {$<.gets.split.map(&:to_i)}
  m = $<.gets.to_i
  dolls += m.times.map {$<.gets.split.map(&:to_i)}
  dolls.sort! {|a, b| (b[0] <=> a[0]).nonzero? || b[1] <=> a[1]}
  
  longest = Array.new(n + m, 0)
  
  (0..n + m - 2).each do |i|
    (i + 1...n + m).each do |j|
      if dolls[i][0] > dolls[j][0] and dolls[i][1] > dolls[j][1]
        if (a = longest[i] + 1) > longest[j]
          longest[j] = a
        end
      end
    end
  end
  puts longest.last + 1
end

これで 0.06秒。
　

0158 Collatz's Problem

@memo = {}

def try(n)
  return @memo[n] if @memo[n]
  return 0 if n == 1
  co = if n.even?
    try(n / 2)
  else
    try(n * 3 + 1)
  end
  @memo[n] = co + 1
end

until (n = $<.gets.to_i).zero?
  puts try(n)
end

0159 The Best Body

until (n = $<.gets.to_i).zero?
  min_dif = Float::INFINITY
  persons = []
  n.times.map {$<.gets.split.map(&:to_i)}.each do |p, h, w|
    h = Rational(h, 100)
    dif = (Rational(w, h * h) - 22).abs
    if dif < min_dif
      persons = [p]
      min_dif = dif
    elsif dif == min_dif
      persons << p
    end
  end
  puts persons.sort.first
end

AOJ（問題集）15

AIZU ONLINE JUDGE: Programming Challenge
　

0140 Bus Line

line = [*0..9] + [5, 4, 3, 2, 1]
line += line

$<.gets.to_i.times do
  start, goal = $<.gets.split.map(&:to_i)
  str = if 1 <= start and start <= 5 and start > goal
    [*goal..start].reverse.join(" ")
  else
    a = line.index(start)
    b = line[a + 1..-1].index(goal)
    line[a..a + 1 + b].join(" ")
  end
  puts str
end

0141 Spiral Pattern

ぐるぐる模様。

result = []

$<.gets.to_i.times do
  n = $<.gets.to_i
  field = Array.new(n) {" " * n}
  x, y = 0, n - 1
  
  go = ->(dx, dy, l) {
    l.times do
      field[y][x] = "#"
      x += dx
      y += dy
    end
  }
  square = ->(l) {
    if l != 1
      go.(0, -1, l - 1)
      go.(1,  0, l - 1)
      go.(0,  1, l - 1)
      if l != 3
        go.(-1, 0, l - 3)
        if l != 4
          if l > 4
            go.(0, -1, 2)
            square.(l - 4)
          end
          return
        end
      end
    end
    field[y][x] = "#"
  }
  
  square.(n)
  result << field.map {|l| l + "\n"}.join
end
puts result.join("\n")

思っていたよりずっとむずかしかった。これがいちばんよいやり方か自信がない。実際、Ruby で解けた人は自分も含めて 4人しかいない。
　

0142 Nature of Prime Numbers

素朴に実装してみる。

until (n = $<.gets.to_i).zero?
  rems = (1...n).map {|i| i * i % n}.uniq.permutation(2).map do |a, b|
    rem = a - b
    rem += n if rem < 0
    rem = n - rem if rem > (n - 1) / 2
    rem
  end
  puts (1..(n - 1) / 2).map {|i| rems.count(i)}
end

時間オーバー。
　

0143 Altair and Vega

require 'matrix'

$<.gets.to_i.times do
  given = $<.gets.split.map(&:to_r).each_slice(2).map {|x, y| Vector[x, y]}
  p1, p2, p3, k, s = given
  calc = ->(r) { Matrix.columns([p2 - p1, p3 - p1]).lup.solve(r - p1).to_a }
  s1, t1 = calc.(k)
  s2, t2 = calc.(s)
  f1 = s1 + t1 < 1 && s1 > 0 && t1 > 0
  f2 = s2 + t2 < 1 && s2 > 0 && t2 > 0
  puts f1 ^ f2 ? "OK" : "NG"
end

こういう問題は慣れてきた。
　

0144 Packet Transportation

address = $<.gets.to_i.times.map do
  r, k, *t = $<.gets.split.map(&:to_i)
  [r, t]
end.to_h

$<.gets.to_i.times do
  s, d, v = $<.gets.split.map(&:to_i)
  queue = [[s]]
  catch :jump do
    while (now = queue.shift) and now.size <= v
      if now.last == d
        puts now.size
        throw :jump
      else
        address[now.last].each do |to|
          next if now.include?(to)
          queue << now + [to]
        end
      end
    end
    puts "NA"
  end
end

幅優先探索なのだが、なんとメモリオーバー。
ダイクストラ法でやる。

class Node
  def initialize(t)
    @to = t
    @cost = Float::INFINITY
    @done = false
  end
  attr_accessor :to, :cost, :done
end

given = $<.gets.to_i.times.map do
  r, k, *t = $<.gets.split.map(&:to_i)
  [r, Node.new(t)]
end.to_h

$<.gets.to_i.times do
  s, d, v = $<.gets.split.map(&:to_i)
  nodes = Marshal.load(Marshal.dump(given))
  nodes[s].cost = 0
  
  loop do
    u = nil
    nodes.each_value do |node|
      next if node.done
      u = node if !u or node.cost < u.cost
    end
    break unless u
    u.done = true
    
    u.to.each do |v|
      if (a = u.cost + 1) < nodes[v].cost
        nodes[v].cost = a
      end
    end
  end
  
  i = nodes[d].cost + 1
  puts (i <= v) ? i : "NA"
end

1.15秒かかった。他の人の回答を見ると、やはりうまく幅優先探索で実装したほうが圧倒的に速い。
やってみる。

address = $<.gets.to_i.times.map do
  r, k, *t = $<.gets.split.map(&:to_i)
  [r, t]
end.to_h

$<.gets.to_i.times do
  s, d, v = $<.gets.split.map(&:to_i)
  queue = [s]
  dist = {s=>1}
  until !(now = queue.shift) or now == d
    address[now].each do |nxt|
      unless dist[nxt]
        dist[nxt] = dist[now] + 1
        queue << nxt
      end
    end
  end
  ds = dist[now]
  puts ds && (ds <= v) ? ds : "NA"
end

これだと 0.06秒。瞬殺である。
　

0145 Cards

decks = $<.gets.to_i.times.map {$<.gets.split.map(&:to_i)}
L = decks.size
memo = Array.new(L) {[]}

minimum = ->(left, right) {
  return memo[left][right] if memo[left][right]
  result = if left == right
    0
  else
    (right - left).times.map do |i|
      decks[left][0] * decks[left + i][1] * decks[left + i + 1][0] * decks[right][1] +
        minimum.(left, left + i) + minimum.(left + i + 1, right)
    end.min
  end
  memo[left][right] = result
}
puts minimum.(0, L - 1)

苦労して考えたにしてはあっさり正解。動的計画法。Ruby だといつもの常連さんしか出来ていない（笑）。
　

0146 Lupin The 4th

全然思いつかない。とりあえず総当り。

n = $<.gets.to_i
kuras = $<.readlines.map {|i| i.split.map(&:to_i)}
min = Float::INFINITY
result = nil

try = ->(reached = [], w = 0, t = 0, before = nil) {
  return if t >= min
  if reached.size == n
    if t < min
      min = t
      result = reached
    end
  else
    kuras.each do |k|
      next if reached.include?(k[0])
      before ||= k[1]
      l = (k[1] - before).abs
      v = 2000 / (70 + w.to_r)
      try.(reached + [k[0]], w + k[2] * 20, t + l / v, k[1])
    end
  end
}
try.()
puts result.join(" ")

予想通りタイムオーバー。
いつものごとく tnakao さんの回答を参考にする。なるほど、蔵間の距離はあらかじめ求めておけばよい。また、これは重要だが、出発点と残っている蔵が確定していれば、残りの順番は確定するということ（千両箱の重さに順番は関係ない）。うーん、すばらしい洞察だ。

n = io.gets.to_i
kuras = io.readlines.map {|i| i.split.map(&:to_i)}
kuras.each {|k| k[2] *= 20}

edges = Array.new(n) {[nil] * n}
n.times do |i|
  (i + 1...n).each {|j| edges[i][j] = edges[j][i] = (kuras[i][1] - kuras[j][1]).abs}
end

all = (1 << n) - 1
memo = Array.new(n) {[]}
n.times {|i| memo[i][all ^ (1 << i)] = [0, [kuras[i][0]]]}

try = ->(start, reached = 0, w = 0) {
  return memo[start][reached] if memo[start][reached]
  
  now = kuras[start]
  min_time = Float::INFINITY
  min_order = nil
  nr = reached | (1 << start)
  w0 = w + now[2]
  
  n.times do |nxt|
    next if (nr & (1 << nxt)).nonzero?
    time, order = try.(nxt, nr, w0)
    time += edges[start][nxt] * (70 + w0).to_r / 2000
    if time < min_time
      min_time = time
      min_order = [now[0]] + order
    end
  end
  
  memo[start][reached] = [min_time, min_order]
}

puts (0...n).map {|i| try.(i)}.sort_by(&:first).first.last.join(" ")

その方向でやってみる。3.99秒でクリア。
　

0147 Fukushimaken

table = [0, 0, 0, 0, 0, 0, 14, 9, 4, 0, 0, 8, 3, 2, 0, 0, 15, 10, 15, 10,
         6, 12, 7, 9, 11, 6, 23, 18, 13, 8, 3, 23, 18, 13, 8, 3, 34, 29, 24,
         22, 17, 28, 23, 24, 19, 27, 34, 29, 35, 30, 28, 31, 28, 23, 24, 28,
         42, 37, 32, 27, 22, 42, 37, 32, 27, 22, 53, 48, 43, 41, 36, 47, 42,
         43, 38, 46, 64, 59, 54, 49, 44, 61, 56, 51, 46, 44, 72, 67, 62, 57,
         52, 72, 67, 62, 57, 52, 83, 78, 73, 71]
puts $<.readlines.map(&:to_i).map {|i| table[i]}

あらかじめ計算しておけばよい。table を得るためのコードは以下。

N = 100
S = 17
in_time = (0...N).map {|i| 5 * i}
numbers = (0...N).map {|i| (i % 5 == 1) ? 5 : 2}
eating_time = (0...N).map {|i| 17 * (i % 2) + 3 * (i % 3) + 19}
finish_time = Array.new(N, -1)
seats = Array.new(S, -1)
waiting = []
waiting_time = Array.new(N, -1)

0.step do |now|
  # 食べ終わったグループの処理
  N.times do |j|
    next unless finish_time[j] == now
    seats = seats.map {|i| i == j ? -1 : i}
  end
  
  # 入ってきたグループの処理
  come_in = in_time.index(now)
  waiting << come_in if come_in
  
  # 座れる場合の処理
  sittable = ->(i) {
    index = ->(size) {
      j = 0
      while j < S
        return j if seats[j, size] == [-1] * size
        j += 1
      end
      false
    }
    idx = index.(numbers[i])
    if idx
      numbers[i].times {|j| seats[idx + j] = i}
      true
    else
      false
    end
  }
  
  while (head = waiting.first) and sittable.(head)
    waiting_time[head] = now - in_time[head]
    waiting.shift
    finish_time[head] = now + eating_time[head]
  end
  
  break if seats.all? {|i| i < 0}
end

p waiting_time

0148 Candy and Class Flag

result = $<.readlines.map(&:to_i).map do |a|
  sprintf "3C%02d", (i = a % 39).zero? ? 39 : i
end
puts result

0149 Eye Test

L = 4
table = [[1.1, Float::INFINITY], [0.6, 1.1], [0.2, 0.6], [0, 0.2]]
left  = Array.new(L, 0)
right = Array.new(L, 0)

count = ->(a, counter) {
  table.each_with_index do |d, i|
    counter[i] += 1 if d[0] <= a and a < d[1]
  end
  counter
}

$<.readlines.map {|l| l.split.map(&:to_f)}.each do |l, r|
  left  = count.(l, left)
  right = count.(r, right)
end

L.times do |i|
  puts "#{left[i]} #{right[i]}"
end

何だか冗長なコードになってしまった。

AOJ（問題集）14

AIZU ONLINE JUDGE: Programming Challenge
　

0130 Train

$<.gets.to_i.times do
  given = $<.gets.chomp.split(/(->|<-)/)
  train = [given.shift]
  while (dir = given.shift)
    car = given.shift
    next if train.include?(car)
    (dir == "->") ? train.push(car) : train.unshift(car)
  end
  puts train.join
end

出来てみればじつに簡単なことなのに、ものすごく悩んだ。
　

0131 Doctor's Strange Particles

L = 10

$<.gets.to_i.times do
  field = Array.new(L) {$<.gets.split.map(&:to_i)}.flatten
  result = Array.new(L * L, 0)
  
  reverse = ->(x, y) {
    [[0, 0], [1, 0], [0, -1], [-1, 0], [0, 1]].each do |dx, dy|
      x1 = x + dx
      y1 = y + dy
      next if x1 < 0 or x1 >= L or y1 < 0 or y1 >= L
      i = y1 * L + x1
      field[i] = 1 - field[i]
    end
  }
  
  top_row = ->(i) {
    if i >= L
      tmp1 = field.dup
      tmp2 = result.dup
      while i < L * L
        if field[i - L] == 1
          result[i] = 1
          reverse.(i % L, i / L)
        end
        i += 1
      end
      if field.all? {|i| i.zero?}
        puts result.each_slice(L).map {|a| a.join(" ")}
        true
      else
        field  = tmp1
        result = tmp2
        false
      end
    else
      return true if top_row.(i + 1)
      
      result[i] = 1
      reverse.(i % L, i / L)
      return true if top_row.(i + 1)
      reverse.(i % L, i / L)
      result[i] = 0
      false
    end
  }
  top_row.(0)
end

些細なミスが多かった。
　

0132 Jigsaw Puzzle

until (a = $<.gets.split.map(&:to_i)) == [0, 0]
  h, w = a
  puzzle = h.times.map {$<.gets.chomp}
  pieces = $<.gets.to_i.times.flat_map do
    ph, pw = $<.gets.split.map(&:to_i)
    tmp = [ph.times.map {$<.gets.chomp}]
    3.times do
      tmp << tmp.last.reverse.map(&:chars).transpose.map(&:join)
    end
    tmp
  end
  
  $<.gets.to_i.times do
    k, *tn = $<.gets.split.map(&:to_i)
    tn = tn.map {|i| i - 1}.sort
    tn1 = tn.flat_map {|i| 4.times.map {|j| i * 4 + j}}.sort
    
    solve = ->(embeded, selected = [], selected_num = []) {
      return true if !embeded.join.index(".") and tn == selected_num
      
      adjust = ->(piece, piece_num) {
        idx = embeded.join.index(".")
        return false unless idx
        x, y = idx % w, idx / w
        
        p_idx = piece.join.index("#")
        pw = piece.first.length
        px = p_idx % pw
        return false if x + pw - px >= w
        return false if (x -= px) < 0
        
        nxt = embeded.map(&:dup)
        piece.each_index do |i|
          piece[i].each_char.with_index do |c, j|
            if c == "#"
              if embeded[y + i][x + j] == "."
                nxt[y + i][x + j] = (piece_num / 4).to_s
              else
                return false
              end
            end
          end
        end
        nxt
      }
      
      (tn1 - selected).each do |pn|
        next unless selected.select {|i| i / 4 == pn / 4}.empty?
        if (nxt = adjust.(pieces[pn], pn))
          return true if solve.(nxt, selected + [pn], (selected_num + [pn / 4]).sort)
        end
      end
      false
    }
    puts solve.(puzzle) ? "YES" : "NO"
  end
end

時間オーバー。

until (a = $<.gets.split.map(&:to_i)) == [0, 0]
  h, w = a
  puzzle = h.times.map {$<.gets.chomp}
  pieces = (n = $<.gets.to_i).times.map do
    ph, pw = $<.gets.split.map(&:to_i)
    ph.times.map {$<.gets.chomp}
  end
  
  io.gets.to_i.times do
    k, *tn = $<.gets.split.map(&:to_i)
    tn = tn.map {|i| i - 1}.sort
    
    solve = ->(embeded, selected = []) {
      return true if !embeded.join.index(".") and tn == selected
      
      adjust = ->(piece) {
        idx = embeded.join.index(".")
        return false unless idx
        x, y = idx % w, idx / w
        
        p_idx = piece.join.index("#")
        pw = piece.first.length
        px = p_idx % pw
        return false if x + pw - px >= w
        return false if (x -= px) < 0
        
        nxt = embeded.map(&:dup)
        piece.each_index do |i|
          piece[i].each_char.with_index do |c, j|
            if c == "#"
              if embeded[y + i][x + j] == "."
                nxt[y + i][x + j] = "#"
              else
                return false
              end
            end
          end
        end
        nxt
      }
      check = ->(piece_num) {
        candidate = pieces[piece_num]
        nexts = []
        4.times do
          if (nxt = adjust.(candidate))
            nexts << nxt
          end
          candidate = candidate.reverse.map(&:chars).transpose.map(&:join)
        end
        nexts.empty? ? false : nexts
      }
      
      (tn - selected).each do |piece_num|
        if (nexts = check.(piece_num))
          nexts.each do |nxt|
            return true if solve.(nxt, (selected + [piece_num]).sort)
          end
        end
      end
      false
    }
    puts solve.(puzzle) ? "YES" : "NO"
  end
end

上も下もやり方は合っていると思うけれど、時間オーバー。Ruby では誰も解けていない。
　

0133 Rotation of a Pattern

given = $<.readlines.map(&:chomp)
3.times do |i|
  puts 90 * (i + 1)
  puts given = given.reverse.map(&:chars).transpose.map(&:join)
end

突然簡単に。
　

0134 Exit Survey

n = $<.gets.to_i
puts Array.new(n) {$<.gets.to_i}.sum / n

0135 Clock Short Hand and Long Hand

$<.gets.to_i.times do
  h, m = $<.gets.split(":").map(&:to_r)
  l, s = m * 6, (h * 60 + m) / 2
  r = (l - s).abs
  r = 360 - r if r > 180
  st = if 0 <= r and r < 30
    "alert"
  elsif 90 <= r and r <= 180
    "safe"
  else
    "warning"
  end
  puts st
end

0136 Frequency Distribution of Height

度数分布。

L = 6
table = 165.0.step(185.0, 5.0).each_cons(2).to_a 
table = [[0, 165.0]] + table + [[185.0, Float::INFINITY]]
count = Array.new(L, 0)

$<.gets.to_i.times do
  h = $<.gets.to_f
  count[table.index {|a, b| a <= h and h < b}] += 1
end

count.each_with_index {|i, j| puts "#{j + 1}:" + "*" * i}

0137 Middle-Square Method

平方採中法。

$<.gets.to_i.times do |i|
  num = $<.gets.to_i
  rnd = Enumerator.new do |y|
    loop do
      num = (num * num).to_s.rjust(8, "0")[2, 4].to_i
      y << num
    end
  end
  puts "Case #{i + 1}:"
  puts rnd.take(10)
end

Ruby っぽいコードだと思います。Enumerator にぴったりな問題というのはあまりない気がする。
　

0138 Track and Field Competition

get = ->{ Array.new(8) {$<.gets.chomp.split} }

left = 3.times.flat_map do
  given = get.().sort_by {|a| a.last.to_f}
  puts given.shift.join(" ")
  puts given.shift.join(" ")
  given
end.sort_by {|a| a.last.to_f}
puts left.shift.join(" ")
puts left.shift.join(" ")

0139 Snakes

$<.gets
$<.readlines.map(&:chomp).each do |line|
  s1 = /^>'(=+)#(=+)~$/.match(line)
  s2 = /^>\^(Q=)+~~$/.match(line)
  str = if s1 and s1[1] == s1[2]
    "A"
  elsif s2
    "B"
  else
    "NA"
  end
  puts str
end

正規表現を使うのはめずらしい。

obelisk2 2019-01-18 01:18

AOJ（問題集）14

広告を非表示にする

• もっと読む

コメントを書く