AOJ(問題集)13

AIZU ONLINE JUDGE: Programming Challenge
 

0120 Patisserie

@memo = {}

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

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

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

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

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

$c = {}

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

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

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

0121 Seven Puzzle

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

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

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

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

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

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

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

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

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

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

0122 Summer of Pyonkichi

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

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

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

0123 Speed Skating Badge Test

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

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

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

0124 League Match Score Sheet

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

 

0125 Day Count

require 'date'

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

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

0126 Puzzle

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

L = 9
T = L / 3

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

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

result = []

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

puts result.join("\n")

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

0127 Pocket Pager Input

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

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

 

0128 Abacus

そろばん。

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

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

print r

 

0129 Hide-and-Seek Supporting System

かくれんぼう。

require 'matrix'

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

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

AOJ(問題集)12

AIZU ONLINE JUDGE: Programming Challenge
 

0110 Alphametic

$<.readlines.map(&:chomp).map {|l| l.split(/\+|=/)}.each do |given|
  catch(:jump) do
    10.times do |i|
      d = given.map {|a| a.gsub("X", i.to_s)}
      next unless d.select {|s| s.length >= 2 and s[0] == "0"}.empty?
      next unless d[0].to_i + d[1].to_i == d[2].to_i
      puts i
      throw(:jump)
    end
    puts "NA"
  end
end

 

0111 Doctor's Memorable Codes

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"=>"?"}
table1 = table1.invert.sort_by {|a| a.first}
table2 = table2.invert

$<.readlines.map(&:chomp).each do |text|
  result = ""
  text.each_char {|c| result += table2[c]}
  
  convert = ->(txt, converted = "") {
    table1.each do |k, v|
      l = k.length
      converted = convert.(txt[l..-1], converted + v) if txt[0, l] == k
    end
    converted
  }
  puts convert.(result)
end

 

0112 A Milk Shop

until (num = $<.gets.to_i).zero?
  order = Array.new(num) {$<.gets.to_i}.sort[0..-2]
  each_wait = 0
  puts order.map {|t| each_wait += t}.sum
end

 

0113 Period

循環少数。

def calc(p, q)
  rems = []
  place = []
  begin
    rems  << p
    place << p * 10 / q
    p = p * 10 % q
    return place.join if p.zero?
  end until (idx = rems.find_index(p))
  result = (st = place.join) + "\n"
  result + " " * idx + "^" * (st.length - idx)
end

$<.readlines.map {|l| l.split.map(&:to_i)}.each do |p, q|
  puts calc(p % q, q)
end

循環少数についてはここで考えておいたのが役立った。
 

0114 Electro-Fly

until (a = $<.gets.split.map(&:to_i)) == [0] * 6
  po = [1, 1, 1]
  co = 0
  result = loop do
    po = a.each_slice(2).zip(po).map {|am, i| am[0] * i % am[1]}
    co += 1
    break co if po == [1, 1, 1]
  end
  puts result
end

これでは例題すらフリーズする。高速化を考えないといけない。
よく考えたらわかった。

def calc(a, m)
  i = 1
  1.step do |co|
    i = a * i % m
    return co if i == 1
  end
end

until (a = $<.gets.split.map(&:to_i)) == [0] * 6
  cx, cy, cz = a.each_slice(2).map {|a, m| calc(a, m)}
  puts cx.lcm(cy).lcm(cz)
end

 

0115 Starship UAZ Advance

宇宙船 UAZ アドバンス号の巻です(参照)。ビームが当たるかを行列演算で求めている。

require 'matrix'

myship, enemy, b1, b2, b3 = $<.readlines.map {|l| Vector[*l.split.map(&:to_r)]}
v = enemy - myship
va = b2 - b1
vb = b3 - b1
begin
  l, s, t = Matrix.columns([-v, va, vb]).lup.solve(myship - b1).to_a
rescue
  puts "HIT"
  exit
end

puts 0 < l && l <= 1 && (s + t).between?(0, 1) && s >= 0 && t >= 0 ? "MISS" : "HIT"

うおお、俺スゲーって感じ。というか、本当は Ruby の Matrix がすごい。
Ruby で解けたのはいまのところ 6人だけ。その中でも自分のは圧倒的にコードのバイト数が少ない。ひゅー。
しかしまあ、数学の問題としては別にむずかしいものではない。手作業では計算が面倒というだけ。そこがプログラミングだな。
 

0116 Rectangular Searching

until (a = $<.gets.split.map(&:to_i)) == [0, 0]
  h, w = a
  field = Array.new(h) do
    $<.gets.chomp.chars.map {|a| (a == ".") ? "1" : "0"}.join.to_i(2)
  end
  
  max = 0
  h.times do |i|
    result = field[i]
    (h - i).times do |j|
      result &= field[i + j]
      max_w = result.to_s(2).chars.chunk_while {|b, a| b == a and b == "1"}
                    .select {|a| a.first == "1"}.map(&:size).max
      max_w ||= 0
      s = max_w * (j + 1)
      max = s if s > max
    end
  end
  puts max
