Ruby のバージョンアップ

まずは rbenv install --list の更新(参照)。

$ cd ~/.rbenv/plugins/ruby-build 
$ git pull origin master

 
インストール。

$ rbenv install 2.x.x
$ rbenv global 2.x.x    #例

 
ローカルな Gem の更新。該当ディレクトリで

$ rbenv exec gem install bundler
$ bundle install

を実行する(参照)。
 

追記(2023/9/5)

Ruby 3.1 では以下が必要。

$ sudo apt-get install -y libssl-dev

Ruby 3.2 では以下が必要。

$ sudo apt install -y libyaml-dev

AOJ(問題集)9

AIZU ONLINE JUDGE: Programming Challenge
 

0081 A Symmetric Point

require 'matrix'

$<.readlines.map {|l| l.split(",").map(&:to_f)}.each do |x1, y1, x2, y2, xq, yq|
  p1 = Vector[x1, y1]
  n  = Vector[y2 - y1, x1 - x2].normalize
  q  = Vector[xq, yq]
  d = (p1 - q).dot(n)
  r = q + (2 * d) * n
  printf "%.6f %.6f\n", r[0], r[1]
end

わりとうまく解けた。
 

0082 Flying Jenny

table = [4, 1, 4, 1, 2, 1, 2, 1]

$<.readlines.map {|l| l.split.map(&:to_i)}.each do |persons|
  result = (0..7).map do |i|
    order = table.rotate(i)
    left = persons.map.with_index do |n, j|
      a = n - order[j]
      a < 0 ? 0 : a
    end.sum
    [left, order]
  end.sort_by {|d| d.first}
  min = result.first.first
  result = result.select {|d| d.first == min}.sort_by {|d| d.last.join.to_i}.first
  puts result.last.join(" ")
end

 

0083 Era Name Transformation

require 'date'

table = [["pre-meiji", [   1,  1,  1], [1868,  9,  7]],
         ["meiji"    , [1868,  9,  8], [1912,  7, 29]],
         ["taisho"   , [1912,  7, 30], [1926, 12, 24]],
         ["showa"    , [1926, 12, 25], [1989,  1,  7]],
         ["heisei"   , [1989,  1,  8], [2020,  1,  1]]]
table.map! {|n, d1, d2| [n, Date.new(*d1), Date.new(*d2)]}

$<.readlines.map {|l| Date.new(*l.split.map(&:to_i))}.each do |day|
  table.each do |name, d1, d2|
    if day.between?(d1, d2)
      if name == "pre-meiji"
        puts name
      else
        puts "#{name} #{day.year - d1.year + 1} #{day.month} #{day.day}"
      end
    end
  end
end

 

0084 Search Engine

text = $<.gets.chomp
puts text.split(/[ \.,]/).select {|w| w.length.between?(3, 6)}.join(" ")

 

0085 Joseph's Potato

until (a = $<.gets.split.map(&:to_i)) == [0, 0]
  n, m = a
  circle = [*1..n]
  try = ->(po) {
    return circle.first if circle.size == 1
    po += m - 1
    po -= circle.size while po >= circle.size
    circle = circle[0...po] + circle[po + 1..-1]
    try.(po)
  }
  puts try.(n)
end

 

0086 Patrol

loop do
  roots = Hash.new([])
  i = 0
  loop do
    exit unless (l = io.gets)
    break if (l = l.split.map(&:to_i)) == [0, 0]
    a, b = l
    roots[a] += [[b, i]]
    roots[b] += [[a, i]]
    i += 1
  end
  
  try = ->(spot, visited) {
    if spot == 2
      return true if visited == 2 ** i - 1
    else
      roots[spot].each do |nxt, root|
        next if (2 ** root & visited).nonzero?
        return true if try.(nxt, 2 ** root | visited)
      end
    end
    false
  }
  puts try.(1, 0) ? "OK" : "NG"
end

これは時間オーバー。バックトラック法しか思いつかない。ちょっと他の人の回答を見たい。

例えばこの回答

