動画の切り出し

ffmpeg を使う。

開始5分の時点から1分間切り出す。ついでに mkv から mp4 へ変換。時間指定は「hh:mm:ss」という形式でも OK。

$ ffmpeg -ss 300 -i a.mkv -t 60 a1.mp4

「-ss」が前に来るようにする。

動画の連結はこちら


※参考
FFmpegで素早く正確に動画をカットする自分的ベストプラクティス - Qiita
それFFmpegで出来るよ! - Qiita
Ffmpegで複数動画ファイルを無劣化で結合したり、無劣化で切り出したりする | Creazy!

CPSCO2019 Session4

CPSCO2019 Session4 - AtCoder

A - Swimming

l, x = gets.split.map(&:to_i)
n = x / l
puts n.even? ? x % l : (n + 1) * l - x

 

B - Meeting

n, d = gets.split.map(&:to_i)
table = d.times.map do
  gets.chomp.chars.map.with_index {|st, i| i if st == "o"}.compact
end
puts table.combination(2).map {|d1, d2| (d1 + d2).uniq.size}.max

 

C - Make a Team

def c(a)
  return 1 if a == 1
  a * (a - 1) / 2
end

n, d = gets.split.map(&:to_i)
r = gets.split.map(&:to_i).sort.push(Float::INFINITY)
count = 0
(n - 2).times do |i|
  idx = r[i + 2..-1].bsearch_index {|r0| r0 - r[i] > d}
  next if !idx or idx.zero?
  count += c(idx + 1)
end
puts count

rindex を使ったら TLE だったので、bsearch_index に切り替えた。

Ruby 2.6 で Gem 'chipmunk' を使う(Ubuntu)

Ubuntu 19.04 の Ruby 2.6 で Gem 'chipmunk' がインストールできない。

解決策:GitHub で修正されているものを使う。

$ git clone https://github.com/chipmunk-rb/chipmunk.git
$ cd chipmunk
$ rake clean compile
$ gem build chipmunk.gemspec
  Successfully built RubyGem
  Name: chipmunk
  Version: 6.1.3.4
  File: chipmunk-6.1.3.4.gem
$ cd ..

 
Gemfile に以下を追加(参照)。

gem 'chipmunk', :path => "chipmunk"

 
インストール。

$ bundle install
$ bundle exec pry
[1] pry(main)> require 'chipmunk'
=> true

これで OK。

AOJ(問題集)20

AIZU ONLINE JUDGE: Programming Challenge
 

0190 Eleven Puzzle

素直に幅優先探索を実行して死んだので、ここを参考に解いた。「両側探索」というらしい。

start = "fff0fff" "ff123ff" "f45678f" "ff9abff" "fff0fff"
result1 = {}
result1[start] = 0
stack = [start]

# 一方からの探索
while (nxt = stack.shift)
  next if result1[nxt] >= 10
  doit1 = ->(idx) {
    [1, -1, 7, -7].each do |di|
      next_index = idx + di
      next if next_index < 0 or next_index >= 35
      next if (c = nxt[next_index]) == "f" or c == "0"
      next_field = nxt.dup
      next_field[idx] = c
      next_field[next_index] = "0"
      next if result1[next_field]
      result1[next_field] = result1[nxt] + 1
      stack << next_field
    end
  }
  doit1.(nxt.index("0"))
  doit1.(nxt.rindex("0"))
end

# 反対側からの探索
pat = Array.new(5)
until (pat[0] = gets.to_i) == -1
  pat[0] = pat[0].to_s(16).center(7, "f")
  4.times {|i| pat[i + 1] = gets.split.map {|a| a.to_i.to_s(16)}.join.center(7, "f") }
  
  if (ans = result1[start = pat.join])
    puts ans
    next
  end
  
  result2 = {}
  result2[start] = 0
  stack = [start]
  str = "NA"
  f = true
  
  while (nxt = stack.shift) and f
    next if result2[nxt] >= 10
    doit2 = ->(idx) {
      [1, -1, 7, -7].each do |di|
        next_index = idx + di
        next if next_index < 0 or next_index >= 35
        next if (c = nxt[next_index]) == "f" or c == "0"
        next_field = nxt.dup
        next_field[idx] = c
        next_field[next_index] = "0"
        next if result2[next_field]
        if result1[next_field]
          str = (result1[next_field] + result2[nxt] + 1).to_s
          return false
        end
        result2[next_field] = result2[nxt] + 1
        stack << next_field
      end
      true
    }
    f = doit2.(nxt.index("0"))
    f = doit2.(nxt.rindex("0")) if f
  end
  puts str