end

時間オーバー。

def count(num)
  return 0 if num.zero?
  pl = Math.log2(num).to_i + 1
  co = 0
  max = 0
  pl.times do
    if (num % 2).zero?
      co = 0
    else
      co += 1
      max = co if co > max
    end
    num /= 2
  end
  max
end

until (a = $<.gets.split.map(&:to_i)) == [0, 0]
  h, w = a
  field = Array.new(h) do
    $<.gets.chomp.chars.map {|a| (a == ".") ? "1" : "0"}.join.to_i(2)
  end
  
  max = 0
  h.times do |i|
    result = field[i]
    (h - i).times do |j|
      result &= field[i + j]
      max_w = count(result)
      s = max_w * (j + 1)
      max = s if s > max
    end
  end
  puts max
end

これも時間オーバー。
メソッド count() をこう替えてみる。

def count(num, max = 0)
  return max if num.empty?
  num = num.drop_while {|e| e == "0"}
  l = num.take_while {|e| e == "1"}.size
  max = l if l > max
  count(num.drop_while {|e| e == "1"}, max)
end

やはり時間オーバー。さらにメモ化をしてみても結果は同じ。根本的にアルゴリズムを変えないとダメだな。
他の人の答えを見る。

loop do
  h, w = $<.gets.split.map(&:to_i)
  break if h.zero? and w.zero?
  f = h.times.map { $<.gets.chomp }
  hseq = Array.new(h) {Array.new(w)}
  
  h.times.map do |y|
    hseq[y][0] = (f[y][0] == ".") ? 1 : 0
    (1...w).each {|x| hseq[y][x] = (f[y][x] == ".") ? hseq[y][x - 1] + 1 : 0}
  end
  ans = 0
   
  (w - 1).downto(0) do|x|
    h.times do |fy|
      tmp = w
      lim = h - fy
      (h - fy).times do |dy|
        tmp = [tmp, hseq[fy + dy][x]].min
        ans = [ans, tmp * (dy + 1)].max
        break if tmp * lim < ans
      end
    end
  end
  puts ans
end

なるほどー、時々あるアルゴリズム動的計画法?)だが、いつもこれが思い浮かばないのだよなあ。勉強になりました。
 

0117 A reward for a Carpenter

towns = Hash.new([])
n = $<.gets.to_i
$<.gets.to_i.times do
  a, b, c, d = $<.gets.split(",").map(&:to_i)
  towns[a] += [[b, c]]
  towns[b] += [[a, d]]
end
s, g, v, p = $<.gets.split(",").map(&:to_i)

travel = ->(start, goal) {
  minimum = Float::INFINITY
  walk = ->(town, visited, cost = 0) {
    if town == goal
      minimum = [minimum, cost].min
    else
      towns[town].each do |nxt, c|
        walk.(nxt, visited + [nxt], cost + c) unless visited.include?(nxt)
      end
    end
  }
  walk.(start, [start])
  minimum
}

v -= travel.(s, g)
v -= travel.(g, s)
puts v - p

簡単なバックトラック法。
 

0118 Property Distribution

until (a = $<.gets.split.map(&:to_i)) == [0, 0]
  h, w = a
  field = Array.new(h) {$<.gets.chomp.chars}
  
  erase = ->(x, y, fruit) {
    stack = [[x, y]]
    while (a = stack.shift)
      x, y = a
      next if x < 0 or x >= w or y < 0 or y >= h
      next unless field[y][x] == fruit
      field[y][x] = "."
      [[1, 0], [0, -1], [-1, 0], [0, 1]].each do |dx, dy|
        stack << [x + dx, y + dy]
      end
    end
  }
  
  num = 0
  i = 0
  loop do
    x, y = i % w, i / w
    i += 1
    unless field[y][x] == "."
      erase.(x, y, field[y][x])
      num += 1
    end
    break if i >= w * h
  end
  puts num
end

最初 erase.()深さ優先探索でやっていて、どうしても Runtime Error が取れなかった。これは幅優先探索じゃないとダメなのかな。よくわからない。
 

0119 Taro's Obsession

table = Hash.new([])

m = $<.gets.to_i
$<.gets.to_i.times do
  x, y = $<.gets.split.map(&:to_i)
  table[x] += [y]
end

check = ->(order) {
  order.map.with_index do |person, i|
    table[person].map {|b| i < order.index(b)}.all?
  end.all?
}

solve = ->(n, order) {
  if order.size == m
    if check.(order)
      puts order
      exit
    end
  else
    a = table[n]
    ([*1..m] - order - (a ? a : [])).each do |prev|
      solve.(prev, [prev] + order)
    end
  end
}
solve.(2, [2])