loop do
  spots = []
 
  loop do
    line = $<.gets
    exit if line.nil?
    p0, p1 = line.chomp.split(" ").map(&:to_i)
    break if p0.zero? and p1.zero?
    p0 -= 1
    p1 -= 1
    spots[p0] = spots[p0] ? (spots[p0] + 1) : 1
    spots[p1] = spots[p1] ? (spots[p1] + 1) : 1
  end
  #p spots
 
  ok = true
 
  if spots[0].even? or spots[1].even?
    ok = false
  else
    (2...spots.length).each do |i|
      if spots[i].odd?
        ok = false
        break
      end
    end
  end
 
  puts ok ? "OK" : "NG"
end

これは…、瞬殺である。配列 spots はその場所から出ている道の数を表わしている。
なるほど、道が一筆書きになればよいわけだな。そんな簡単なことに気づかなかったとは!
 

0087 Strange Mathematical Expression

逆ポーランド記法

$<.readlines.map {|l| l.chomp.split}.each do |data|
  stack = []
  while (x = data.shift)
    if %w(+ - * /).include?(x)
      a, b = stack.pop, stack.pop
      stack << eval("#{b}.to_f #{x} #{a}")
    else
      stack << x
    end
  end
  printf "%.6f\n", stack.first
end

 

0088 The Code A Doctor Loved

table1 = {"'"=>"000000", ","=>"000011", "-"=>"10010001", "."=>"010001",
  "?"=>"000001", "A"=>"100101", "B"=>"10011010", "C"=>"0101", "D"=>"0001",
  "E"=>"110", "F"=>"01001", "G"=>"10011011", "H"=>"010000", "I"=>"0111",
  "J"=>"10011000", "K"=>"0110", "L"=>"00100", "M"=>"10011001",
  "N"=>"10011110", "O"=>"00101", "P"=>"111", "Q"=>"10011111", "R"=>"1000",
  "S"=>"00110", "T"=>"00111", "U"=>"10011100", "V"=>"10011101",
  "W"=>"000010", "X"=>"10010010", "Y"=>"10010011", "Z"=>"10010000", " "=>"101"}
table2 = {"00000"=>"A", "00001"=>"B", "00010"=>"C", "00011"=>"D", "00100"=>"E",
  "00101"=>"F", "00110"=>"G", "00111"=>"H", "01000"=>"I", "01001"=>"J",
  "01010"=>"K", "01011"=>"L", "01100"=>"M", "01101"=>"N", "01110"=>"O",
  "01111"=>"P", "10000"=>"Q", "10001"=>"R", "10010"=>"S", "10011"=>"T",
  "10100"=>"U", "10101"=>"V", "10110"=>"W", "10111"=>"X", "11000"=>"Y",
  "11001"=>"Z", "11010"=>" ", "11011"=>".", "11100"=>",", "11101"=>"-",
  "11110"=>"'", "11111"=>"?"}

$<.readlines.each do |line|
  line.chomp!
  text = ""
  line.each_char {|c| text += table1[c]}
  l = text.length % 5
  text += "0" * (5 - l) if l > 0
  
  result = ""
  until text.empty?
     result += table2[text[0, 5]]
     text = text[5..-1]
  end
  puts result
end

 

0089 The Shortest Path on A Rhombic Path

lines = $<.readlines.map {|l| l.split(",").map(&:to_i)}
ln = lines.size / 2 + 1

up = ->(n, sums) {
  return sums if n == ln
  nxt = Array.new(n + 1, 0)
  sums.each_index do |i|
    nxt[i] = sums[i] + lines[n][i] if i.zero?
    nxt[i + 1] = sums[i, 2].max + lines[n][i + 1]
  end
  up.(n + 1, nxt)
}
mid = up.(1, lines.first)

down = ->(n, sums) {
  return sums.first if sums.size == 1
  nxt = sums.each_cons(2).map.with_index do |pair, i|
    lines[n][i] + pair.max
  end
  down.(n + 1, nxt)
}
puts down.(ln, mid)

こんな面倒なやり方しか思いつかなかった。むずかしかったので一発でいってよかった。ダメだったら考え直す気力がない…。
 

0090 Overlaps of Seals

