AOJ（問題集）7

AOJ Ruby

AIZU ONLINE JUDGE: Programming Challenge
　

0061 Rank Checker

data = []
until (st = $<.gets.chomp) == "0,0"
  data << st.split(",").map(&:to_i)
end
data.sort! {|a, b| b[1] <=> a[1]}
x = data.first.last
h = {}
l = 1
data.each do |d|
  l += 1 unless x == d.last
  x = d.last
  h[d.first] = l
end

puts $<.readlines.map(&:to_i).map {|i| h[i]}

実装が汚い…。
　

0062 What is the Bottommost?

def doit(ary)
  return ary.first if ary.size == 1
  doit( ary.each_cons(2).map {|i, j| (i + j) % 10} )
end

$<.readlines.map {|a| a.chomp.chars.map(&:to_i)}.each do |given|
  puts doit(given)
end

　

0063 Palindrome

co = 0
$<.readlines.map(&:chomp).each do |st|
  co += 1 if st == st.reverse
end
puts co

　

0064 Secret Number

n = 0
$<.readlines.map(&:chomp).each do |st|
  n += st.scan(/\d+/).map(&:to_i).sum
end
puts n

　

0065 Trading

x, y = $<.readlines.map(&:chomp).chunk {|st| st.empty?}.reject {|a| a.first}
         .map(&:last).map{|a| a.map {|b| b.split(",").first.to_i}}.to_a
h = Hash.new(0)
(x + y).each {|i| h[i] += 1}
(x - (x - y)).uniq.sort.each {|i| puts "#{i} #{h[i]}"}

　

0066 Tic Tac Toe

table = [[0, 1, 2], [3, 4, 5], [6, 7, 8], [0, 3, 6], [1, 4, 7], [2, 5, 8],
         [0, 4, 8], [2, 4, 6]]
check = ->(field, type) {
  table.each {|pat| return true if pat.map {|i| field[i] == type}.all?}
  false
}

$<.readlines.map(&:chomp).map(&:chars).each do |field|
  result = if check.(field, "o")
    "o"
  elsif check.(field, "x")
    "x"
  else
    "d"
  end
  puts result
end

最初与えられた盤面でゲームが完結していないのかと思った…。
　

0067 The Number of Island

L = 12

def delete(field, x, y)
  field[y][x] = "0"
  [[1, 0], [0, -1], [-1, 0], [0, 1]].each do |dx, dy|
    x1 = x + dx
    y1 = y + dy
    if !(x1 < 0 or x1 >= L or y1 < 0 or y1 >= L) and field[y1][x1] == "1"
      delete(field, x1, y1)
    end
  end
end

$<.readlines.map(&:chomp).chunk {|st| st.empty?}
  .reject {|a| a.first}.map {|a| a.last}.each do |field|
  co = 0
  L.times do |y|
    L.times do |x|
      if field[y][x] == "1"
        co += 1
        delete(field, x, y)
      end
    end
  end
  puts co
end

　

0068 Enclose Pins with a Rubber Band

include Math

until (n = $<.gets.to_i).zero?
  points = Array.new(n) { Complex(*$<.gets.split(",").map(&:to_f))  }
  ym = points.map(&:imaginary).max
  start_po = po0 = points.find {|po| po.imaginary == ym}
  prev_arg = PI
  
  result = loop do
    points = (points - [start_po] + [po0]).uniq
    selected = points.map {|po| [po - start_po, po]}
      .reject {|pos| pos.first == 0}
      .sort_by {|pos| a = pos.first.angle + PI - prev_arg; a >= 0 ? a : a + 2 * PI}
      .first.last
    points.select! {|po| po != start_po}
    break points.size - 1 if selected == po0    # po0の分だけ1引く
    prev_arg = (selected - start_po).angle + PI
    start_po = selected
  end
  
  puts result
end

ムズカしかったので一発でいってうれしいが、しかし複雑すぎる。もっといい解法がないかな。
Ruby で解けている人は多くない。

