2019-12-09

AOJ（問題集）22

AOJ Ruby

0210 The Squares

むずかしかった。何とか自力で出来た。

Table = %W(E N W S)

Man = Struct.new(:x, :y, :dir, :next_x, :next_y) do
  def next
    dx, dy = [[1, 0], [0, -1], [-1, 0], [0, 1]][self.dir]
    self.next_x, self.next_y = self.x + dx, self.y + dy
  end
  
  def move(field)
    field[self.y][self.x] = "."
    self.x, self.y = self.next_x, self.next_y
    self.next
    if field[self.y][self.x] == "X"
      return [self, true]
    else
      field[self.y][self.x] = Table[self.dir]
      return [self, false]
    end
  end
  
  def turn(field)
    [-1, 0, 1, 2].each do |step|
      next_dir = (self.dir + step) % 4
      dx, dy = [[1, 0], [0, -1], [-1, 0], [0, 1]][next_dir]
      type = field[self.y + dy][self.x + dx]
      if type == "." || type == "X"
        self.dir = next_dir
        field[self.y][self.x] = Table[next_dir]
        self.next
        return
      end
    end
  end
end


def passage(persons, field)
  h = Hash.new([])
  persons.each do |man|
    next_type = field[man.next_y][man.next_x]
    next unless next_type == "." || next_type == "X"
    h[[man.next_x, man.next_y]] += [man]
  end
  h.values
end


loop do
  w, h = gets.split.map(&:to_i)
  break if (w + h).zero?
  
  field = h.times.map {gets.chomp.chars}
  
  persons = []
  field.each_with_index do |row, y|
    row.each_with_index do |po, x|
      idx = Table.index(po)
      persons << Man.new(x, y, idx) if idx
    end
  end
  persons.each(&:next)
  
  t = 1
  loop do
    persons.each {|man| man.turn(field)}
    
    passage(persons, field).each do |ary|
      man, flag = if ary.size == 1
        ary[0].move(field)
      else
        ary.sort_by {|man0| (man0.dir + 2) % 4}[0].move(field)
      end
      persons.delete(man) if flag
    end
    
    break if t > 180
    break if persons.empty?
    t += 1
  end
  
  puts (t > 180) ? "NA" : t
end

0211 Jogging

until (n = gets.to_i).zero?
  data = n.times.map {gets.split.map(&:to_i)}.map {|a, b| Rational(a, b)}
  lcm = data.map(&:denominator).inject(:lcm)
  nums = data.map {|d| Rational(1, d * lcm)}
  
  lcm = nums.map(&:denominator).inject(:lcm)
  puts nums.map {|n| (n * lcm).to_i}
end

だいぶ考えた。しかし Ruby は大きい整数を扱うのがラクなので、そんなにむずかしくない。
　

0212 Highway Express Bus

require "set"

INF = (1 << 31) - 1
TownMax = 100

until (given = gets.chomp) == "0 0 0 0 0"
  c, n, m, s, d = given.split.map(&:to_i)
  s -= 1
  d -= 1
  data = m.times.map {gets.split.map(&:to_i)}
  
  fares = Array.new(n) {[]}
  route_map = Array.new(n, [])
  towns = Set.new
  
  data.each do |a, b, f|
    a -= 1
    b -= 1
    route_map[a] += [b]
    route_map[b] += [a]
    fares[a][b] = fares[b][a] = f
    towns << a
    towns << b
  end
  
  shortest = Array.new(c + 1) {Array.new(TownMax, INF)}
  done = Array.new(c + 1) {Array.new(TownMax, false)}
  
  shortest[0][s] = 0
  
  loop do
    u0 = u1 = nil
    (c + 1).times do |ticket|
      towns.each do |town|
        next if done[ticket][town]
        if !u0 or shortest[ticket][town] < shortest[u0][u1]
          u0, u1 = ticket, town
        end
      end
    end
    break unless u0
    done[u0][u1] = true
    
    route_map[u1].each do |to|
      if (a0 = shortest[u0][u1] + fares[u1][to]) < shortest[u0][to]
        shortest[u0][to] = a0
      end
      if u0 + 1 <= c
        if (a1 = shortest[u0][u1] + fares[u1][to] / 2) < shortest[u0 + 1][to]
          shortest[u0 + 1][to] = a1
        end
      end
    end
  end
  
  puts shortest.map {|a| a[d]}.min