10問中 5問で時間オーバー。

table = Hash.new([])

m = io.gets.to_i
io.gets.to_i.times do
  x, y = io.gets.split.map(&:to_i)
  table[y] += [x]
end

check = ->(order) {
  table.map do |k, v|
    v.map {|prev| order.index(prev) < order.index(k)}.all?
  end.all?
}

solve = ->(person, order) {
  if order.size == m
    if check.(order)
      puts order
      exit
    end
  else
    table[person].each do |prev|
      solve.(prev, [prev] + order) unless order.include?(prev)
    end
    ([*1..m] - table[person] - order).each do |prev|
      solve.(prev, [prev] + order) unless order.include?(prev)
    end
  end
}
solve.(2, [2])

10問中 4問で時間オーバー。どうもバックトラック法では無理だな。
他の人の回答を見た。

m = $<.gets.to_i
n = $<.gets.to_i
e = Array.new(m + 1) {[]}
n.times do
  x, y = $<.gets.split.map(&:to_i)
  e[x] << y    #後にあるのを入れている
end
r = [2]

while r.size < m
  1.upto(m) do |i|
    next if r.include?(i)
    catch(:a) do
      e[i].each do |j|
        throw(:a) unless r.include?(j)
      end
      r << i
    end
  end
end
puts r.reverse

なるほどー、後にあるのが確実になってから入れるのかあ。すごいなあ。

SSD の寿命を Linux で判断する

SSD(Intel X25-M)で寿命を確認するには at nkjmkzk.net

$ sudo smartctl -i /dev/sdc -d sat -a
smartctl 6.6 2016-05-31 r4324 [x86_64-linux-4.18.0-13-generic] (local build)
Copyright (C) 2002-16, Bruce Allen, Christian Franke, www.smartmontools.org

=== START OF INFORMATION SECTION ===
Device Model:     SATA SSD
Serial Number:    D61E076A1D2203758638
LU WWN Device Id: 5 000000 000000000
Firmware Version: SBFM10.6
User Capacity:    240,057,409,536 bytes [240 GB]
Sector Size:      512 bytes logical/physical
Rotation Rate:    Solid State Device
Form Factor:      < 1.8 inches
Device is:        Not in smartctl database [for details use: -P showall]
ATA Version is:   Unknown(0x0ff8) (minor revision not indicated)
SATA Version is:  SATA 3.2, 6.0 Gb/s (current: 6.0 Gb/s)
Local Time is:    Tue Jan 29 00:20:22 2019 JST
SMART support is: Available - device has SMART capability.
SMART support is: Enabled

=== START OF READ SMART DATA SECTION ===
SMART overall-health self-assessment test result: PASSED

General SMART Values:
Offline data collection status:  (0x00)	Offline data collection activity
					was never started.
					Auto Offline Data Collection: Disabled.
Self-test execution status:      (   0)	The previous self-test routine completed
					without error or no self-test has ever 
					been run.
Total time to complete Offline 
data collection: 		(65535) seconds.
Offline data collection
capabilities: 			 (0x79) SMART execute Offline immediate.
					No Auto Offline data collection support.
					Suspend Offline collection upon new
					command.
					Offline surface scan supported.
					Self-test supported.
					Conveyance Self-test supported.
					Selective Self-test supported.
SMART capabilities:            (0x0003)	Saves SMART data before entering
					power-saving mode.
					Supports SMART auto save timer.
Error logging capability:        (0x01)	Error logging supported.
					General Purpose Logging supported.
Short self-test routine 
recommended polling time: 	 (   4) minutes.
Extended self-test routine
recommended polling time: 	 (  32) minutes.
Conveyance self-test routine
recommended polling time: 	 (   8) minutes.

SMART Attributes Data Structure revision number: 16
Vendor Specific SMART Attributes with Thresholds:
ID# ATTRIBUTE_NAME          FLAG     VALUE WORST THRESH TYPE      UPDATED  WHEN_FAILED RAW_VALUE
  1 Raw_Read_Error_Rate     0x000b   100   100   050    Pre-fail  Always       -       0
  9 Power_On_Hours          0x0012   100   100   000    Old_age   Always       -       6907
 12 Power_Cycle_Count       0x0012   100   100   000    Old_age   Always       -       4379
168 Unknown_Attribute       0x0012   100   100   000    Old_age   Always       -       0
170 Unknown_Attribute       0x0003   093   093   010    Pre-fail  Always       -       180
173 Unknown_Attribute       0x0012   100   100   000    Old_age   Always       -       2490448
192 Power-Off_Retract_Count 0x0012   100   100   000    Old_age   Always       -       1372
194 Temperature_Celsius     0x0023   067   067   000    Pre-fail  Always       -       33 (Min/Max 33/33)
218 Unknown_Attribute       0x000b   100   100   050    Pre-fail  Always       -       0
231 Temperature_Celsius     0x0013   100   100   000    Pre-fail  Always       -       96
241 Total_LBAs_Written      0x0012   100   100   000    Old_age   Always       -       7107