問題はこれ。考え方としては
1. 点を複素数としてオブジェクト化する。
2. 確実に外にある点（po0）をひとつ選ぶ。
3. 残りの点のすべてへの方向を計算し、いちばん少ない角度で左回りになる点を選ぶ。
4. 選んだ点で同様に (3) を繰り返し、一周したところでおしまい。
5. 残った点の数が求めるもの。
つまり、反時計回りで一周して、周にない点の数を求めるということ。
　

0069 Drawing Lots II

あみだくじ。与えられたあみだくじで特定の場所を選んで当たりに到達するか調べる。もしそれでダメなら、一本だけ横線を加えてもよい。という問題（参照）。

def hit(n, m, goal, d, dans)
  h = 0
  until h == d
    yoko = dans[h]
    if m != n - 1 and yoko[m] == 1
      m += 1
    elsif m.nonzero? and yoko[m - 1] == 1
      m -= 1
    end
    h += 1
  end
  goal == m
end

until (n = $<.gets.to_i).zero?
  m    = $<.gets.to_i - 1
  goal = $<.gets.to_i - 1
  d    = $<.gets.to_i
  dans = Array.new(d) { $<.gets.chomp.chars.map(&:to_i) }
  
  if hit(n, m, goal, d, dans)
    puts 0
  else
    try = ->{
      d.times do |h|
        ([0] + dans[h] + [0]).each_cons(3).with_index do |a, x|
          if a.sum.zero?
            dans[h][x] = 1
            return "#{h + 1} #{x + 1}" if hit(n, m, goal, d, dans)
            dans[h][x] = 0
          end
        end
      end
      1
    }
    puts try.()
  end
end

これも一発でいった。しかし、段々ムズカしくなってきた…。ふう。
これも Ruby で解いた人は少ない。
　

0070 Tag Discussion Solution Statistics Submit

def solve(ary, n, s)
  co = 0
  ary.each do |i|
    s1 = s - i * n
    if n == 1
      if s1.zero?
        co += 1
      end
    elsif s1 > 0
      co += solve(ary - [i], n - 1, s1)
    end
  end
  co
end

$<.readlines.map {|a| a.split.map(&:to_i)}.each do |n, s|
  puts solve([*0..9], n, s)
end

たぶんこれでいけるのだけれど、時間制限に引っかかる。問題はこれ。よく考えないとな。

デバッグ用。

io.readlines.map {|a| a.split.map(&:to_i)}.each do |n, s|
  solve = ->(ary, n, s1, st = "") {
    co = 0
    ary.each do |i|
      s2 = s1 - i * n
      st1 = st + "#{i}*#{n} + "
      if n == 1
        if s2.zero?
          co += 1
          puts st1[0..-4] + " = #{s}"
        end
      elsif s2 > 0
        co += solve.(ary - [i], n - 1, s2, st1)
      end
    end
    co
  }
  puts solve.([*0..9], n, s)
end

これはたとえば n = 5, s = 24 でこうなる。

0*5 + 1*4 + 2*3 + 3*2 + 8*1 = 24
0*5 + 1*4 + 2*3 + 4*2 + 6*1 = 24
0*5 + 1*4 + 2*3 + 5*2 + 4*1 = 24
0*5 + 1*4 + 3*3 + 2*2 + 7*1 = 24
0*5 + 1*4 + 4*3 + 3*2 + 2*1 = 24
0*5 + 2*4 + 1*3 + 3*2 + 7*1 = 24
0*5 + 2*4 + 1*3 + 4*2 + 5*1 = 24
0*5 + 2*4 + 1*3 + 5*2 + 3*1 = 24
0*5 + 2*4 + 3*3 + 1*2 + 5*1 = 24
0*5 + 3*4 + 1*3 + 2*2 + 5*1 = 24
0*5 + 3*4 + 2*3 + 1*2 + 4*1 = 24
1*5 + 0*4 + 2*3 + 3*2 + 7*1 = 24
1*5 + 0*4 + 2*3 + 4*2 + 5*1 = 24
1*5 + 0*4 + 2*3 + 5*2 + 3*1 = 24
1*5 + 0*4 + 3*3 + 2*2 + 6*1 = 24
1*5 + 0*4 + 3*3 + 4*2 + 2*1 = 24
1*5 + 0*4 + 4*3 + 2*2 + 3*1 = 24
1*5 + 2*4 + 0*3 + 3*2 + 5*1 = 24
1*5 + 2*4 + 0*3 + 4*2 + 3*1 = 24
2*5 + 0*4 + 1*3 + 3*2 + 5*1 = 24
2*5 + 0*4 + 1*3 + 4*2 + 3*1 = 24
2*5 + 1*4 + 0*3 + 3*2 + 4*1 = 24
22