end

拡張ダイクストラ法だって。わけがわからない。ここを参考にした。
これが圧倒的に速い。たぶん単純なバックトラック。うーむ。
　

0213 Subdivide The Land

バックトラック法なのだけれど、時間オーバー。頑張って実装したのだけれどなあ。

class Field
  def initialize(width, height)
    @w, @h = width, height
    @field = Array.new(height) {Array.new(width, 0)}
  end
  
  def write(x, y, width, height, num, delete = false)
    tmp = @field.dup.map {|row| row.dup}
    height.times do |i|
      yy = y + i
      return false if yy < 0 || yy >= @h
      width.times do |j|
        xx = x + j
        return false if xx < 0 || xx >= @w
        type = tmp[yy][xx]
        return false if type.nonzero? && !delete
        tmp[yy][xx] = num
        tmp
      end
    end
    @field = tmp
    true
  end
  
  def to_s
    @field.map {|row| row.join(" ")}
  end
end

def search(field_area)
  (1..Math.sqrt(field_area).to_i).each do |i|
    n0 = field_area % i
    if n0.zero?
      yield(i, n = field_area / i)
      yield(n, i) if i != n
    end
  end
end


until (xyn = gets.chomp) == "0 0 0"
  x, y, n = xyn.split.map(&:to_i)
  field_areas = n.times.map {gets.split.map(&:to_i)}.sort.map(&:last)
  init_field = y.times.map {gets.split.map(&:to_i)}
    
  if field_areas.sum != x * y
    puts "NA"
    exit
  end
  
  field_num = Array.new(n)
  init_field.each_with_index do |row, y0|
    row.each_with_index do |num, x0|
      field_num[num - 1] = [x0, y0] if num.nonzero?
    end
  end
  
  field = Field.new(x, y)
  result = nil
  
  try = ->(customer){
    if customer == n
      if result
        result = "NA"
        false
      else
        result = field.to_s
        true
      end
    else
      search(field_areas[customer]) do |width, height|
        x0, y0 = field_num[customer]
        height.times do |dy|
          width.times do |dx|
            f = field.write(x0 - dx, y0 - dy, width, height, customer + 1)
            next unless f
            return false unless try.(customer + 1)
            field.write(x0 - dx, y0 - dy, width, height, 0, true)
          end
        end
      end
      true
    end
  }
  try.(0)
  
  result = "NA" unless result
  puts result
end

0216 Cutting Down Water Bills

while (w = gets.to_i) >= 0
  water_rate = case
               when w <= 10 then 1150
               when w <= 20 then 1150 + 125 * (w - 10)
               when w <= 30 then 2400 + 140 * (w - 20)
               else 3800 + 160 * (w - 30)
               end
  puts 4280 - water_rate
end

0217 Walking in the Hospital

until (n = gets.to_i).zero?
  result = n.times.map {gets.split.map(&:to_i)}
            .map {|p, d1, d2| [p, d1 + d2]}
            .max {|a, b| a[1] <=> b[1]}
  puts result.join(" ")
end

0218 Dividing Students

until (n = gets.to_i).zero?
  n.times.map {gets.split.map(&:to_i)}.each do |m, e, j|
    math_eng_av = (m + e) / 2.0
    three_av = (m + e + j) / 3.0
  
    klass = case
            when [m, e, j].include?(100) then :A
            when math_eng_av >= 90 then :A
            when three_av >= 80 then :A
            when three_av >= 70 then :B
            when three_av >= 50 && [m, e].max >= 80 then :B
            else :C
            end
    puts klass
  end
end

0219 A Popular Ice-cream Shop

ICE = 10

until (n = gets.to_i).zero?
  count = Array.new(ICE, 0)
  n.times.map {gets.to_i}.each {|type| count[type] += 1}
  
  puts count.map {|num| num.zero? ? "-" : "*" * num}
end

2019-10-29

Zork を Linux で遊ぶ

Linux

大昔のテキスト・アドヴェンチャー・ゲームである「Zork」を、Ubuntu 系で遊ぶ仕方です。

まず、以下でゲーム用のインタプリタをインストールします。