全然思いつかない…。他人の回答を見る(自己流に改変しています)。

require 'matrix'

DELTA = 1e-6
 
until (n = $<.gets.to_i).zero?
  points = []
  n.times do
    points << Vector[*$<.gets.chomp.split(",").map(&:to_f)]
  end
 
  cps = []
  points.each_with_index do |p0, i|
    (i + 1...n).each do |j|
      p1 = points[j]
      v = p1 - p0
      d = v.norm
      if d <= 1.0 + DELTA
        hd = d / 2
        ul = Math.sqrt(1.0 - hd * hd)
 
        u = Vector[-v[1], v[0]] / d * ul
        c = (p0 + p1) / 2
 
        cps << c + u
        cps << c - u
      end
    end
  end
 
  max_ov = 1
  cps.each do |cp|
    ov = 0
    points.each do |point|
      ov += 1 if (point - cp).norm <= 1.0 + DELTA
    end
    max_ov = ov if max_ov < ov
  end
  puts max_ov
end

いやあ、すごい。これは思いつかなかったなあ…。
20190102162110

AOJ(問題集)8

AIZU ONLINE JUDGE: Programming Challenge
 

0071 Bombs Chain

$<.gets.to_i.times do |co|
  $<.gets
  field = Array.new(8) {$<.gets.chomp.chars.map(&:to_i)}
  xi, yi = $<.gets.to_i, $<.gets.to_i
  
  blast = ->(x, y) {
    field[y][x] = 2
    3.times do |i|
      [[1, 0], [0, -1], [-1, 0], [0, 1]].each do |dx, dy|
        x1, y1 = x + dx * (i + 1), y + dy * (i + 1)
        next if x1 < 0 or x1 >= 8 or y1 < 0 or y1 >= 8
        if field[y1][x1] == 1
          blast.(x1, y1)
        else
          field[y1][x1] = 2
        end
      end
    end
  }
  blast.(xi - 1, yi - 1)
  
  puts "Data #{co + 1}:"
  puts field.map {|line| line.map {|a| a == 2 ? 0 : a}.join}
end

 

0072 Carden Lantern

until (n = $<.gets.to_i).zero?
  m = $<.gets.to_i
  table = Array.new(m) {$<.gets.split(",").map(&:to_i)}
  table.map! {|a, b, d| [a, b, d / 100 - 1]}
  
  min = Float::INFINITY
  (1..m).each do |i|
    table.combination(i) do |paths|
      next unless paths.inject([]) {|a, path| a + path[0, 2]}.uniq.sort == [*0...n]
      n = paths.map{|path| path.last}.sum
      min = n if n < min
    end
  end
  puts min
end

まずはこれで解ける筈だが、時間オーバー。そりゃそうだ。
ふと、動的計画法で解けることに気がつく。これはよいアイデア

until (n = $<.gets.to_i).zero?
  m = $<.gets.to_i
  field = []
  Array.new(m) {$<.gets.split(",").map(&:to_i)}.each do |a, b, d|
    n = d / 100 - 1
    field += field.map {|spots, num| [(spots + [a, b]).uniq, num + n]}
    field << [[a, b], n]
  end
  puts field.select {|x| x.first.size == n}.sort_by {|x| x.last}.first.last
end

しかしメモリオーバー。ならばと訪れた史跡のチェックをビット演算でおこない、さらに配列の代わりにハッシュを使って省メモリ化。

until (n = $<.gets.to_i).zero?
  m = $<.gets.to_i
  field = {0=>0}
  Array.new(m) {$<.gets.split(",").map(&:to_i)}.each do |a, b, d|
    n = d / 100 - 1
    added = {}
    field.each do |spots, num|
      spots |= 2 ** a
      spots |= 2 ** b
      added[spots] = num + n if !added[spots] or num + n < added[spots]
    end
    field.merge!(added) {|spots, b, f| [b, f].min}
  end
  puts field[2 ** n - 1]
end

それでもメモリオーバー。うーん。いきづまった。
まったく別の考え方で。後戻りも含めて幅優先探索し、適当なところで打ち切る。

