ABC151

https://atcoder.jp/contests/abc151
過去問。

A

puts gets.chomp.succ

B

n, k, m = gets.split.map(&:to_i)
sum = gets.split.map(&:to_i).inject(&:+)

target = m * n - sum
result = case
         when target < 0 then 0
         when target > k then -1
         else target
         end

puts result

C

'WA' だけの問題はペナルティにカウントされないことになかなか気づかなかった。'AC' が出て初めてカウントしないといけない。

n, m = gets.split.map(&:to_i)
ps = m.times.map {gets.split}

memo = Array.new(n + 1)
penalty_memo = Hash.new(0)
score = penalty = 0

ps.each do |p, s|
  pn = p.to_i    #problem number
  next if memo[pn]
  case s
  when "AC"
    score += 1
    penalty += penalty_memo[pn]
    memo[pn] = true
  else
    penalty_memo[pn] += 1
  end
end

puts "#{score} #{penalty}"    

D

最初はTLE。それから、まさかの Ruby 2.3.3 なのにハマった。
方針がまちがっていた。スタートとゴールを設定して二重ループでやっていたが、よく考えてみたらスタートを設定してあとはいちばん遠いところへ行けばよいのだ。迷路を解くのはBFS。781ms。

class Position
  def initialize(x = 0, y = 0, count = 0)
    @x = x
    @y = y
    @count = count
  end
  attr_reader :x, :y, :count
end

h, w = gets.split.map(&:to_i)
maze = h.times.map {gets.chomp}
field = nil

Position.send(:define_method, :succ) do
  x = @x + 1
  y = @y
  if x >= w
    x = 0
    y += 1
    return false if y >= h
  end
  Position.new(x, y)
end

Position.send(:define_method, :move) do |dir|
  x, y = @x, @y
  dx, dy = [[1, 0], [0, -1], [-1, 0], [0, 1]][dir]
  x += dx
  y += dy
  return false if x >= w || x < 0 || y >= h || y < 0
  return false if field[y][x] != "."
  Position.new(x, y, @count + 1).mark
end

Position.send(:define_method, :mark) do
  field[@y][@x] = "*"
  self
end

solve_maze = ->(start) {
  return 0 if maze[start.y][start.x] == "#"
  field = maze.map(&:dup)
  max = 0
  q = [start.mark]
  while (po = q.shift)
    max = po.count if po.count > max
    4.times do |dir|
      nxt = po.move(dir)
      q << nxt if nxt
    end
  end
  max
}


start = Position.new
max = 0
loop do
  hosuu = solve_maze.(start)
  max = hosuu if hosuu > max
  break unless (start = start.succ)
end

puts max

E

TLE。

LIMIT = 10 ** 9 + 7

def factorial(n)
  result = 1
  2.upto(n) {|i| result *= i}
  result
end

def permutation(a, b)
  [*1..a].last(b).inject(1, &:*)
end
  
def combination(a, b)
  permutation(a, b) / factorial(b)
end


n, k = gets.split.map(&:to_i)
as = gets.split.map(&:to_i).sort
sum = 0

if k == 1
  puts 0
  exit
end

(0..n - k).each do |min|
  (min + k - 1..n - 1).each do |max|
    f = as[max] - as[min]
    sum += f * combination(max - min - 1, k - 2)
  end
end

puts sum % LIMIT

TLE。

LIMIT = 10 ** 9 + 7

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

acc = 1
factorial = [1] + (1..n).map {|i| acc *= i}
factorial_r = factorial.map {|a| Rational(1, a)}
combination = ->(a, b) {factorial[a] * factorial_r[b] * factorial_r[a - b]}

result = 0
(n - k + 1).times {|i| result -= as[i] * combination.(n - i - 1, k - 1)}
as.reverse!
(n - k + 1).times {|i| result += as[i] * combination.(n - i - 1, k - 1)}

puts result.to_i % LIMIT

ABC152

https://atcoder.jp/contests/abc152
過去問。

A

n, m = gets.split.map(&:to_i)
puts (n == m) ? "Yes" : "No"

B

a, b = gets.split.map(&:to_i)
result = a.to_s * b
tmp = b.to_s * a
result = tmp if result > tmp
puts result

C

これはすぐに思いついた。

n = gets.to_i
ps = gets.split.map(&:to_i)
min = ps.first
count = 0