end

 

0191 Baby Tree

until (given = gets.split.map(&:to_i)) == [0, 0]
  n, m = given
  g = n.times.map {gets.split.map(&:to_f)}
  memo = Array.new(101) {Array.new(101)}
  
  compost = ->(num, left) {
    return memo[num][left] if memo[num][left]
    memo[num][left] = if left.zero?
      1.0
    else
      n.times.map {|j| g[num][j] * compost.(j, left - 1)}.max
    end
  }
  printf "%.02f\n", n.times.map {|i| compost.(i, m - 1)}.max.round(2)
end

アホなミスをしていた。メモ化で値が存在するときに return を忘れているという…(笑)
 

0192 Multistory Parking Lot

class Car
  num = 1
  
  define_method(:initialize) do |waiting_time|
    @num = num
    num += 1
    @time = waiting_time
  end
  attr_reader   :num
  attr_accessor :time
  
  define_singleton_method(:clear) {num = 1}
end

class ParkingLot
  Space = Struct.new(:upper, :lower)
  
  def initialize(num)
    @spaces = num.times.map {|i| Space.new}
  end
  
  def add_car(waiting_time)
    idx = @spaces.index {|sp| sp.lower.nil?}
    if idx
      @spaces[idx].lower = Car.new(waiting_time)   #下のスペースが空いている
    else
      return false if @spaces.all?(&:upper)        #満車
      
      #下は空いていないが満車でない場合
      idxs = @spaces.map.with_index {|sp, i| i unless sp.upper}.compact
      idx = idxs.map do |i|
        diff = @spaces[i].lower.time - waiting_time
        diff >= 0 ? [diff, i] : nil
      end.compact.sort.first&.last
      unless idx
        idx = idxs.map {|i| [waiting_time - @spaces[i].lower.time, i]}.sort.first.last
      end
      
      @spaces[idx].upper = @spaces[idx].lower
      @spaces[idx].lower = Car.new(waiting_time)
    end
    true
  end
  
  def next
    @spaces.each do |sp|
      if sp.lower
        sp.lower.time -= 1
        sp.upper.time -= 1 if sp.upper
      end
    end
    
    out = []
    2.times do
      @spaces.each do |sp|
        if sp.lower and sp.lower.time <= 0
          out << sp.lower.num
          sp.lower = sp.upper
          sp.upper = nil
        end
      end
    end
    
    out
  end
  
  #車庫が空か
  def empty?
    @spaces.all? {|sp| sp.lower.nil?}
  end
end


until (given = gets.split.map(&:to_i)) == [0, 0]
  m, n = given
  parking_time = n.times.map {gets.to_i}
  pl = ParkingLot.new(m)
  result = []
  wait = []
  Car.clear
  t = 0
  
  loop do
    result += pl.next
    
    wait << parking_time.shift if (t % 10).zero?
    t += 1
    while (wait_time = wait.shift)
      unless pl.add_car(wait_time)
        wait.unshift(wait_time)    #満車の場合
        break
      end
    end
    
    break if pl.empty?
  end
  
  puts result.join(" ")
end

だいぶ勘違いをしていた。Ruby では三人しか出来ていないですよ。
 

0194 Delivery Company

MaxTime = 100

Truck = Struct.new(:x, :y, :dir, :time)

def get_hv(str)
  h, v = str.split("-")
  [h.bytes.first - 97, v.to_i - 1]
end

def signal_wait(x, y, signals, next_dir, time)
  signal = false
  movable = true
  signals.each do |hv, k|
    if x == hv[1] && y == hv[0]
      signal = true
      if (i = time / k).odd?    #東西方向が青?
        movable = false if next_dir.odd?
      else
        movable = false if next_dir.even?
      end
    end
  end
  [movable, signal]
end