SMART Error Log Version: 1
No Errors Logged

SMART Self-test log structure revision number 1
No self-tests have been logged.  [To run self-tests, use: smartctl -t]

SMART Selective self-test log data structure revision number 0
Note: revision number not 1 implies that no selective self-test has ever been run
 SPAN  MIN_LBA  MAX_LBA  CURRENT_TEST_STATUS
    1        0        0  Not_testing
    2        0        0  Not_testing
    3        0        0  Not_testing
    4        0        0  Not_testing
    5        0        0  Not_testing
Selective self-test flags (0x0):
  After scanning selected spans, do NOT read-scan remainder of disk.
If Selective self-test is pending on power-up, resume after 0 minute delay.



上の情報をどう読み取ればよいかわからなかったので、Windows 7CrystalDiskInfo をインストールして調べてみた。
「Crystal Disk Info」で、SSDの健康状態を把握しよう! | SSD徹底解説!
ただ、Wndows では ext4 が読み取れないので、下を参考に Ext2Fsd をインストールする。
ext4のパーティションをWindowsで読み書きする方法 | Linux Fan
以上の結果、下のように診断されました。
20190129010121
結果としては、Linux で smartctl を使ったのと同じ情報だが、なるほどこれはわかりやすい。
まだこの SSD は大丈夫みたいです。(2019/1/29)

AOJ(問題集)11

AIZU ONLINE JUDGE: Programming Challenge
 

0100 Sale Result

問題が曖昧。同じ社員が二度出てくるかどうかはっきりしない。

Border = 1_000_000

until (n = $<.gets.to_i).zero?
  data = Hash.new(0)
  entry = []
  n.times do
    e, p, q = $<.gets.split.map(&:to_i)
    data[e] += p * q
    entry << e if data[e] >= Border
  end
  puts entry.empty? ? "NA" : entry.uniq
end

 

0101 Aizu PR

$<.gets.to_i.times do
  text = $<.gets.chomp
  result = ""
  po = 0
  while result.size < text.size
    if text[po, 7] == "Hoshino"
      result += "Hoshina"
      po += 7
    else
      result += text[po]
      po += 1
    end
  end
  puts result
end

 

0102 Matrix-like Computation

until (n = $<.gets.to_i).zero?
  table = n.times.map do
    l = $<.gets.split.map(&:to_i)
    l + [l.sum]
  end
  last = (n + 1).times.map do |i|
    n.times.map {|j| table[j][i]}.sum
  end
  puts (table + [last]).map {|l| l.map {|i| sprintf("%5d", i)}.join }
end

簡単な問題でも [提出] のボタンを押すときはドキドキするな。
 

0103 Baseball Simulation

$<.gets.to_i.times do
  bases = [0, 0, 0]
  out_count = 0
  points = 0
  while out_count < 3
    case $<.gets.chomp
    when "OUT"
      out_count += 1
      puts points if out_count >= 3
    when "HIT"
      bases << 1
      points += bases.shift
    when "HOMERUN"
      points += bases.sum + 1
      bases = [0, 0, 0]
    else
      raise "error"
    end
  end
end

 

0104 Magical Tiles

ひさしぶりにやる。

until (a = $<.gets.split.map(&:to_i)) == [0, 0]
  h, w = a
  tiles = h.times.map {$<.gets.chomp}
  positions = [0]
  x, y = 0, 0
  
  result = loop do
    case tiles[y][x]
    when ">" then x += 1
    when "<" then x -= 1
    when "^" then y -= 1
    when "v" then y += 1
    when "." then break "#{x} #{y}"
    else raise "error"
    end
    po = y * w + x
    break "LOOP" if positions.include?(po)
    positions << po
  end
  puts result
end

簡単だけれどドキドキするな。
 

0105 Book Index

index = Hash.new([])

$<.readlines.map do |l|
  a = l.chomp.split
  [a.first, a.last.to_i]
end.each {|word, page| index[word] += [page]}

index.keys.sort.each {|k| puts k, index[k].sort.join(" ")}

 

0106 Discounts of Buckwheat

table = [[200, 380, 5, 0.8], [300, 550, 4, 0.85], [500, 850, 3, 0.88]]
A, B, C = table.map(&:first)

calc = ->(shop, num) {
  t = table[shop]
  discount = (num / t[2]) * t[2]
  discount * t[1] * t[3] + (num - discount) * t[1]
}

until (soba = $<.gets.to_i).zero?
  min = Float::INFINITY
  (0..soba / C).each do |c|
    pay = calc.(2, c)
    soba1 = soba - c * C
    
    (0..soba1 / B).each do |b|
      pay1 = pay + calc.(1, b)
      soba2 = soba1 - b * B
      
      next if (soba2 % A).nonzero?
      pay2 = pay1 + calc.(0, soba2 / A)
      min = pay2 if pay2 < min
    end
    
  end
  puts min.to_i