until (n = $<.gets.to_i).zero?
  m = $<.gets.to_i
  cpd = Hash.new([])
  table = Array.new(m) {$<.gets.split(",").map(&:to_i)}
  table.map! {|a, b, d| [a, b, d / 100 - 1]}
  table.each_with_index do |x, i|
    cpd[x[0]] += [i]
    cpd[x[1]] += [i]
  end
  stack = [[0, 1, 0, 0]]    # 現在位置、行った場所、灯籠の数、使った道
  result = loop do
    nxt = stack.shift
    cpd[nxt[0]]
    .map {|tn| [tn, (table[tn][0, 2] - [nxt[0]]).first, table[tn].last]}
    .each do |tn, spot, n|
      nxt_lnt = nxt[2]
      nxt_lnt += n if (2 ** spot & nxt[1]).zero?
      stack << [spot, 2 ** spot | nxt[1], nxt_lnt, 2 ** tn | nxt[3]]
    end
    tmp1 = stack.select {|x| x[1] == 2 ** n - 1}
    tmp2 = tmp1 .select {|x| x[3] == 2 ** m - 1}
    break tmp1 unless tmp2.empty?
  end
  puts result.map {|x| x[2]}.min
end

今度は時間オーバー。うーむ。
後戻りは一度しかできないとする。

until (n = $<.gets.to_i).zero?
  m = $<.gets.to_i
  cpd = Hash.new([])
  table = Array.new(m) {$<.gets.split(",").map(&:to_i)}
  table.map! {|a, b, d| [a, b, d / 100 - 1]}
  table.each_with_index do |x, i|
    cpd[x[0]] += [i]
    cpd[x[1]] += [i]
  end
  result = []
  stack = [[0, 1, 0, 0, 0]]    # 現在位置、行った場所、灯籠の数、使った道、道は戻ったことがあるか
  while (nxt = stack.shift)
    if nxt[1] == 2 ** n - 1
      result << nxt[2]
    else
      cpd[nxt[0]]
      .map {|path| [path, (table[path][0, 2] - [nxt[0]]).first, table[path].last]}
      .each do |path, spot, n|
        next if (nxt[4] & 2 ** path).nonzero?    # 道を戻るのは一度だけ
        # 行った場所で使っていない道だとダメ
        next if (2 ** spot & nxt[1]).nonzero? and (2 ** path & nxt[3]).zero?
        nxt_lnt = nxt[2]
        nxt_lnt += n if (2 ** spot & nxt[1]).zero?
        f = nxt[4]
        f |= 2 ** path if (2 ** path & nxt[3]).nonzero?
        stack << [spot, 2 ** spot | nxt[1], nxt_lnt, 2 ** path | nxt[3], f]
      end
    end
  end
  puts result.min
end

今度も時間オーバー。うーん、ここまで考えたのだが。
またまったく別の方法。すべて足しておいて、削れるだけ削る。

until (n = $<.gets.to_i).zero?
  m = $<.gets.to_i
  init_spots = Array.new(m, 0)
  tourou = 0
  table = Array.new(m) {$<.gets.split(",").map(&:to_i)}.map do |a, b, d|
    init_spots[a] += 1
    init_spots[b] += 1
    n = d / 100 - 1
    tourou += n
    [a, b, n]
  end
  min = tourou
  solve = ->(i, spots, t) {
    min = t if t < min
    return if i == m
    solve.(i + 1, spots, t)
    now = table[i]
    return if spots[now[0]] == 1 or spots[now[1]] == 1
    spots[now[0]] -= 1
    spots[now[1]] -= 1
    solve.(i + 1, spots, t - now[2])
    spots[now[0]] += 1
    spots[now[1]] += 1
  }
  solve.(0, init_spots, tourou)
  puts min
end

これも時間オーバー。

他の人の回答(参照)。