ps.each do |p0|
  if p0 <= min
    count += 1
    min = p0
  end
end

puts count

D

とりあえず総当り。もちろんこれは提出していない。

n = io.gets.to_i
count = 0

(1..n).each do |i|
  il, ir = i.to_s[0], i.to_s[-1]
  (1..n).each do |j|
    jl, jr = j.to_s[0], j.to_s[-1]
    count += 1 if il == jr && ir == jl
  end
end

puts count

これで 1~200 を計算してみる。

[[1, 1], [2, 2], [3, 3], [4, 4], [5, 5], [6, 6], [7, 7], [8, 8], [9, 9], [10, 9], [11, 12], [12, 12], [13, 12], [14, 12], [15, 12], [16, 12], [17, 12], [18, 12], [19, 12], [20, 12], [21, 14], [22, 17], [23, 17], [24, 17], [25, 17], [26, 17], [27, 17], [28, 17], [29, 17], [30, 17], [31, 19], [32, 21], [33, 24], [34, 24], [35, 24], [36, 24], [37, 24], [38, 24], [39, 24], [40, 24], [41, 26], [42, 28], [43, 30], [44, 33], [45, 33], [46, 33], [47, 33], [48, 33], [49, 33], [50, 33], [51, 35], [52, 37], [53, 39], [54, 41], [55, 44], [56, 44], [57, 44], [58, 44], [59, 44], [60, 44], [61, 46], [62, 48], [63, 50], [64, 52], [65, 54], [66, 57], [67, 57], [68, 57], [69, 57], [70, 57], [71, 59], [72, 61], [73, 63], [74, 65], [75, 67], [76, 69], [77, 72], [78, 72], [79, 72], [80, 72], [81, 74], [82, 76], [83, 78], [84, 80], [85, 82], [86, 84], [87, 86], [88, 89], [89, 89], [90, 89], [91, 91], [92, 93], [93, 95], [94, 97], [95, 99], [96, 101], [97, 103], [98, 105], [99, 108], [100, 108], [101, 113], [102, 115], [103, 117], [104, 119], [105, 121], [106, 123], [107, 125], [108, 127], [109, 129], [110, 129], [111, 136], [112, 138], [113, 140], [114, 142], [115, 144], [116, 146], [117, 148], [118, 150], [119, 152], [120, 152], [121, 161], [122, 163], [123, 165], [124, 167], [125, 169], [126, 171], [127, 173], [128, 175], [129, 177], [130, 177], [131, 188], [132, 190], [133, 192], [134, 194], [135, 196], [136, 198], [137, 200], [138, 202], [139, 204], [140, 204], [141, 217], [142, 219], [143, 221], [144, 223], [145[152, 250], [153, 252], [154, 254], [155, 256], [156, 258], [157, 260], [158, 26, 289], [166, 291], [167, 293], [168, 295], [169, 297], [170, 297], [171, 316], [172, 318], [173, 320], [174, 322], [175, 324], [176, 326], [177, 328], [178, 330], [179, 332], [180, 332], [181, 353], [182, 355], [183, 357], [184, 359], [185, 361], [186, 363], [187, 365], [188, 367], [189, 369], [190, 369], [191, 392], [192, 394], [193, 396], [194, 398], [195, 400], [196, 402], [197, 404], [198, 406], [199, 408], [200, 408]]

　
これを眺めていて、漸化式を計算すればよいことがわかった。つまり、n が 1 増えるときに結果がいくつ増えるか考える。O(n)。

def calc(n)
  result = 0
  (1..n).each do |i|
    if i < 10
      result += 1
    else
      str = i.to_s
      digits = str.length - 2
      next if str[-1] == "0"
      if str[0] < str[-1]
        #i=1263だったら、13, 1_3みたいなやつ
        result += [0, 1, 11, 111, 1111][digits] * 2
      elsif str[0] > str[-1]
        #i=4321だったら、14, 1_4, 1__4みたいなやつ
        result += [1, 11, 111, 1111, 11111][digits] * 2
      else
        #i=1321だったら、1, 11, 1_1みたいなやつ
        result += [1, 2, 12, 112, 1112][digits] * 2
        #i=1321だったら、1001 ~ 1__1 ~ 1321みたいなやつで、1321は重複するので-1する
        result += (str[1..-2].to_i + 1) * 2 - 1
      end
    end
  end
  result
end

puts calc(gets.to_i)

まずまずうまく解けたと思う。207ms。
　

E

全体の最小公倍数を求める。あとはそれぞれの a で割って足すだけ。

LIMIT = 10 ** 9 + 7

n = gets
as = gets.split.map(&:to_i)
result = 0

lcm0 = as.inject(1) {|acc, i| acc.lcm(i)}
as.each {|ai| result += lcm0 / ai}

puts result % LIMIT

誰でも思いつく凡庸な方法ですぐにクリア。大きな数を簡単に扱えるのは Ruby の恩恵である。でも、時間は 1319 ms で全然よくない感じだが、調べてみると Ruby だとまあ皆んな同じようなものか。

演奏家 / 作曲家

作曲家

• グリゴール・ハチャトゥリアン Grigor Khachatryan （1986-） （NML）
• リチャード・ダニエルプール Richard Danielpour （1956-） （NML）

指揮者

• 山田和樹 （NML）

弦楽四重奏

• ドビュッシー四重奏団 Quatuor Debussy （NML）
• ミロ・クァルテット Miró Quartet （NML）

ピアノ・トリオ

• シトコヴェツキー・トリオ Sitkovetsky Trio （NML）

ピアノ

• ヴァネッサ・ベネッリ・モーゼル Vanessa Benelli Mosell （NML）
• セドリック・ペシャ Cédric Pescia （NML）
• クレール＝マリー・ル・ゲ Claire-Marie Le Guay （NML）
• ピ＝シェン・チェン or チェン・ピチェン Pi-hsien Chen （NML）
• レオン・マッコウリー Leon McCawley （NML）
• アレクサンドラ・パパステファノウ Alexandra Papastefanou （NML）
• オリヴィエ・カヴェー Olivier Cavé （NML）
• エリック・ル・サージュ Eric Le Sage （NML）
• マルセル・メイエ Marcelle Meyer （NML）

ヴァイオリン

• マイア・カベザ Maia Cabeza （NML）
• クリストフ・バラティ Kristóf Baráti （NML）

チェンバロ

• 辰巳美納子 （NML）

AOJ（問題集）23

0220 Binary Digit A Doctor Loved

小数の2進表現かあ。勉強になるなあ。なお、10進表現で循環小数でなくとも、2進表現で循環小数になる場合がある。

def calc(r, str = "")
  return str if str.length > 4
  a = r * 2
  b = a.to_i
  str += b.to_s
  c = a - b
  if c.zero?
    return str
  else
    calc(c, str)
  end
end


until (n = gets.to_f.rationalize) < 0
  integer_part = n.to_i
  decimal_part = n - integer_part
  
  result = "NA"
  str = integer_part.to_s(2)
  if str.length <= 8
    str = str.rjust(8, "0")
    tmp = calc(decimal_part)
    if tmp.length <= 4
      result = str + "." + tmp.ljust(4, "0")
    end
  end
  
  puts result
end

0221 FizzBuzz

発言データを一気読みしていなくてハマった。0.24秒。

e = Enumerator.new do |y|
  i = 1
  loop do
    y << case
         when (i % 15).zero? then "FizzBuzz"
         when (i %  3).zero? then "Fizz"
         when (i %  5).zero? then "Buzz"
         else i.to_s
         end
    i += 1
  end
end

until (given = gets.chomp) == "0 0"
  m, n = given.split.map(&:to_i)
  data = n.times.map {gets.chomp}
  table = Array.new(m, true)
  pointer = 0
  count = m
  
  inc = ->{
    pointer += 1
    pointer = 0 if pointer >= m
  }
  
  data.each do |said|
    break if count == 1
    inc.() until table[pointer]
    if said != e.next
      table[pointer] = false
      count -= 1
    end
    inc.()
  end
  
  puts table.map.with_index {|a, i| a ? (i + 1).to_s : nil}.compact.join(" ")
  e.rewind
end

　
これで0.21秒。あまり変わらないな。

e = Enumerator.new do |y|
  i = 1
  loop do
    y << case
         when (i % 15).zero? then "FizzBuzz"
         when (i %  3).zero? then "Fizz"
         when (i %  5).zero? then "Buzz"
         else i.to_s
         end
    i += 1
  end
end

until (given = gets.chomp) == "0 0"
  m, n = given.split.map(&:to_i)
  data = n.times.map {gets.chomp}
  table = (1..m).map(&:itself)
  pointer = 0
  
  data.each do |said|
    if said != e.next
      table.delete_at(pointer)
      break if table.size == 1
    else
      pointer += 1
    end
    pointer = 0 if pointer >= table.size
  end
  
  puts table.join(" ")
  e.rewind
end

0225 Kobutanukitsuneko

時間切れ。素朴な DFS。

loop do
  n = io.gets.to_i
  break if n.zero?
  words = n.times.map { io.gets.chomp }
  
  goal = words[0][0]
  try = ->(num, word) {
    if num.zero?
      word[-1] == goal
    else
      words.delete(word)
      words.select { |w| word[-1] == w[0] }.each do |w|
        f = try.(num - 1, w)
        return f if f
      end
      false
    end
  }
  puts try.(n - 1, words[0]) ? "OK" : "NG"
end

0226 Hit and Blow

loop do
  r, a = gets.split.map(&:chars)
  break if r == ["0"] && a == ["0"]
  
  r1, a1 = [], []
  hit = 0
  r.size.times do |i|
    if r[i] == a[i]
      hit += 1
    else
      r1 << r[i]
      a1 << a[i]
    end
  end
  blow = (r1 & a1).size
  puts "#{hit} #{blow}"
end

0227 Thanksgiving

loop do
  n, m = gets.split.map(&:to_i)
  break if n.zero? && m.zero?
  ps = gets.split.map(&:to_i).sort.reverse
  
  price = 0
  ps.each_slice(m) do |ary|
    if ary.size == m
      price += ary[0, m - 1].sum
    else
      price += ary.sum
    end
  end
  puts price
end

0228 Seven Segments

Pats = %w(0111111 0000110 1011011 1001111 1100110) +
       %w(1101101 1111101 0100111 1111111 1101111)

loop do
  n = gets.to_i
  break if n < 0
  ds = n.times.map { gets.to_i }
  
  disp = 0
  ds.each do |d|
    pat = Pats[d].to_i(2)
    puts "%07b" % (pat ^ disp)
    disp = pat
  end
end

0229 Big Hit !

loop do
  b, r, g, c, s, t = gets.split.map(&:to_i)
  break if b + r + g + c + s + t == 0
  
  medals = 100
  bonus = ->{
    medals += 15 + 1
  }
  b.times do
    medals += 15
    5.times { bonus.() }
  end
  r.times do
    medals += 15
    3.times { bonus.() }
  end
  medals += 7 * g
  medals += 2 * c
  medals += 3 * s
  medals -= 3 * t
  
  puts medals
end

Ruby でタイマーを作った

Gem 'kaki-utils' に入れた。
　
timer.rb

module Utils
  #簡易タイマー
  def timer(minutes)
    end_time = Time.now + (minutes * 60).to_i
    
    while Time.now < end_time
      print "\e[2K\e[1G" + "left: #{(end_time - Time.now).to_i} sec."
      sleep(1)
    end
    
    Utils.bell
    puts
  end
  module_function :timer
end

　
使用例。30秒後にベルが鳴る。（Ubuntu のみ）

$ bundle exec irb
irb(main):001:0> require "kaki/utils"
=> true
irb(main):002:0> Utils.timer(0.5)
left: 0 sec.
=> nil

（個人的）LaVie の Ubuntu 18.04 のファイルシステムが死んだので修復

Ubuntu が立ち上がらなくなってしまったので、Kubuntu のインストール・ディスクをお試しモードで立ち上げて修復する。

Ubuntu は /dev/sda3 だということを確認して、fsck で修復。

kubuntu@kubuntu:/$ umount /dev/sda3 
kubuntu@kubuntu:/$ fsck /dev/sda3 -p
fsck from util-linux 2.28.2
fsck.ext2: Permission denied while trying to open /dev/sda3
You must have r/w access to the filesystem or be root
kubuntu@kubuntu:/$ sudo fsck /dev/sda3 -p
fsck from util-linux 2.28.2
/dev/sda3 contains a file system with errors, check forced.
/dev/sda3: Inodes that were part of a corrupted orphan linked list found.  

/dev/sda3: UNEXPECTED INCONSISTENCY; RUN fsck MANUALLY.
        (i.e., without -a or -p options)

kubuntu@kubuntu:/$ sudo fsck /dev/sda3
fsck from util-linux 2.28.2
e2fsck 1.43.3 (04-Sep-2016)
/dev/sda3 contains a file system with errors, check forced.
Pass 1: Checking inodes, blocks, and sizes
Inodes that were part of a corrupted orphan linked list found.  Fix<y>? yes
Inode 14418682 was part of the orphaned inode list.  FIXED.
Inode 14419665 was part of the orphaned inode list.  FIXED.
Inode 14419758 was part of the orphaned inode list.  FIXED.
Inode 14419776 was part of the orphaned inode list.  FIXED.
Inode 14423215 was part of the orphaned inode list.  FIXED.
Inode 14423281 was part of the orphaned inode list.  FIXED.
Inode 14423330 was part of the orphaned inode list.  FIXED.
Inode 14423410 was part of the orphaned inode list.  FIXED.
Inode 20709604 was part of the orphaned inode list.  FIXED.
Inode 21758134 was part of the orphaned inode list.  FIXED.
Inode 21758255 was part of the orphaned inode list.  FIXED.
Inode 21759035 was part of the orphaned inode list.  FIXED.
Inode 21764033 was part of the orphaned inode list.  FIXED.
Pass 2: Checking directory structure
Pass 3: Checking directory connectivity
Pass 4: Checking reference counts
Pass 5: Checking group summary information
Block bitmap differences:  -196672 -(11081728--11083775) -(11085824--11087871) -(11089920--11091967) -(11094016--11096063) -(11098112--11100159) -(11102208--11104255) -(11106304--11108062) -82870390 -83039424 -83039568 -(83643970--83643985) -(83643994--83644009) -(83644068--83644075) -(83664452--83664459) -83664619 -83664890 -(83946396--83946399) -(85817921--85817928) -85818358 -(92887458--92887465)
Fix<y>? yes
Free blocks count wrong for group #6 (32089, counted=32090).
Fix<y>? yes
Free blocks count wrong for group #338 (868, counted=14915).
Fix<y>? yes
Free blocks count wrong for group #2529 (26184, counted=26185).
Fix<y>? yes
Free blocks count wrong for group #2534 (13904, counted=13906).
Fix<y>? yes
Free blocks count wrong for group #2552 (9182, counted=9222).
Fix<y>? yes
Free blocks count wrong for group #2553 (9769, counted=9779).
Fix<y>? yes
Free blocks count wrong for group #2561 (10796, counted=10800).
Fix<y>? yes
Free blocks count wrong for group #2618 (1808, counted=1817).
Fix ('a' enables 'yes' to all) <y>? yes to all
Free blocks count wrong for group #2834 (18779, counted=18787).
Fix? yes

Free blocks count wrong (63838170, counted=63852292).
Fix? yes

Inode bitmap differences:  -14417977 -14418682 -14419665 -14419758 -14419776 -14423215 -14423281 -14423330 -14423410 -20709604 -21758134 -21758255 -21759035 -21764033
Fix? yes

Free inodes count wrong for group #1760 (5, counted=14).
Fix? yes

Free inodes count wrong for group #2528 (1718, counted=1719).
Fix? yes

Free inodes count wrong for group #2656 (1995, counted=1999).
Fix? yes

Free inodes count wrong (22957171, counted=22957185).
Fix? yes


/dev/sda3: ***** FILE SYSTEM WAS MODIFIED *****
/dev/sda3: 1094527/24051712 files (0.4% non-contiguous), 32339114/96191406 blocks
kubuntu@kubuntu:/$ 

　
これで立ち上がるようになった。

Ubuntu で unattended-upgrades を無効にする

apt upgrade とかが出来なくなるので、unattended-upgrades を無効にしたい。
　

$ sudo apt install -y unattended-upgrades
$ sudo dpkg-reconfigure --priority=low unattended-upgrades
Replacing config file /etc/apt/apt.conf.d/20auto-upgrades with new version

訊かれる質問には「No」を選択する。

AOJ（問題集）22

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

Zork を 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.

AtCoder/ABC138

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 はスタックオーバーフローになっていたみたいだ。