フーム。

関係性を調べてみる。

table = []
s = 0
while s < 25
  st = ""
  table << (1..10).map {|n| "%3d" % solve([*0..9], n, s)}.join(" ")  
  s += 1
end
table.reverse_each {|l| puts l}

結果。

  0   1  16  43  22   0   0   0   0   0
  0   3  27  51  13   0   0   0   0   0
  0   3  21  35   7   0   0   0   0   0
  0   3  18  36   5   0   0   0   0   0
  0   4  20  26   1   0   0   0   0   0
  0   5  23  29   0   0   0   0   0   0
  0   3  13  19   0   0   0   0   0   0
  0   5  20  23   0   0   0   0   0   0
  0   4  14  15   0   0   0   0   0   0
  0   4  13  14   0   0   0   0   0   0
  0   4  12  11   0   0   0   0   0   0
  0   5  14   9   0   0   0   0   0   0
  0   3   7   4   0   0   0   0   0   0
  0   5  11   4   0   0   0   0   0   0
  0   4   8   1   0   0   0   0   0   0
  1   4   5   0   0   0   0   0   0   0
  1   4   4   0   0   0   0   0   0   0
  1   4   5   0   0   0   0   0   0   0
  1   2   2   0   0   0   0   0   0   0
  1   3   3   0   0   0   0   0   0   0
  1   2   1   0   0   0   0   0   0   0
  1   1   0   0   0   0   0   0   0   0
  1   1   0   0   0   0   0   0   0   0
  1   1   0   0   0   0   0   0   0   0
  1   0   0   0   0   0   0   0   0   0

うーん。

かなり考えたのだが、これでも時間オーバー。メモ化。

@memo = {}

def solve(ary, n, s)
  hash = ary.map {|i| [11, 13, 17, 19, 23, 29, 31, 37, 41, 43][i]}.inject(&:*)
  hash *= n
  return @memo[[hash, s]] if @memo[[hash, s]]
  co = 0
  ary.each do |i|
    s1 = s - i * n
    if n == 1
      if s1.zero?
        co += 1
      end
    elsif s1 > 0
      co += solve(ary - [i], n - 1, s1)
    end
  end
  @memo[[hash, s]] = co
end

$<.readlines.map {|a| a.split.map(&:to_i)}.each do |n, s|
  puts solve([*0..9], n, s)
end

このアプローチでは無理かな。

他の人の回答（参照）。

$sumhash = {}

def check_sum(n, s, used = 0)
  key = "#{n},#{s},#{used}"
  return $sumhash[key] if ! $sumhash[key].nil?
 
  if n == 0
    return s == 0 ? 1 : 0
  end
 
  count = 0
 
  10.times do |i|
    b = 1 << i
    ni = n * i
    if (used & b).zero? and s >= ni
      used |= b
      count += check_sum(n - 1, s - ni, used)
      used ^= b
    end
  end
 
  return $sumhash[key] = count
end
 
while (line = $<.gets)
  n, s = line.chomp.split(" ").map{|s| s.to_i}
  puts check_sum(n, s)
end

なんと、じつに素直なアプローチ。で、あとはメモ化かあ。全然自分の知っている方法だけで解けるではないか。うーん、まだまだだなあ…。
ただ、ビット演算で or で立てたフラグを消すのが xor というのは気づかなかった。これは勉強になった。