until (n = $<.gets.chomp.to_i).zero?
  edges = []
  $<.gets.chomp.to_i.times do
    e = $<.gets.chomp.split(",").map(&:to_i)
    e[2] = e[2] / 100 - 1
    edges << e
  end
  #p [n, m, edges]
  
  #灯籠の数の少ない順に並べる
  edges.sort! {|a, b| a[2] <=> b[2]}
 
  nodes = Array.new(n, false)
 
  connected = [0]
  nodes[0] = true
 
  sumw = 0
 
  while connected.length < n
    (0...edges.length).each |i|
      n0, n1, w = edges[i]
 
      if nodes[n0] or nodes[n1]
        if !nodes[n0]
          nodes[n0] = true
          connected << n0
          sumw += w
        elsif !nodes[n1]
          nodes[n1] = true
          connected << n1
          sumw += w
        end
 
        edges.delete_at(i)
        break
      end
    end
  end
 
  puts sumw
end

なるほど、灯籠の少ない順にならべておいて、あとは史跡 0 から順に繋げていくと。なるほどなあー。
 

0073 Surface Area of Quadrangular Pyramid

loop do
  x, h = $<.gets.to_i, $<.gets.to_i
  break if x.zero? and h.zero?
  puts x * x + Math.sqrt(h * h + (x / 2.0) ** 2) * x * 2
end

 

0074 Videotape

loop do
  t, h, s = $<.gets.split.map(&:to_i)
  break if t == -1 and h == -1 and s == -1
  left = 120 * 60 - (t * 3600 + h * 60 + s)
  output = ->(t) {
    printf "%02d:%02d:%02d\n", h = t / 3600, (m = t / 60) - h * 60, t - m * 60
  }
  output.(left)
  output.(left * 3)
end

 

0075 BMI

$<.readlines.map {|l| l.split(",").map(&:to_f)}
  .select {|s, w, h| w / h ** 2 >= 25.0}.each {|a| puts a.first.to_i}

 

0076 Treasure Hunt II

until (n = $<.gets.to_i) == -1
  x, y = 1.0, 0.0
  (n - 1).times do
    l = Math.sqrt(x ** 2 + y ** 2)
    x, y = x - y / l, y + x / l
  end
  puts x, y
end

 

0077 Run Length

$<.readlines.map(&:chomp).each do |given|
  po = 0
  text = ""
  while po < given.length
    if given[po] == "@"
      text += given[po + 2] * given[po + 1].to_i
      po += 3
    else
      text += given[po]
      po += 1
    end
  end
  puts text
end

 

0078 Magic Square

until (n = $<.gets.to_i).zero?
  square = Array.new(n) {[0] * n}
  
  set = ->(i, x, y) {
    return if i > n * n
    if x < 0
      set.(i, n - 1, y)
    elsif x >= n
      set.(i, 0, y)
    elsif y >= n
      set.(i, x, 0)
    elsif square[y][x].nonzero?
      set.(i, x - 1, y + 1)
    else
      square[y][x] = i
      set.(i + 1, x + 1, y + 1)
    end
  }
  set.(1, n / 2, n / 2 + 1)
  
  square.each do |l|
    puts l.map {|x| sprintf("%4d", x)}.join
  end
end

 

0079 Area of Polygon

多角形の面積。

include Math

points = $<.readlines.map {|l| Complex(*l.split(",").map(&:to_f))}
start_po = p0 = points.sort_by(&:imaginary).last
prev_arg = PI
  
e = Enumerator.new do |y|
  loop do
    points -= [start_po]
    break if points.empty?
    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
    y << selected
    prev_arg = (selected - start_po).angle + PI
    start_po = selected
  end
end

result = e.each_cons(2).map do |p1, p2|
  a = (p1 - p0).abs
  b = (p2 - p0).abs
  c = (p2 - p1).abs
  z = (a + b + c) / 2.0
  sqrt(z * (z - a) * (z - b) * (z - c))
end.sum
puts result

意外とむずかしくて、かなり大袈裟なことをしている。0068 の回答参照。
他の人の回答にはすごいのがあって、例えばどうしてこれで求まるのかわからない。
ああ、そうか、問題をよく読んでいなかったのか! よくあるな、これ。点が順番に並んでいるのだ。じゃあ簡単だ…。

これでOK。

require 'matrix'