$ sudo apt-get install frotz

　
ゲームのデータは以下にあります。ダウンロード・展開して下さい。
http://www.infocom-if.org/downloads/downloads.html
　
そして、「Zork I」なら以下のようにします。

$ cd zork1
$ frotz DATA/ZORK1.DAT

これでゲームが始まる筈です。

　

README.TXT の一部

Gameplay notes
-----------------------------------------------------------------------------------------------------
The game is a text adventure and recognizes different words that you type in to
the computer. The following is a list of some (but not all) of the verbs that
you can use:
look take
examine kill
talk open
close enter
exit push
pull lift
move tie
You can also use compass directions to indicate that you want to move in that
direction. For example, you can type:
"go north"
or you can type
"north"
or just
"n"
Typical directions are N,S,E,W,NE,NW,SE,SW,Up,Down
To save a game, type "save" and the name of the game you want to save.
To load a game, type "restore" and the name of the game you want to load.

2019-08-20

AtCoder/ABC138

AtCoder Ruby

https://atcoder.jp/contests/abc138

A - Red or Not

puts (gets.to_i >= 3200) ? gets.chomp : "red"

B - Resistors in Parallel

gets
as = gets.split.map(&:to_i)

puts Rational(1, as.map {|i| Rational(1, i)}.inject(:+)).to_f

C - Alchemist

gets
as = gets.split.map(&:to_i).sort

def calc(ary)
  return ary.first if ary.size == 1
  a = Rational(ary[0] + ary[1], 2)
  calc([a] + ary[2..-1])
end

puts calc(as).to_f

いや、これわからんよ。思いつかないし。
　

D - Ki

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

#頂点 a と b を結ぶ
tree = Array.new(n + 1) {[]}
(n - 1).times do
  a, b = gets.split.map(&:to_i)
  tree[a] << b
  tree[b] << a
end

#頂点 p は根で、部分木のすべての頂点に足されるのは x
total = Array.new(n + 1, 0)
q.times do
  p, x = gets.split.map(&:to_i)
  total[p] += x
end

#実際に足す操作
visited = Array.new(n + 1)
queue = [1]
until queue.empty?
  c = queue.shift
  visited[c] = true
  tree[c].each do |q|
    next if visited[q]
    total[q] += total[c]
    queue << q
  end
end
 
puts total[1..n].join(" ")

RE はスタックオーバーフローになっていたみたいだ。

2019-08-17

ある双曲線の整数解

数学 Ruby

36*x^2-4*x-71*y^2+8=0 の整数解の導出。

Ruby でできるだけ解いてみる。
solve.rb

dir = [[1, 0], [0, 1], [-1, 0], [0, -1]]

x = y = 0
step = 1
f = ->{p [x, y] if 36 * x ** 2 - 4 * x - 71 * y ** 2 + 8 == 0}
add = ->(i) {
  dx, dy = dir[i]
  x += dx
  y += dy
}

loop do
  2.times do |j|
    step.times do
      f.()
      add.(j * 2)
    end
    step.times do
      f.()
      add.(j * 2 + 1)
    end
    step += 1
  end
end

　
実行。

$ ruby solve.rb
[-1629, 1160]
[-1629, -1160]

これしか見つかっていない。

2019-08-14

AtCoder/ABC137

AtCoder Ruby

A - +-x

a, b = gets.split.map(&:to_i)
puts [a + b, a - b, a * b].max

B - One Clue

k, x = gets.split.map(&:to_i)
puts [*x - k + 1..x + k - 1].join(" ")

C - Green Bin

words = gets.to_i.times.map {gets.chomp.chars.sort.join}.group_by(&:itself)
ans = words.inject(0) do |acc, (_, ary)|
  l = ary.size
  l == 1 ? acc : acc + l * (l - 1) / 2
end
puts ans

これは他の人の回答を見た。
あとで自分で考えたもの。

table = {}
count = 0
 
gets.to_i.times.map {gets.chomp.chars.sort}.each do |word|
  if table[word]
    table[word] += 1
    count += table[word]
  else
    table[word] = 0
  end
end
puts count

D - Summer Vacation

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]
    b = @heap.pop
    @size -= 1
    return b if @heap.size == 1
    @heap[1] = b
    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
  
  def size
    @heap.size - 1
  end