def under_construction?(stat, x, y, constructions)
  constructions.each do |hv1, hv2|
    return true if stat.x == hv1[1] && stat.y == hv1[0] && x == hv2[1] && y == hv2[0]
    return true if stat.x == hv2[1] && stat.y == hv2[0] && x == hv1[1] && y == hv1[0]
  end
  false
end

def add_holdup(stat, x, y, holdups)
  next_time = stat.time
  holdups.each do |hv1, hv2, d|
    f1 = (stat.x == hv1[1] && stat.y == hv1[0] && x == hv2[1] && y == hv2[0])
    f2 = (stat.x == hv2[1] && stat.y == hv2[0] && x == hv1[1] && y == hv1[0])
    next_time += d if f1 || f2
  end
  next_time
end


until (mn = gets.split.map(&:to_i)) == [0, 0]
  d0 = gets.to_i
  signals = gets.to_i.times.map do
    hv, k = gets.chomp.split
    [get_hv(hv), k.to_i]
  end
  constructions = gets.to_i.times.map do
    hv1, hv2 = gets.chomp.split
    [get_hv(hv1), get_hv(hv2)]
  end
  holdups = gets.to_i.times.map do
    hv1, hv2, d = gets.chomp.split
    [get_hv(hv1), get_hv(hv2), d.to_i]
  end
  start, goal = gets.split.map {|hv| get_hv(hv)}
  field = Array.new(mn[0]) {Array.new(mn[1])}
  queue = [Truck.new(start[1], start[0], 0, 0)]
  field[start[0]][start[1]] = queue.first
  min_time = Float::INFINITY
  
  go = ->(stat, dir) {
    next_dir = (stat.dir + dir) % 4
    dx, dy = [[1, 0], [0, -1], [-1, 0], [0, 1]][next_dir]
    x = stat.x + dx
    y = stat.y + dy
    return [] if x < 0 || x >= mn[1] || y < 0 || y >= mn[0]
    
    return [] if under_construction?(stat, x, y, constructions)
    next_time = d0 + add_holdup(stat, x, y, holdups)
    movable, signal = signal_wait(x, y, signals, next_dir, next_time)
    return [] unless movable
    
    return [] if next_time > MaxTime
    
    next_stat = Truck.new(x, y, next_dir, next_time)
    tmp = field[y][x]
    
    return [next_stat] if signal
    if tmp
      return [] if tmp.time <= next_time
    end
    [field[y][x] = next_stat]
  }
  
  while (now = queue.shift)
    if now.x == goal[1] && now.y == goal[0]
      min_time = now.time if min_time > now.time
    else
      queue += go.(now, 0)
      queue += go.(now, 1)
      queue += go.(now, -1)
    end
  end
  
  puts min_time
end

10秒で時間オーバー。
 

0195 What is the Most Popular Shop in Tokaichi?

Shop = "ABCDE"
N = Shop.length

until (data = [gets.chomp]) == ["0 0"]
  data.concat (N - 1).times.map {gets}
  result = data.map.with_index {|d, i| [d.split.map(&:to_i).sum, i]}.sort.last
  puts "#{Shop[result[1]]} #{result[0]}"
end

 

0196 Baseball Championship

until (n = gets.to_i).zero?
  data = n.times.map {gets.chomp.split}
  scores = data.map {|n, *r| [n, r.count("0"), r.count("1")]}
               .sort {|a, b| (b[1] <=> a[1]).nonzero? || a[2] <=> b[2]}
  puts scores.map(&:first)
end

複数キーのソート。
 

0197 Greatest Common Divisor: Euclidean Algorithm

until (given = gets.chomp) == "0 0"
  x, y = given.split.map(&:to_i)
  x, y = y, x if x < y
  count = 0
  until y.zero?
    x = x % y
    x, y = y, x
    count += 1
  end
  puts "#{x} #{count}"
end

 

0198 Trouble in Shinagawa's Artifacts