p0, *points = $<.readlines.map {|l| Vector[*l.split(",").map(&:to_f)]}
result = points.each_cons(2).map do |p1, p2|
  a = (p1 - p0).norm
  b = (p2 - p0).norm
  c = (p2 - p1).norm
  z = (a + b + c) / 2
  Math.sqrt(z * (z - a) * (z - b) * (z - c))
end.sum
puts result

前の回答だと、点の並びが任意でも計算できる。
 

0080 Third Root

until (q = $<.gets.to_f) == -1
  x = q / 2.0
  result = loop do
    x -= (x ** 3 - q) / (3 * x ** 2)
    break x if (x ** 3 - q).abs < 0.00001 * q
  end
  puts result
end

古い Linux Kernel のインストール

askubuntu.comここが参考になる。
 
例えばここここここから

を拾ってきてひとつのフォルダに入れ、

$ sudo dpkg -i *.deb

を実行するということらしい。
 
あとは Grub の変更が必要。自分は Grub Customizer でやる。
 
※追記
こんなことをするくらいなら Synaptic で入れた方がよい。



※再追記(2019/8/11)
https://kernel.ubuntu.com/~kernel-ppa/mainline/
ここからv4.4.189を拾ってくる。

  • linux-headers-4.4.189-0404189_4.4.189-0404189.201908111150_all.deb
  • linux-headers-4.4.189-0404189-generic_4.4.189-0404189.201908111150_amd64.deb
  • linux-image-unsigned-4.4.189-0404189-generic_4.4.189-0404189.201908111150_amd64.deb
  • linux-modules-4.4.189-0404189-generic_4.4.189-0404189.201908111150_amd64.deb

をひとつのフォルダに入れて

$ sudo dpkg -i *.deb
$ sudo update-grub

 
あとは Grub Customizer でやった。

$ sudo uname -a
Linux tomoki-ThinkPad-T410 4.4.189-0404189-generic #201908111150 SMP Sun Aug 11 11:53:09 UTC 2019 x86_64 x86_64 x86_64 GNU/Linux

OK!

AOJ(問題集)7

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 というのは気づかなかった。これは勉強になった。

AOJ(問題集)6

AIZU ONLINE JUDGE: Programming Challenge
 

0051 Differential II

$<.readlines.drop(1).map {|a| a.chomp.chars.map(&:to_i).sort}.each do |ary|
  puts ary.reverse.join.to_i - ary.join.to_i
end

 

0052 Factorial II

until (n = $<.gets.to_i).zero?
  five = n / 5
  f = ->(x) {
    return five if n < x
    five += n / x
    f.(x * 5)
  }
  puts f.(25)
end

これはちょっと考えました。
 

0053 Sum of Prime Numbers

require 'prime'

nums = []
h = {}
until (i = $<.gets.to_i).zero?
  nums << i
  h[i] = 0
end
max_num = nums.max

sum = 0
Prime.each.with_index do |prime, i|
  break if i + 1 > max_num
  sum += prime
  h[i + 1] = sum if h[i + 1]
end
nums.each {|j| puts h[j]}

与えられた値が重複しているのだな。結構いい成績だった。
 

0054 Sum of Nth decimal places

$<.readlines.map {|a| a.split.map(&:to_i)}.each do |a, b, n|
  f = ->(x, i = 1, sum = 0) {
    return sum if i > n or x.zero?
    f.(x * 10 % b, i + 1, sum + x * 10 / b)
  }
  puts f.(a % b)
end

 

0055 Sequence

$<.readlines.map(&:to_f).each do |x|
  sum = 0
  solve = ->(n, i = 1) {
    sum += n
    return sum if i == 10
    (i + 1).even? ? solve.(n * 2.0, i + 1) : solve.(n / 3.0, i + 1)
  }
  puts solve.(x)
end

 

0056 Goldbach's Conjecture

require 'prime'

h = {}
primes = Prime.each(50000).to_a
primes.each {|pr| h[pr] = true}
until (n = $<.gets.to_i).zero?
  co = 0
  if n.odd?
    co = 1 if h[n - 2]
  else
    primes.each do |pr|
      break if pr > n / 2
      co += 1 if h[n - pr]
    end 
  end
  puts co