end


n, m = gets.split.map(&:to_i)
given = Hash.new {|h, v| h[v] = []}
n.times.each do
  a, b = gets.split.map(&:to_i)
  given[a] << b
end

mh = MaxHeap.new
sum = 0

(1..m).each do |left_day|
  given[left_day].each {|reward| mh.insert(reward)}
  sum += mh.remove_root unless mh.size.zero?
end
puts sum

これを参考にして、優先度付きキューを実装して頑張った。優先度付きキューは以前に自分で実装したのだけれど、バグがあったりして直した。きちんと使える実装（参照）が手に入ってうれしいけれど、そもそも Ruby では標準添付ライブラリにこれがないのだよなあ。Python はあるらしいのに…。
　

E - Coins Respawn

全然わからないのでいろいろ参考にする。これが参考になりまくり。パクった。

INF = 1 << 60

n, m ,p = gets.split.map(&:to_i)
g = []
to = Array.new(n + 1) {[]}
ot = Array.new(n + 1) {[]}
m.times do
  a, b, c = gets.split.map(&:to_i)
  g << [a, b, -(c - p)]
  to[a] << b
  ot[b] << a
end

toflag = [0] * (n + 1)
toflag[1] = 1
iki = ->(v) {
  to[v].each do |u|
    if toflag[u].zero?
      toflag[u] = 1
      iki.(u)
    end
  end
}
iki.(1)

otflag = [0] * (n + 1)
otflag[n] = 1
kaeri = ->(v) {
  ot[v].each do |u|
    if otflag[u].zero?
      otflag[u] = 1
      kaeri.(u)
    end
  end
}
kaeri.(n)

cand = toflag.zip(otflag).map {|a, b| a * b}
max_count = cand.count(1)
g.select! {|a, b, _| cand[a] == 1 && cand[b] == 1}

bellman_ford = ->{
  inf = INF
  d = Array.new(n + 1, inf)
  d[1] = 0
  max_count.times do
    update = false
    g.each do |v, u, cost|
      if d[v] != inf && d[u] > (a = d[v] + cost)
        d[u] = a
        update = true
      end
    end
    return -d[n] unless update
  end
  inf
}
ans = bellman_ford.()

ans = (ans == INF) ? -1 : [ans, 0].max
puts ans

なんと、Float::INFINITY を 1 << 60 に直したら TLE が解消された。ははあ、なるほど。

2019-08-13

AtCorder/ABC（その1）

AtCoder Ruby

ABC001

A - 積雪深差

puts gets.to_i - gets.to_i

　
B - 視程の通報

ans = case (m = gets.to_i)
      when 0...100      then 0
      when 100..5000    then m / 100
      when 6000..30000  then m / 1000 + 50
      when 35000..70000 then (m / 1000 - 30) / 5 + 80
      else 89
      end
puts sprintf "%02d", ans

　
C - 風力観測

Houi = %W(NNE NE ENE E ESE SE SSE S SSW SW WSW W WNW NW NNW)
Fuuryoku_table = [[0.0, 0.2], [0.3, 1.5], [1.6, 3.3], [3.4, 5.4], [5.5, 7.9],
                  [8.0, 10.7], [10.8, 13.8], [13.9, 17.1], [17.2, 20.7],
                  [20.8, 24.4], [24.5, 28.4], [28.5, 32.6]]
 
deg, dis = gets.split.map(&:to_i)
kazamuki = "N"
 
112.5.step(3265.5, 225).with_index do |d, i|
  kazamuki = Houi[i] if d <= deg && deg < d + 225
end
 
fuusoku = (dis / 60.0).round(1)
fuuryoku = 12
Fuuryoku_table.each_with_index do |f, i|
  fuuryoku = i if fuusoku.between?(f.first, f.last)
end
 
kazamuki = "C" if fuuryoku.zero?
puts "#{kazamuki} #{fuuryoku}"

　
D - 感雨時刻の整理

memo = gets.to_i.times.map {gets.split("-").map(&:to_i)}
modified = memo.map do |t0|
  t0.map.with_index do |t, i|
    m = (t / 100) * 60 + t % 100
    m += 4 if i > 0
    m = (m / 5) * 5
    (m / 60) * 100 + m % 60
  end    
end.sort
 