end

再帰で解いた方がよかったかな。ごちゃごちゃしたコードだ。
 

0107 Carry a Cheese

until (a = $<.gets.split.map(&:to_i)) == [0, 0, 0]
  $<.gets.to_i.times.map {$<.gets.to_i}.each do |r|
    result = a.combination(2).map do |w, h|
      Math.sqrt((w / 2.0) ** 2 + (h / 2.0) ** 2) < r
    end.any?
    puts result ? "OK" : "NA"
  end
end

 

0108 Operation of Frequency of Appearance

def operation(ary, prev = [], i = 0)
  return i - 1, ary if ary == prev
  count = Hash.new(0)
  ary.each {|x| count[x] += 1}
  operation(ary.map {|x| count[x]}, ary, i + 1)
end

until $<.gets.to_i.zero?
  i, ary = operation($<.gets.split.map(&:to_i))
  puts i, ary.join(" ")
end

 

0109 Smart Calculator

$<.gets.to_i.times do
  splited = $<.gets.chomp.scan(/([0-9\.]+|\+|\-|\*|\/|\(|\)|=)/)
  output = []
  stack = []
  a = nil
  until (token = splited.shift) == ["="]
    token = token.first
    case token
    when "(" then stack << token
    when ")" then
      output << a until (a = stack.pop) == "("
    when "*", "/"
      loop do
        a = stack.last
        break unless %w(* /).include?(a)
        output << stack.pop
      end
      stack << token
    when "+", "-"
      loop do
        a = stack.last
        break unless %w(+ - * /).include?(a)
        output << stack.pop
      end
      stack << token
    else
      output << token
    end
  end
  output << a while (a = stack.pop)
  
  stack = []
  while (x = output.shift)
    if %w(+ - * /).include?(x)
      a, b = stack.pop, stack.pop
      stack << eval("#{b} #{x} #{a}").to_i
    else
      stack << x
    end
  end
  puts stack.first
end

何がいけないのかわからない。
どうしてもわからないので他人の回答を見た。喰らった…。

$<.gets.to_i.times do
  splited = $<.gets.chomp.scan(/([0-9\.]+|\+|\-|\*|\/|\(|\)|=)/)
  a = nil
  
  # パーサー(逆ポーランド記法に変換)
  output = []
  stack = []
  until (token = splited.shift) == ["="]
    token = token.first
    case token
    when "(" then stack << token
    when ")" then
      output << a until (a = stack.pop) == "("
    when "*", "/"
      loop do
        a = stack.last
        break unless %w(* /).include?(a)
        output << stack.pop
      end
      stack << token
    when "+", "-"
      loop do
        a = stack.last
        break unless %w(+ - * /).include?(a)
        output << stack.pop
      end
      stack << token
    else
      output << token.to_r
    end
  end
  output << a while (a = stack.pop)
  
  # 逆ポーランド記法を処理
  stack = []
  while (x = output.shift)
    if %w(+ - * /).include?(x)
      a, b = stack.pop, stack.pop
      if x == "/" and ((a < 0) ^ (b < 0))
        stack << -(b.abs / a.abs)
      else
        stack << eval("#{b.to_i} #{x} #{a.to_i}").to_i
      end
    else
      stack << x
    end
  end
  puts stack.first.to_i
end

これを見てほしい。

$ pry
[1] pry(main)> -3/2
=> -2

マジか! -1 ではないのか!

div はメソッド / を呼びだし、floorを取ることで計算されます。

class Numeric (Ruby 2.5.0)

やられた。そういう Ruby の仕様なのね。勉強になりました。せっかくパーサー(操車場アルゴリズム)まで書いて頑張ったのに…。なお、皆さん演算子の再定義でやっておられる。自分もそれは考えたが、それではつまらん。

AOJ(問題集)10

AIZU ONLINE JUDGE: Programming Challenge
 

0091 Blur

L = 10
table = [[[0, 0], [0, 1], [-1, 1], [1, 1], [0, 2], [-1, 2], [-2, 2], [1, 2],
  [2, 2], [0, 3], [-1, 3], [1, 3], [0, 4]],
  [[0, 0], [1, 0], [2, 0], [0, 1], [1, 1], [2, 1], [0, 2], [1, 2], [2, 2]],
  [[0, 0], [0, 1], [-1, 1], [1, 1], [0, 2]]]

n = $<.gets.to_i
cloth = $<.readlines.map {|l| l.split.map(&:to_i)}

copy = ->(ary) { ary.map {|l| l.dup} }
form = ->(x, y, i) {
  case (j = 3 - i)
  when 1 then "#{x} #{y + 1} #{j}"
  when 2 then "#{x + 1} #{y + 1} #{j}"
  when 3 then "#{x} #{y + 2} #{j}"
  else nil
  end
}