end

何か変なミスをしていた。何とタイムは挑戦者中最速。
 

0057 The Number of Area

$<.readlines.map(&:to_i).each do |n|
  puts 2 + (n - 1) * (n + 2) / 2
end

 

0058 Orthogonal

$<.readlines.map {|l| l.split.map(&:to_r)}.each do |xa, ya, xb, yb, xc, yc, xd, yd|
  x1, y1 = xb - xa, yb - ya
  x2, y2 = xd - xc, yd - yc
  puts x1 * x2 + y1 * y2 == 0 ? "YES" : "NO"
end

 

0059 Intersection of Rectangles

while (st = $<.gets)
  xa1, ya1, xa2, ya2, xb1, yb1, xb2, yb2 = st.split.map(&:to_f)
  if !(xa1 > xb2 or xa2 < xb1 or ya1 > yb2 or ya2 < yb1)
    puts "YES"
  else
    puts "NO"
  end
end

こんなに簡単なものが条件を見落としていた…。
 

0060 Card Game

$<.readlines.map {|a| a.split.map(&:to_i)}.each do |my1, my2, opp1|
  deck = [*1..10] - [my1, my2, opp1]
  limit = 20 - (my1 + my2)
  p = 0
  deck.each do |opp2|  
    n = (deck - [opp2]).take_while {|i| i <= limit}.size
    p += 1/7r * Rational(n, 6)
  end
  puts p >= 1/2r ? "YES" : "NO"
end

AOJ(問題集)5

AIZU ONLINE JUDGE: Programming Challenge
 

0041 Expression

def solve(ary)
  if ary.size <= 1
    return ary[0] if eval(ary[0]) == 10
  else
    idxs = [*0...ary.size]
    idxs.combination(2) do |i, j|
      a, b = ary[i], ary[j]
      nxt = (idxs - [i, j]).map{|x| ary[x]}
      ["(#{a} + #{b})", "(#{a} - #{b})", "(#{b} - #{a})", "#{a} * #{b}"].each do |st|
        result = solve(nxt + [st])
        return result if result
      end
    end
  end
  nil
end

until (given = $<.gets.chomp.split) == ["0", "0", "0", "0"]
  ans = solve(given)
  puts ans ? ans : 0
end

自信作(笑)。
 

0042 A Thief

i = 1
until (furoshiki = $<.gets.to_i).zero?
  table = {0 => 0}
  Array.new($<.gets.to_i) {$<.gets.split(",").map(&:to_i)}.each do |v, w|
    h = Hash.new(0)
    table.each {|key, value| h[key + w] = table[key] + v if key + w <= furoshiki}
    table.merge!(h) {|k, v1, v2| [v1, v2].max}
  end
  m = table.values.max
  result = table.select {|k, v| v == m}.sort {|a, b| a[0] <=> b[0]}.first
  puts "Case #{i}:", result[1], result[0]
  i += 1
end

典型的な動的計画法
 

0043 Puzzle

def check(table)
  result = 0
  if table.sum <= 2
    result = 1 if table.find {|x| x == 2}
  else
    (1..7).each do |i|
      tmp = table.dup
      if tmp[i].nonzero? and tmp[i + 1].nonzero? and tmp[i + 2].nonzero?
        3.times {|x| tmp[i + x] -= 1}
        result += check(tmp)
        return 1 if result.nonzero?
      end
      (1..9).each do |j|
        tmp1 = table.dup
        if tmp1[j] >= 3
          tmp1[j] -= 3
          result += check(tmp1)
          return 1 if result.nonzero?
        end
      end
    end
  end
  result
end

$<.readlines.map(&:chomp).map {|n| n.chars.map(&:to_i)}.each do |data|
  table = Array.new(10, 0)
  data.each {|i| table[i] += 1}
  result = (1..9).map do |i|
    added = table.dup
    added[i] += 1
    next if added[i] > 4
    check(added).nonzero? ? i : nil
  end.compact
  puts result.empty? ? 0 : result.join(" ")
end

3.09秒かかった。

他の人の回答を見ていて気づいたが、check() メソッド内のループはネストさせる必要がない。書き直すと