be, af = modified.shift
modified.each do |s, e|
  if s.between?(be, af)
    af = e if e > af
  else
    puts sprintf "%04d-%04d", be, af
    be, af = s, e
  end
end
puts sprintf "%04d-%04d", be, af

5分単位の時刻に丸めるのが上手くいっていなかった。きちんと分に直してやらないといけないのね。
別解。

Day = 60 * 24
work = Array.new(Day + 1, 0)
 
gets.to_i.times.map {gets.split("-").map(&:to_i)}.each do |t0|
  t0.each_with_index do |t, i|
    m = (t / 100) * 60 + t % 100
    m += 4 if i > 0
    m = (m / 5) * 5
    work[m] += i.zero? ? 1 : -1
  end    
end
 
Day.times {|i| work[i + 1] += work[i]}
 
be = nil
(Day + 1).times do |t|
  if !be && work[t] > 0
    be = (t / 60) * 100 + t % 60
  elsif be && work[t] < 1
    af = (t / 60) * 100 + t % 60
    puts sprintf "%04d-%04d", be, af
    be = nil
  end
end

いもす法。
　

ABC002

A - 正直者

a, b = gets.split.map(&:to_i)
puts a > b ? a : b

あるいは

puts gets.split.map(&:to_i).max

　
B - 罠

puts (gets.chomp.chars - %W(a i u e o)).join

　
C - 直訴

xa, ya, xb, yb, xc, yc = gets.split.map(&:to_i)
puts ((xa - xc) * (yb - yc) - (xb - xc) * (ya - yc)).abs / 2.0

　
D - 派閥

n, m = gets.split.map(&:to_i)
relations = Hash.new {|h, k| h[k] = [k]}
 
m.times do
  x, y = gets.split.map(&:to_i)
  relations[x] << y
  relations[y] << x
end
 
n.downto(1) do |i|
  [*1..n].combination(i) do |persons|
    if persons.all? {|p| persons & relations[p] == persons}
      puts i
      exit
    end
  end
end

最大クリーク問題だってさ。最大で12人しかいないので、総当りで解いている。
　

ABC003

A - AtCoder社の給料

n = gets.to_i
puts (1..n).inject(0) {|acc, i| acc + 10000 * i * Rational(1, n)}.to_i

2019-07-31

AOJ（問題集）21

AOJ Ruby

0200 Traveling Alone: One-way Ticket of Youth

until (given = gets.split.map(&:to_i)) == [0, 0]
  n, m = given
  edge = Array.new(m) {[]}
  h = Array.new(m) {[]}
  n.times do
    a, b, cost, time = gets.split.map(&:to_i)
    a -= 1
    b -= 1
    edge[a][b] = edge[b][a] = [cost, time]
    h[a] << b
    h[b] << a
  end
  
  gets.to_i.times do
    p, q, r = gets.split.map(&:to_i)
    p -= 1
    q -= 1
  
    shortest = Array.new(m, Float::INFINITY)
    done = m.times.map(&:itself)
    shortest[p] = 0
    
    until done.empty?
      u = done.min {|a, b| shortest[a] <=> shortest[b]}
      done.delete(u)
      
      h[u].each do |v|
        if (a = shortest[u] + edge[u][v][r]) < shortest[v]
          shortest[v] = a
        end
      end
    end
    
    puts shortest[q]
  end
end

ダイクストラ法なのだが、他の人の回答を見て徹底的に高速化する。これで 3.30秒。
　

0201 Wrought Gold Master

until (n = gets.to_i).zero?
  costs = n.times.map { gets.split.tap {|a| a[1] = a[1].to_i} }.to_h
  
  m = gets.to_i
  recipe = Hash.new {|hash, key| hash[key] = []}
  m.times do
    given = gets.split
    recipe[given[0]] += given[2..-1]
  end
  goal = gets.chomp
  
  try = ->(parent) {
    r = recipe[parent]
    c = costs[parent]
    if r.empty?
      c
    else
      made = r.map {|child| try.(child)}.sum
      [made, c].min
    end
  }
  puts try.(goal)
end

DFS（深さ優先探索）。錬金釜で作った方が安いかチェックを入れる。
　

0202 At Boss's Expense

require "prime"