table = [[0, 1, 2, 3, 4, 5], [3, 1, 0, 5, 4, 2], [1, 5, 2, 3, 0, 4],
         [4, 0, 2, 3, 5, 1], [2, 1, 5, 0, 4, 3], [0, 2, 4, 1, 3, 5],
         [0, 3, 1, 4, 2, 5], [5, 1, 3, 2, 4, 0], [1, 2, 0, 5, 3, 4],
         [4, 3, 0, 5, 2, 1], [3, 0, 4, 1, 5, 2], [3, 5, 1, 4, 0, 2],
         [5, 4, 2, 3, 1, 0], [2, 5, 4, 1, 0, 3], [1, 3, 5, 0, 2, 4],
         [2, 0, 1, 4, 5, 3], [4, 2, 5, 0, 3, 1], [0, 4, 3, 2, 1, 5],
         [1, 0, 3, 2, 5, 4], [4, 5, 3, 2, 0, 1], [5, 3, 4, 1, 2, 0],
         [5, 2, 1, 4, 3, 0], [2, 4, 0, 5, 1, 3], [3, 4, 5, 0, 1, 2]]
color_table = %w(Red Yellow Blue Magenta Green Cyan).map
                .with_index {|c, i| [c, i]}.to_h

until (n = gets.to_i).zero?
  dices = n.times.map { gets.split.map {|c_name| color_table[c_name]} }
  pool = []
  count = 0
  
  dices.each do |color|
    check_f = true
    table.each do |t|
      next_dice = t.map {|idx| color[idx]}
      if pool.include?(next_dice)
        count += 1 if check_f
        check_f = false
      else
        pool << next_dice
      end
    end
  end
  
  puts count
end

 

0199 Chairs Where Demanding People Sit

def a(seats)
  seats[seats.index("#")] = "A"
end

def b(seats, n)
  (n - 1).downto(0) do |i|
    if (i - 1 < 0 || seats[i - 1] != "A") && seats[i + 1] != "A" &&
        seats[i] == "#"
      seats[i] = "B"
      return
    end
  end
  seats[seats.index("#")] = "B"
end

def c(seats, n)
  if seats.count("#") == n
    idx = n / 2
  else
    n.times do |i|
      if seats[i] != "#"
        if seats[i + 1] == "#"
          idx = i + 1
          break
        elsif i - 1 >= 0 && seats[i - 1] == "#"
          idx = i - 1
          break
        end
      end
    end
  end
  seats[idx] = "C"
end

def d(seats, n)
  idx = 0
  if seats.count("#") != n
    max_dist = 0
    n.times do |i|
      d = nearest_dist(seats, i)
      if d > max_dist
        max_dist = d
        idx = i
      end    
    end
  end
  seats[idx] = "D"
end

def nearest_dist(seats, i)
  dist = 0
  dist += 1 until /[A-D]/ =~ seats[i + dist] ||
                  (i - dist >= 0 && /[A-D]/ =~ seats[i - dist])
  dist
end


until (given = gets.split.map(&:to_i)) == [0, 0]
  n, m = given
  seats = "#" * n
  m.times do
    case gets.chomp
    when "A" then a(seats)
    when "B" then b(seats, n)
    when "C" then c(seats, n)
    when "D" then d(seats, n)
    end
  end
  puts seats
end

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 falsefalse なのだけれど、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

ダイクストラ法。

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

 

ALDS1_10_B: Matrix Chain Multiplication

連鎖行列積問題(Matrix-Chain Multiplication problem)。

INF = (1 << 31) - 1

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

dp = Array.new(n + 1) {Array.new(n + 1, 0)}
dim = [ms[0][0]] + ms.map(&:last)

2.upto(n) do |l|
  1.upto(n - l + 1) do |i|
    j = i + l - 1
    dp[i][j] = INF
    i.upto(j - 1) do |k|
      tmp = dp[i][k] + dp[j][k] + dp[k + 1][j] + dim[i - 1] * dim[k] * dim[j]
      dp[i][j] = [dp[i][j], tmp].min
    end
  end
end

puts dp[1][n]

ここのパクリ。むずかしい。
※参考
連鎖行列積問題 - Qiita
動的計画法4 連鎖行列積 - Daily Tech Blog
連鎖行列積問題 : がぶ飲みミルク珈琲
※追記
わたしがパクったコードは、じつは『アルゴリズムイントロダクション 第3版 第2巻: 高度な設計と解析手法・高度なデータ構造・グラフアルゴリズム (世界標準MIT教科書)』のパクリだったことがわかった。

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