def check(table)
  result = 0
  if table.sum <= 2
    table.find {|x| x == 2}
  else
    (1..7).each do |i|
      tmp = table.dup
      if tmp[i].nonzero? and tmp[i + 1].nonzero? and tmp[i + 2].nonzero?
        3.times {|x| tmp[i + x] -= 1}
        return true if check(tmp)
      end
    end
    (1..9).each do |j|
      tmp1 = table.dup
      if tmp1[j] >= 3
        tmp1[j] -= 3
        return true if check(tmp1)
      end
    end
    false
  end
end

$<.readlines.map(&:chomp).map {|n| n.chars.map(&:to_i)}.each do |data|
  table = Array.new(10, 0)
  data.each {|i| table[i] += 1}
  result = (1..9).map do |i|
    added = table.dup
    added[i] += 1
    next if added[i] > 4
    check(added) ? i : nil
  end.compact
  puts result.empty? ? 0 : result.join(" ")
end

これで 0.10秒。充分速い。
 

0044 Prime Number II

require 'prime'

$<.readlines.map(&:to_i).each do |n|
 a = (n - 1).step(0, -1) {|i| break i if Prime.prime?(i)}
 b = (n + 1).step {|i| break i if Prime.prime?(i)}
 puts "#{a} #{b}"
end

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

0045 Sum and Average

all_price = amount = i = 0
$<.readlines.map {|x| x.split(",").map(&:to_i)}.each do |price, n|
  all_price += price * n
  amount += n
  i += 1
end
puts all_price
puts (amount / i.to_f).round

 

0046 Differential

max, min = 0, Float::INFINITY
$<.readlines.map(&:to_f).each do |h|
  max = h if h > max
  min = h if h < min
end
printf "%.1f\n", max - min

 

0047 Cup Game

place = "A"
$<.readlines.map {|x| x.chomp.split(",")}.each do |a, b|
  if place == a
    place = b
  elsif place == b
    place = a
  end
end
puts place

 

0048 Class

table = [["light fly", 0, 48.0], ["fly", 48.0, 51.0], ["bantam", 51.0, 54.0],
         ["feather", 54.0, 57.0], ["light", 57.0, 60.0],
         ["light welter", 60.0, 64.0], ["welter", 64.0, 69.0],
         ["light middle", 69.0, 75.0], ["middle", 75.0, 81.0],
         ["light heavy", 81.0, 91.0], ["heavy", 91.0, Float::INFINITY]]
$<.readlines.map(&:to_f).each do |w|
  table.each {|name, bottom, top| puts name if bottom < w and w <= top}
end

 

0049 Blood Groups

table = {"A"=>0, "B"=>1, "AB"=>2, "O"=>3}
nums = Array.new(4, 0)
$<.readlines.map {|a| a.chomp.split(",").last}.each do |type|
  nums[table[type]] += 1
end
puts nums

 

0050 Apple and Peach

st = $<.gets.chomp
po = 0
result = ""
while po < st.length
  case st[po, 5]
  when "apple"
    result += "peach"
    po += 5
  when "peach"
    result += "apple"
    po += 5
  else
    result += st[po]
    po += 1
  end
end
puts result

Windows フリーゲーム「Almagest」を Linux で遊ぶ

20181210015655

ゲーム HP。
Almagest -Overture-
以下よりダウンロードする。
「Almagest -Overture-」ターン制SFシミュレーションゲーム - 窓の杜
 
lzh ファイルは Linux ではそのままでは解答できないので、ここでは lhasa を入れてみる。

$ sudo apt install lhasa

これで解凍できる。ver 3.04 の差分フォルダもダウンロードした場合は、手作業で差分ファイルを差し替える(参照)。

動かすためには Wine が必要です。実行はふつうに

$ wine Almagest-1.exe

でよい。特にインストールとかはされない。
 
Linux Mint 19, wine-3.0 で動作確認。
 
※参考
Almagest -Overture- - Wikipedia
Almagestとは (アルマゲストとは) [単語記事] - ニコニコ大百科
Almagest Wiki - Front Page