until (given = io.gets.split.map(&:to_i)) == [0, 0]
  dishes = given[0].times.map {io.gets.to_i}
  
  result = 0
  dp = Array.new(given[1] + 1, false)
  dp[0] = true
  
  (1..given[1]).each do |i|
    dishes.each do |price|
      if i >= price && dp[i - price]
        dp[i] = true
        break
      end
    end
    result = i if dp[i] && i.prime?
  end
  
  puts result.zero? ? "NA" : result
end

時間オーバー。これは Ruby ではかなり無理っぽい。出来ている人は一人しかいない。
　

0203 A New Plan of Aizu Ski Resort

loop do
  w, h = gets.split.map(&:to_i)
  break if w + h == 0
  
  field = h.times.map {gets.split.map(&:to_i)}
  dp = Array.new(h) {Array.new(w, 0)}
  w.times {|x| dp[h - 1][x] = 1 if field[h - 1][x] != 1}
  
  (h - 2).downto(0) do |y|
    w.times do |x|
      case field[y][x]
      when 2
        if y + 2 == h
          dp[y][x] = 1
        else
          dp[y][x] = dp[y + 2][x]
        end
      when 0
        s = 0
        [-1, 0, 1].each do |dx|
          x1 = x + dx
          next if x1 < 0 || x1 == w
          next if dx.nonzero? && field[y + 1][x1] == 2
          s += dp[y + 1][x1]
        end
        dp[y][x] = s
      end
    end
  end
  
  puts dp[0].sum
end

動的計画法。これをパクリましたよ。いやー、むずかしいなあ。
　

0204 UFO Shooting Down Operation

class Ufo
  def initialize(x, y, r, v)
    @dist = Math.sqrt(x ** 2 + y ** 2)
    @x = x
    @y = y
    @r = r
    @v = v
    @ex = x / @dist
    @ey = y / @dist
    @vx = -v * @ex
    @vy = -v * @ey
  end
  attr_reader :x, :y, :r, :dist, :ex, :ey
  
  def move
    @dist -= @v
    @x += @vx
    @y += @vy
  end
end

loop do
  radius, n = gets.split.map(&:to_i)
  break if (radius + n).zero?
  
  ufos = n.times.map {Ufo.new(*gets.split.map(&:to_i))}
  count = 0
  
  loop do
    ufos.each(&:move)
    ufos.sort_by! {|u| u.dist}
    
    ufos1 = ufos.select {|u| u.dist <= radius}
    count += ufos1.size
    ufos -= ufos1
    break if ufos.size.zero?
    
    min = ufos.shift
      
    ufos = ufos.reject do |u|
      r = (min.y * u.x - min.x * u.y).abs / min.dist
      r < u.r &&
          u.dist * (min.ex * u.ex + min.ey * u.ey) +
             Math.sqrt(u.r ** 2 - r ** 2) > radius
    end
    break if ufos.size.zero?
  end
  
  puts count
end

これむずかしすぎでしょう。検索して初めてわかった。
　

0205 Rock, Paper, Scissors

until (a = gets.to_i).zero?
  given = [a] + 4.times.map {gets.to_i}
  
  hands = given.uniq
  if hands.size == 3 || hands.size == 1
    result = [3] * 5
  else
    point = (hands[0] - hands[1]) % 3 == 2 ? 1 : 2
    result = given.map do |hand|
      hand == hands[0] ? point : 3 - point
    end
  end
  
  puts result
end

突然簡単に。
　

0206 Next Trip

until (l = gets.to_i).zero?
  data = 12.times.map {gets.split.map(&:to_i)}
  month_number = "NA"
  
  acc = 0
  data.each_with_index do |mn, i|
    acc += mn[0] - mn[1]
    if acc >= l
      month_number = i + 1
      break
    end
  end
  
  puts month_number
end

簡単。
　

0207 Block

Position = Struct.new(:x, :y)