try = ->(place, field, co, order = []) {
  # にじみがあるまでスキップ
  x = y = nil
  loop do
    return false if place >= L * L
    x, y = place % L, place / L
    break if field[y][x].nonzero?
    place += 1
  end
  
  result = false
  # 大、中、小の滴を順に試す
  table.each_with_index do |drip, i|
    tmp = copy.(field)
    
    catch(:jump) do
      # 滴を試す(適合しなければ大域脱出で次の滴へ)
      drip.each do |po|
        x1, y1 = x + po[0], y + po[1]
        throw(:jump) if x1 < 0 or x1 >= L or y1 >= L or tmp[y1][x1].zero?
        tmp[y1][x1] -= 1
      end
      
      # 滴が適合した場合の処理
      co -= 1
      prc = form.(x, y, i)
      if co.zero?
        if tmp.flatten.map(&:zero?).all?
          return order + [prc]    #解が発見された場合(一気にリターン)
        else
          co += 1
          throw(:jump)
        end
      end
      
      result = try.(place, tmp, co, order + [prc])
      return result if result
      co += 1
    end
    
  end
  result
}
puts try.(0, cloth, n)

よくこんなのできたな。いまのところ Ruby で解けたのは 5人だけで、タイムは自分が最速。うれしい。
 

0092 Square Searching

until (n = $<.gets.to_i).zero?
  field = Array.new(n) {$<.gets.chomp}
  max = 0
  
  check = ->(x, y, num) {
    num.times do |i|
      num.times do |j|
        return false if x + j >= n or y + i >= n
        return false if field[y + i][x + j] == "*"
      end
    end
    true
  }
  
  (0...n * n).each do |i|
    x, y = i % n, i / n
    (max + 1..n - x).each do |width|
      max = width if check.(x, y, width)
    end
  end
  puts max
end

これだと時間オーバー。ちょっと素朴すぎるか。
高速化に挑戦。チェックをビット演算に切り替える。

until (n = $<.gets.to_i).zero?
  field = Array.new(n) {$<.gets.chomp}
  field.map! {|st| eval("0b" + st.gsub(/\./, "0").gsub(/\*/, "1"))}
  max = 0
  
  n.times do |y|
    l = field[y]
    break unless n - y > max
    (n - y).times do |i|
      l |= field[y + i]
      if l.to_s(2).rjust(n, "0").include?("0" * (i + 1))
        max = i + 1 if i + 1 > max
      end
    end
  end
  puts max
end

いちおう通ったけれども、3.91秒もかかってしまった。判定時にわざわざ文字列に直しているのがよくないのだけれど。
判定時に文字列を使わないバージョンも作ってみたのだが、余計に遅くなってしまった。正解者の結果を見ると 3.91秒というのは真ん中くらいで、そんなに悪い数字ではなかったようだ。Ruby だとしようがないのね。
 

0093 Leap Year

stack = []
until (years = $<.gets.split.map(&:to_i)) == [0, 0]
  is_uruu = ->(year) {
    (year % 4).zero? and ((year % 100).nonzero? or (year % 400).zero?)
  }
  result = (years.first..years.last).map {|i| is_uruu.(i) ? i : nil}.compact
  result << "NA" if result.empty?
  stack << result.join("\n") 
end
print stack.join("\n\n") + "\n"

 

0094 Calculation of Area

a, b = $<.gets.split.map(&:to_i)
printf "%.5f\n", a * b / 3.305785

 

0095 Surf Smelt Fishing Contest

$<.gets
data = $<.readlines.map {|l| l.split.map(&:to_i)}.sort_by(&:last)
max = data.last.last
num = data.select {|a| a.last == max}.sort_by(&:first).first.first
puts "#{num} #{max}"

sort_bysort と書くタイポがあって、なかなか気づけなかった。
 

0096 Sum of 4 Integers II

L = 1000
@memo = {}

def doit(s, n = 1)
  return (s <= L) ? 1 : 0 if n == 4
  key = [s, n]
  return @memo[key] if @memo.has_key?(key)
  co = 0
  a = (s <= L) ? s : L
  (0..a).each do |i|
    co += doit(s - i, n + 1)
  end
  @memo[key] = co
end

$<.readlines.map(&:to_i).each do |s|
  puts doit(s)
end

これだと時間オーバー。メモ化はしているのだけれど、もっと工夫しないといけない。

L = 1000
memo = {}

f1 = ->(n) {(n ** 3 + 6 * n ** 2 + 11 * n + 6) / 6}
f2 = ->(n) {(n ** 2 + 3 * n + 2) / 2}
f3 = ->(n) {n + 1}

f = ->(s, n) {
  case n
  when 1 then f1.(s)
  when 2 then f2.(s)
  when 3 then f3.(s)
  when 4 then 1
  else nil
  end
}

