AOJ(問題集)15
AIZU ONLINE JUDGE: Programming Challenge
0140 Bus Line
line = [*0..9] + [5, 4, 3, 2, 1] line += line $<.gets.to_i.times do start, goal = $<.gets.split.map(&:to_i) str = if 1 <= start and start <= 5 and start > goal [*goal..start].reverse.join(" ") else a = line.index(start) b = line[a + 1..-1].index(goal) line[a..a + 1 + b].join(" ") end puts str end
0141 Spiral Pattern
ぐるぐる模様。
result = [] $<.gets.to_i.times do n = $<.gets.to_i field = Array.new(n) {" " * n} x, y = 0, n - 1 go = ->(dx, dy, l) { l.times do field[y][x] = "#" x += dx y += dy end } square = ->(l) { if l != 1 go.(0, -1, l - 1) go.(1, 0, l - 1) go.(0, 1, l - 1) if l != 3 go.(-1, 0, l - 3) if l != 4 if l > 4 go.(0, -1, 2) square.(l - 4) end return end end end field[y][x] = "#" } square.(n) result << field.map {|l| l + "\n"}.join end puts result.join("\n")
思っていたよりずっとむずかしかった。これがいちばんよいやり方か自信がない。実際、Ruby で解けた人は自分も含めて 4人しかいない。
0142 Nature of Prime Numbers
素朴に実装してみる。
until (n = $<.gets.to_i).zero? rems = (1...n).map {|i| i * i % n}.uniq.permutation(2).map do |a, b| rem = a - b rem += n if rem < 0 rem = n - rem if rem > (n - 1) / 2 rem end puts (1..(n - 1) / 2).map {|i| rems.count(i)} end
時間オーバー。
0143 Altair and Vega
require 'matrix' $<.gets.to_i.times do given = $<.gets.split.map(&:to_r).each_slice(2).map {|x, y| Vector[x, y]} p1, p2, p3, k, s = given calc = ->(r) { Matrix.columns([p2 - p1, p3 - p1]).lup.solve(r - p1).to_a } s1, t1 = calc.(k) s2, t2 = calc.(s) f1 = s1 + t1 < 1 && s1 > 0 && t1 > 0 f2 = s2 + t2 < 1 && s2 > 0 && t2 > 0 puts f1 ^ f2 ? "OK" : "NG" end
こういう問題は慣れてきた。
0144 Packet Transportation
address = $<.gets.to_i.times.map do r, k, *t = $<.gets.split.map(&:to_i) [r, t] end.to_h $<.gets.to_i.times do s, d, v = $<.gets.split.map(&:to_i) queue = [[s]] catch :jump do while (now = queue.shift) and now.size <= v if now.last == d puts now.size throw :jump else address[now.last].each do |to| next if now.include?(to) queue << now + [to] end end end puts "NA" end end
幅優先探索なのだが、なんとメモリオーバー。
ダイクストラ法でやる。
class Node def initialize(t) @to = t @cost = Float::INFINITY @done = false end attr_accessor :to, :cost, :done end given = $<.gets.to_i.times.map do r, k, *t = $<.gets.split.map(&:to_i) [r, Node.new(t)] end.to_h $<.gets.to_i.times do s, d, v = $<.gets.split.map(&:to_i) nodes = Marshal.load(Marshal.dump(given)) nodes[s].cost = 0 loop do u = nil nodes.each_value do |node| next if node.done u = node if !u or node.cost < u.cost end break unless u u.done = true u.to.each do |v| if (a = u.cost + 1) < nodes[v].cost nodes[v].cost = a end end end i = nodes[d].cost + 1 puts (i <= v) ? i : "NA" end
1.15秒かかった。他の人の回答を見ると、やはりうまく幅優先探索で実装したほうが圧倒的に速い。
やってみる。
address = $<.gets.to_i.times.map do r, k, *t = $<.gets.split.map(&:to_i) [r, t] end.to_h $<.gets.to_i.times do s, d, v = $<.gets.split.map(&:to_i) queue = [s] dist = {s=>1} until !(now = queue.shift) or now == d address[now].each do |nxt| unless dist[nxt] dist[nxt] = dist[now] + 1 queue << nxt end end end ds = dist[now] puts ds && (ds <= v) ? ds : "NA" end
これだと 0.06秒。瞬殺である。
0145 Cards
decks = $<.gets.to_i.times.map {$<.gets.split.map(&:to_i)} L = decks.size memo = Array.new(L) {[]} minimum = ->(left, right) { return memo[left][right] if memo[left][right] result = if left == right 0 else (right - left).times.map do |i| decks[left][0] * decks[left + i][1] * decks[left + i + 1][0] * decks[right][1] + minimum.(left, left + i) + minimum.(left + i + 1, right) end.min end memo[left][right] = result } puts minimum.(0, L - 1)
0146 Lupin The 4th
全然思いつかない。とりあえず総当り。
n = $<.gets.to_i kuras = $<.readlines.map {|i| i.split.map(&:to_i)} min = Float::INFINITY result = nil try = ->(reached = [], w = 0, t = 0, before = nil) { return if t >= min if reached.size == n if t < min min = t result = reached end else kuras.each do |k| next if reached.include?(k[0]) before ||= k[1] l = (k[1] - before).abs v = 2000 / (70 + w.to_r) try.(reached + [k[0]], w + k[2] * 20, t + l / v, k[1]) end end } try.() puts result.join(" ")
予想通りタイムオーバー。
いつものごとく tnakao さんの回答を参考にする。なるほど、蔵間の距離はあらかじめ求めておけばよい。また、これは重要だが、出発点と残っている蔵が確定していれば、残りの順番は確定するということ(千両箱の重さに順番は関係ない)。うーん、すばらしい洞察だ。
n = io.gets.to_i kuras = io.readlines.map {|i| i.split.map(&:to_i)} kuras.each {|k| k[2] *= 20} edges = Array.new(n) {[nil] * n} n.times do |i| (i + 1...n).each {|j| edges[i][j] = edges[j][i] = (kuras[i][1] - kuras[j][1]).abs} end all = (1 << n) - 1 memo = Array.new(n) {[]} n.times {|i| memo[i][all ^ (1 << i)] = [0, [kuras[i][0]]]} try = ->(start, reached = 0, w = 0) { return memo[start][reached] if memo[start][reached] now = kuras[start] min_time = Float::INFINITY min_order = nil nr = reached | (1 << start) w0 = w + now[2] n.times do |nxt| next if (nr & (1 << nxt)).nonzero? time, order = try.(nxt, nr, w0) time += edges[start][nxt] * (70 + w0).to_r / 2000 if time < min_time min_time = time min_order = [now[0]] + order end end memo[start][reached] = [min_time, min_order] } puts (0...n).map {|i| try.(i)}.sort_by(&:first).first.last.join(" ")
その方向でやってみる。3.99秒でクリア。
0147 Fukushimaken
table = [0, 0, 0, 0, 0, 0, 14, 9, 4, 0, 0, 8, 3, 2, 0, 0, 15, 10, 15, 10, 6, 12, 7, 9, 11, 6, 23, 18, 13, 8, 3, 23, 18, 13, 8, 3, 34, 29, 24, 22, 17, 28, 23, 24, 19, 27, 34, 29, 35, 30, 28, 31, 28, 23, 24, 28, 42, 37, 32, 27, 22, 42, 37, 32, 27, 22, 53, 48, 43, 41, 36, 47, 42, 43, 38, 46, 64, 59, 54, 49, 44, 61, 56, 51, 46, 44, 72, 67, 62, 57, 52, 72, 67, 62, 57, 52, 83, 78, 73, 71] puts $<.readlines.map(&:to_i).map {|i| table[i]}
あらかじめ計算しておけばよい。table
を得るためのコードは以下。
N = 100 S = 17 in_time = (0...N).map {|i| 5 * i} numbers = (0...N).map {|i| (i % 5 == 1) ? 5 : 2} eating_time = (0...N).map {|i| 17 * (i % 2) + 3 * (i % 3) + 19} finish_time = Array.new(N, -1) seats = Array.new(S, -1) waiting = [] waiting_time = Array.new(N, -1) 0.step do |now| # 食べ終わったグループの処理 N.times do |j| next unless finish_time[j] == now seats = seats.map {|i| i == j ? -1 : i} end # 入ってきたグループの処理 come_in = in_time.index(now) waiting << come_in if come_in # 座れる場合の処理 sittable = ->(i) { index = ->(size) { j = 0 while j < S return j if seats[j, size] == [-1] * size j += 1 end false } idx = index.(numbers[i]) if idx numbers[i].times {|j| seats[idx + j] = i} true else false end } while (head = waiting.first) and sittable.(head) waiting_time[head] = now - in_time[head] waiting.shift finish_time[head] = now + eating_time[head] end break if seats.all? {|i| i < 0} end p waiting_time
0148 Candy and Class Flag
result = $<.readlines.map(&:to_i).map do |a| sprintf "3C%02d", (i = a % 39).zero? ? 39 : i end puts result
0149 Eye Test
L = 4 table = [[1.1, Float::INFINITY], [0.6, 1.1], [0.2, 0.6], [0, 0.2]] left = Array.new(L, 0) right = Array.new(L, 0) count = ->(a, counter) { table.each_with_index do |d, i| counter[i] += 1 if d[0] <= a and a < d[1] end counter } $<.readlines.map {|l| l.split.map(&:to_f)}.each do |l, r| left = count.(l, left) right = count.(r, right) end L.times do |i| puts "#{left[i]} #{right[i]}" end
何だか冗長なコードになってしまった。