loop do
  w, h = gets.split.map(&:to_i)
  break if (w + h).zero?
  field = Array.new(h + 1) {Array.new(w + 1, 0)}
  
  xs, ys = gets.split.map(&:to_i)
  xg, yg = gets.split.map(&:to_i)
  start = Position.new(xs, ys)
  
  gets.to_i.times do
    color, direction, x, y = gets.split.map(&:to_i)
    width, height = direction.zero? ? [4, 2] : [2, 4]
    height.times do |h1|
      width.times {|w1| field[y + h1][x + w1] = color}
    end
  end
  
  start_color = field[ys][xs]
  field[ys][xs] = 100
  stack = [start]
  result = "NG"
  
  while (po = stack.shift)
    if po.x == xg && po.y == yg
      result = "OK"
      break
    else
      [[1, 0], [0, -1], [-1, 0], [0, 1]].each do |dx, dy|
        next_x, next_y = po.x + dx, po.y + dy
        next if next_x <= 0 || next_x > w || next_y <= 0 || next_y > h
        if field[next_y][next_x] == start_color
          stack << Position.new(next_x, next_y)
          field[next_y][next_x] = 100
        end
      end
    end
  end
  
  puts result
end

幅優先探索。簡単。
　

0208 Room Numbers of a Hospital

Table = [0, 1, 2, 3, 3, 4 ,4, 5, 6, 7]

def func(num)
  num1 = num.to_s.chars
  result = 0
  loop do
    top = num1.shift.to_i
    digits = num1.size
    result += Table[top] * 8 ** digits
    break if digits.zero?
  end
  result
end

until (num = gets.to_i).zero?
  puts (1..9358757000).bsearch {|i| num <= func(i)}
end

何かダメ。検索してみる。

Table = [0, 1, 2, 3, 5, 7, 8, 9]

def f(n)
  f(n / 8) if n >= 8
  print Table[n % 8]
end

until (num = gets.to_i).zero?
  f(num)
  puts
end

世の中にはかしこい人がいますな。
　

0209 Scene in a Picture

loop do
  n, m = gets.split.map(&:to_i)
  break if (n + m).zero?
  
  scene   = n.times.map {gets.split.map(&:to_i)}
  picture = m.times.map {gets.split.map(&:to_i)}
  
  pictures = []
  4.times do
    pictures << picture 
    picture = picture.reverse.transpose    #右回転
  end
  
  check = ->{
    result = []
    (0..n - m).each do |y|
      (0..n - m).each do |x|
        pictures.each do |pic|
          catch :jump {
            nx = ny = nil
            m.times do |dy|
              m.times do |dx|
                next if pic[dy][dx] == -1
                nx, ny = x + dx, y + dy unless nx
                throw :jump if pic[dy][dx] != scene[y + dy][x + dx]
              end
            end
            result << [nx + 1, ny + 1]
          }
        end
      end
      return result unless result.empty?
    end
    "NA"
  }
  result = check.()
  
  if result != "NA"
    result = result.sort! {|a, b| (a[1] <=> b[1]).nonzero? || a[0] <=> b[0]}[0].join(" ")
  end
  puts result
end

凡庸なコード。でも Ruby では三人しか出来ていないね。

2019-07-03

E: ロック /var/lib/dpkg/lock-frontend が取得できませんでした - open (11: リソースが一時的に利用できません)

Linux

追記
ここへいらっしゃった方は、たぶん unattended-upgrades のせいで apt が使えないのだと思います。以下を見ることをお勧めします。
marginalia.hatenablog.com

Ubuntu で apt を使おうとしたら以下が出る。

E: ロック /var/lib/dpkg/lock-frontend が取得できませんでした - open (11: リソースが一時的に利用できません)
E: Unable to acquire the dpkg frontend lock (/var/lib/dpkg/lock-frontend), is another process using it?

対策

$ sudo rm /var/lib/apt/lists/lock
$ sudo rm /var/lib/dpkg/lock
$ sudo rm /var/lib/dpkg/lock-frontend

　
これでダメなら

$ sudo apt autoremove

これだけでもいけると書いてあるサイトもある。

※参考
Ubuntu 18.04¤Çlock¥Õ¥¡¥¤¥ë´ØÏ¢¤ÎÉÔ¶ñ¹ç | ¤Í¤³¤á¤â
　

追記

上の原因が unattended-upgrades によるものなら、以下を試した方がよい。
Ubuntu で unattended-upgrades を無効にする - Marginalia

2019-06-23

Windows 8.1, Ruby 2.6.3 に gtk2

2019-06-23

Windows 8.1, Ruby 2.6.3 に gem 'glib2' が入らない