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 7 に CrystalDiskInfo をインストールして調べてみた。
「Crystal Disk Info」で、SSDの健康状態を把握しよう! | SSD徹底解説!
ただ、Wndows では ext4 が読み取れないので、下を参考に Ext2Fsd をインストールする。
ext4のパーティションをWindowsで読み書きする方法 | Linux Fan
以上の結果、下のように診断されました。
結果としては、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_by
を sort
と書くタイポがあって、なかなか気づけなかった。
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
Ruby のバージョンアップ
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
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!