doit = ->(s, n = 1) {
  co = 0
  return f.(s, n) if s <= L
  return 0 if n == 4
  
  key = [s, n]
  return memo[key] if memo.has_key?(key)
  
  (0..L).each do |i|
    co += doit.(s - i, n + 1)
  end
  memo[key] = co
}

$<.readlines.map(&:to_i).each do |s|
  puts doit.(s)
end

これも時間オーバーだが、正しい答えを出すようだ。これがひな型になる。

f1 = ->(n) {(n ** 3 + 6 * n ** 2 + 11 * n + 6) / 6}
f2 = ->(n) {
  n1 = n - 1000
  (335337002 + 1004001 * n1 + 998 * n1 ** 2 - n1 ** 3) / 2
}
f3 = ->(n) {
  n1 = n - 2001
  (1337336000 - 4002 * n1 - 1999 * n1 ** 2 + n1 ** 3) / 2
}
f4 = ->(n) {
  n1 = n - 3002
  (999999000 - 2999999 * n1 + 3000 * n1 ** 2 - n1 ** 3) / 6
}

$<.readlines.map(&:to_i).each do |s|
  result = case s
           when    0..1000 then f1.(s)
           when 1001..2001 then f2.(s)
           when 2002..3002 then f3.(s)
           when 3003..4000 then f4.(s)
           end
  puts result
end

ほとんどインチキ。瞬殺である。WolframAlpha に助けを借りたのはナイショ。
他の人の回答。

MAX_SUM = 4000
MAX_I = 1000
K = 4
 
$sn_cache = Array.new(K + 1) {[]}
 
def check_sum(k, n)
  unless $sn_cache[k][n]
    count = 0
    max_i = [MAX_I, n].min
 
    (0..max_i).each do |i|
      count += check_sum(k - 1, n - i)
    end
 
    $sn_cache[k][n] = count
  end
  
  $sn_cache[k][n]
end
 
$sn_cache[1] = Array.new(MAX_I + 1, 1) + Array.new(MAX_SUM - MAX_I, 0)
 
while (line = gets)
  n = line.chomp.to_i
  puts check_sum(K, n)
end

これで 0.81秒なのだが、自分の最初の答えとよく似ている。しかし、自分のだと 6.51秒で時間オーバー。どこがちがうのだろう。
わかった、メモ化の際の配列の作り方がちがっているのだ。ハッシュを多重配列に直す。

L = 1000
@memo = Array.new(3) {[]}

def doit(s, n = 1)
  return (s <= L) ? 1 : 0 if n == 4
  return @memo[n - 1][s] if @memo[n - 1][s]
  co = 0
  a = (s <= L) ? s : L
  (0..a).each do |i|
    co += doit(s - i, n + 1)
  end
  @memo[n - 1][s] = co
end

$<.readlines.map(&:to_i).each do |s|
  puts doit(s)
end

これだけのことで 0.83秒で解けた。うーん、めっちゃ勉強になるなあ。
この最後のコードがいちばん好きだな。
なお、メモ化をハッシュにして、キーを key = "#{s},#{n}" という感じにしてやってもまあまあいけて、2.25秒で出来た。しかし、数字でいける場合はやはり配列が速いのは当り前か。
 

0097 Sum of Integers II

L = 100
@memo = Array.new(9) {Array.new(101) {[]}}

def solve(num, start, sum)
  return 0 if sum < 0 or start > L
  return (start <= sum and sum <= L) ? 1 : 0 if num == 1
  a = @memo[num - 1][start][sum]
  return a if a
  
  co = 0
  lim = [L, (2 * sum - num ** 2 + num) / (2 * num)].min
  (start..lim).each do |i|
    co += solve(num - 1, i + 1, sum - i)
  end
  @memo[num - 1][start][sum] = co
end
  
until (a = $<.gets.split.map(&:to_i)) == [0, 0]
  puts solve(a.first, 0, a.last)
end

1.11秒かかった。lim を求めるのは少し凝ってみた。lim = [L, sum].min とやるより少し効率がよい。
 

0098 Maximum Sum Sequence II

matrix = Array.new(n = $<.gets.to_i) {$<.gets.split.map(&:to_i)}
max = -Float::INFINITY
memo = {}

try = ->(x, y, w, h) {
  return 0 if x >= n or y >= n or w <= 0 or h <= 0
  key = "#{x},#{y},#{w},#{h}"
  return memo[key] if memo[key]
  
  if h == 1 and w == 1
    num = matrix[y][x]
  else
    try.(x, y + 1, w, h - 1)
    try.(x, y    , w, h - 1)
    try.(x + 1, y, w - 1, h)
    try.(x    , y, w - 1, h)
    num = try.(x, y, 1, 1) + try.(x + 1, y, w - 1, 1) +
          try.(x, y + 1, 1, h - 1) + try.(x + 1, y + 1, w - 1, h - 1)
  end
  max = num if num > max
  memo[key] = num
}

try.(0, 0, n, n)
puts max

メモ化しても時間オーバー。
他の人の回答(参照)を見る。コードは自分の好みに改変してあります。

n = $<.gets.to_i
matrix = (1..n).map { $<.gets.split.map(&:to_i) }
# 各行の数字を左から加算していった配列
accum = matrix.map {|row| row.inject([0]) {|s, x| s + [s[-1] + x]} }
 
max = 0 
[*1..n].repeated_combination(2) do |i, j|
  sum = 0 
  (0..n - 1).each do |k|
    sum += accum[k][j] - accum[k][i - 1]
    max = sum if sum > max
    sum = 0 if sum < 0
  end
end
 
matrix.flatten!
puts matrix.any? {|x| x >= 0} ? max : matrix.max

瞬殺。うーん、すごい、これは思いつかなかった。でもあらかじめ数字を加算しておいた配列を作るのいうのは、確かに時々見る手法。
 

0099 Surf Smelt Fishing Contest II

Node = Struct.new(:key, :value, :left, :right)

class Tree
  def initialize
    @root = nil
  end
  
  def insert(key, value)
    unless @root
      @root = Node.new(key, value)
      return
    end
    node = @root
    while node
      if key < node.key
        if node.left
          node = node.left
        else
          node.left = Node.new(key, value)
          break
        end
      elsif key > node.key
        if node.right
          node = node.right
        else
          node.right = Node.new(key, value)
          break
        end
      else
        if block_given?
          node.value = yield(key, node.value, value)
        else
          node.value = value
        end
        break
      end
    end
  end
  
  def []=(key, value)
    insert(key, value)
  end
  
  def search(key)
    node = @root
    while node
      if key < node.key
        node = node.left
      elsif key > node.key
        node = node.right
      else
        return node
      end
    end
    nil
  end
  
  def [](key)
    search(key)&.value
  end
  
  def delete(key)
    delete_min = ->(node) {
      return node.right unless node.left
      node.left = delete_min.(node.left)
      node
    }
    search_min = ->(node) {
      node = node.left while node.left
      node
    }
    del = ->(node) {
      if node
        if key == node.key
          if node.left.nil?
            return node.right
          elsif node.right.nil?
            return node.left
          else
            min_node = search_min.(node.right)
            node.key = min_node.key
            node.value = min_node.value
            node.right = delete_min.(node.right)
          end
        elsif key < node.key
          node.left  = del.(node.left)
        else
          node.right = del.(node.right)
        end
      end
      node
    }
    
    @root = del.(@root)
  end
  
  def maximum
    search_max = ->(node) {
      node = node.right while node.right
      node
    }
    raise "error" unless @root
    node = search_max.(@root)
    raise "error" unless node
    node.key
  end
end

n, q = $<.gets.split.map(&:to_i)
entry = []
fish_num = Hash.new(0)
t = Tree.new

delete = ->(fish, member) {
  t[fish] -= [member]
  t.delete(fish) if t[fish].empty?
}

q.times do
  member, fs = $<.gets.split.map(&:to_i)
  tmp = fish_num[member]
  fish_num[member] += fs
  t.insert(fish_num[member], [member]) {|k, v1, v2| v1 + v2}
  if entry.include?(member)
    delete.(tmp, member)
  else
    entry << member
  end
  max_fish = t.maximum
  puts "#{t[max_fish].sort.first} #{max_fish}"
end

惜しい、22課題中21課題までいって時間オーバー(9秒99)。二分探索木を実装して頑張った。しかしこれではダメのようだから、平衡二分探索木を実装しないといけないのか。
いや、シンプルに考え直してみる。

fish = Hash.new(0)
max = 0
max_fishers = []
selected_fisher = nil

n, q = $<.gets.split.map(&:to_i)
q.times do
  a, v = $<.gets.split.map(&:to_i)
  fish[a] += v
  if v > 0
    if fish[a] > max
      max = fish[a]
      puts "#{a} #{max}"
      max_fishers = [a]
      selected_fisher = a
    elsif fish[a] == max
      max_fishers << a
      puts "#{selected_fisher = max_fishers.min} #{max}"
    else
      puts "#{selected_fisher} #{max}"
    end
  else
    if fish[a] - v == max
      if max_fishers.size == 1
        max = fish.values.max
        max_fishers = fish.keys.select {|k| fish[k] == max}
        puts "#{selected_fisher = max_fishers.min} #{max}"
      else
        max_fishers.delete(a)
        puts "#{selected_fisher = max_fishers.min} #{max}"
      end
    else
      puts "#{selected_fisher} #{max}"
    end
  end
end

これで 0.23秒で通った。なんと Ruby での通過者中最速だった。C と C++ 以外には負けないぜ!

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!