動画の切り出し
ffmpeg を使う。
開始5分の時点から1分間切り出す。ついでに mkv から mp4 へ変換。時間指定は「hh:mm:ss」という形式でも OK。
$ ffmpeg -ss 300 -i a.mkv -t 60 a1.mp4
「-ss」が前に来るようにする。
動画の連結はこちら。
※参考
FFmpegで素早く正確に動画をカットする自分的ベストプラクティス - Qiita
それFFmpegで出来るよ! - Qiita
Ffmpegで複数動画ファイルを無劣化で結合したり、無劣化で切り出したりする | Creazy!
CPSCO2019 Session4
A - Swimming
l, x = gets.split.map(&:to_i) n = x / l puts n.even? ? x % l : (n + 1) * l - x
B - Meeting
n, d = gets.split.map(&:to_i) table = d.times.map do gets.chomp.chars.map.with_index {|st, i| i if st == "o"}.compact end puts table.combination(2).map {|d1, d2| (d1 + d2).uniq.size}.max
C - Make a Team
def c(a) return 1 if a == 1 a * (a - 1) / 2 end n, d = gets.split.map(&:to_i) r = gets.split.map(&:to_i).sort.push(Float::INFINITY) count = 0 (n - 2).times do |i| idx = r[i + 2..-1].bsearch_index {|r0| r0 - r[i] > d} next if !idx or idx.zero? count += c(idx + 1) end puts count
rindex を使ったら TLE だったので、bsearch_index に切り替えた。
Ruby 2.6 で Gem 'chipmunk' を使う(Ubuntu)
Ubuntu 19.04 の Ruby 2.6 で Gem 'chipmunk' がインストールできない。
解決策:GitHub で修正されているものを使う。
$ git clone https://github.com/chipmunk-rb/chipmunk.git $ cd chipmunk $ rake clean compile $ gem build chipmunk.gemspec Successfully built RubyGem Name: chipmunk Version: 6.1.3.4 File: chipmunk-6.1.3.4.gem $ cd ..
Gemfile に以下を追加(参照)。
gem 'chipmunk', :path => "chipmunk"
インストール。
$ bundle install $ bundle exec pry [1] pry(main)> require 'chipmunk' => true
これで OK。
AOJ(問題集)20
AIZU ONLINE JUDGE: Programming Challenge
0190 Eleven Puzzle
素直に幅優先探索を実行して死んだので、ここを参考に解いた。「両側探索」というらしい。
start = "fff0fff" "ff123ff" "f45678f" "ff9abff" "fff0fff" result1 = {} result1[start] = 0 stack = [start] # 一方からの探索 while (nxt = stack.shift) next if result1[nxt] >= 10 doit1 = ->(idx) { [1, -1, 7, -7].each do |di| next_index = idx + di next if next_index < 0 or next_index >= 35 next if (c = nxt[next_index]) == "f" or c == "0" next_field = nxt.dup next_field[idx] = c next_field[next_index] = "0" next if result1[next_field] result1[next_field] = result1[nxt] + 1 stack << next_field end } doit1.(nxt.index("0")) doit1.(nxt.rindex("0")) end # 反対側からの探索 pat = Array.new(5) until (pat[0] = gets.to_i) == -1 pat[0] = pat[0].to_s(16).center(7, "f") 4.times {|i| pat[i + 1] = gets.split.map {|a| a.to_i.to_s(16)}.join.center(7, "f") } if (ans = result1[start = pat.join]) puts ans next end result2 = {} result2[start] = 0 stack = [start] str = "NA" f = true while (nxt = stack.shift) and f next if result2[nxt] >= 10 doit2 = ->(idx) { [1, -1, 7, -7].each do |di| next_index = idx + di next if next_index < 0 or next_index >= 35 next if (c = nxt[next_index]) == "f" or c == "0" next_field = nxt.dup next_field[idx] = c next_field[next_index] = "0" next if result2[next_field] if result1[next_field] str = (result1[next_field] + result2[nxt] + 1).to_s return false end result2[next_field] = result2[nxt] + 1 stack << next_field end true } f = doit2.(nxt.index("0")) f = doit2.(nxt.rindex("0")) if f end puts str end
0191 Baby Tree
until (given = gets.split.map(&:to_i)) == [0, 0] n, m = given g = n.times.map {gets.split.map(&:to_f)} memo = Array.new(101) {Array.new(101)} compost = ->(num, left) { return memo[num][left] if memo[num][left] memo[num][left] = if left.zero? 1.0 else n.times.map {|j| g[num][j] * compost.(j, left - 1)}.max end } printf "%.02f\n", n.times.map {|i| compost.(i, m - 1)}.max.round(2) end
アホなミスをしていた。メモ化で値が存在するときに return を忘れているという…(笑)
0192 Multistory Parking Lot
class Car num = 1 define_method(:initialize) do |waiting_time| @num = num num += 1 @time = waiting_time end attr_reader :num attr_accessor :time define_singleton_method(:clear) {num = 1} end class ParkingLot Space = Struct.new(:upper, :lower) def initialize(num) @spaces = num.times.map {|i| Space.new} end def add_car(waiting_time) idx = @spaces.index {|sp| sp.lower.nil?} if idx @spaces[idx].lower = Car.new(waiting_time) #下のスペースが空いている else return false if @spaces.all?(&:upper) #満車 #下は空いていないが満車でない場合 idxs = @spaces.map.with_index {|sp, i| i unless sp.upper}.compact idx = idxs.map do |i| diff = @spaces[i].lower.time - waiting_time diff >= 0 ? [diff, i] : nil end.compact.sort.first&.last unless idx idx = idxs.map {|i| [waiting_time - @spaces[i].lower.time, i]}.sort.first.last end @spaces[idx].upper = @spaces[idx].lower @spaces[idx].lower = Car.new(waiting_time) end true end def next @spaces.each do |sp| if sp.lower sp.lower.time -= 1 sp.upper.time -= 1 if sp.upper end end out = [] 2.times do @spaces.each do |sp| if sp.lower and sp.lower.time <= 0 out << sp.lower.num sp.lower = sp.upper sp.upper = nil end end end out end #車庫が空か def empty? @spaces.all? {|sp| sp.lower.nil?} end end until (given = gets.split.map(&:to_i)) == [0, 0] m, n = given parking_time = n.times.map {gets.to_i} pl = ParkingLot.new(m) result = [] wait = [] Car.clear t = 0 loop do result += pl.next wait << parking_time.shift if (t % 10).zero? t += 1 while (wait_time = wait.shift) unless pl.add_car(wait_time) wait.unshift(wait_time) #満車の場合 break end end break if pl.empty? end puts result.join(" ") end
だいぶ勘違いをしていた。Ruby では三人しか出来ていないですよ。
0194 Delivery Company
MaxTime = 100 Truck = Struct.new(:x, :y, :dir, :time) def get_hv(str) h, v = str.split("-") [h.bytes.first - 97, v.to_i - 1] end def signal_wait(x, y, signals, next_dir, time) signal = false movable = true signals.each do |hv, k| if x == hv[1] && y == hv[0] signal = true if (i = time / k).odd? #東西方向が青? movable = false if next_dir.odd? else movable = false if next_dir.even? end end end [movable, signal] end def under_construction?(stat, x, y, constructions) constructions.each do |hv1, hv2| return true if stat.x == hv1[1] && stat.y == hv1[0] && x == hv2[1] && y == hv2[0] return true if stat.x == hv2[1] && stat.y == hv2[0] && x == hv1[1] && y == hv1[0] end false end def add_holdup(stat, x, y, holdups) next_time = stat.time holdups.each do |hv1, hv2, d| f1 = (stat.x == hv1[1] && stat.y == hv1[0] && x == hv2[1] && y == hv2[0]) f2 = (stat.x == hv2[1] && stat.y == hv2[0] && x == hv1[1] && y == hv1[0]) next_time += d if f1 || f2 end next_time end until (mn = gets.split.map(&:to_i)) == [0, 0] d0 = gets.to_i signals = gets.to_i.times.map do hv, k = gets.chomp.split [get_hv(hv), k.to_i] end constructions = gets.to_i.times.map do hv1, hv2 = gets.chomp.split [get_hv(hv1), get_hv(hv2)] end holdups = gets.to_i.times.map do hv1, hv2, d = gets.chomp.split [get_hv(hv1), get_hv(hv2), d.to_i] end start, goal = gets.split.map {|hv| get_hv(hv)} field = Array.new(mn[0]) {Array.new(mn[1])} queue = [Truck.new(start[1], start[0], 0, 0)] field[start[0]][start[1]] = queue.first min_time = Float::INFINITY go = ->(stat, dir) { next_dir = (stat.dir + dir) % 4 dx, dy = [[1, 0], [0, -1], [-1, 0], [0, 1]][next_dir] x = stat.x + dx y = stat.y + dy return [] if x < 0 || x >= mn[1] || y < 0 || y >= mn[0] return [] if under_construction?(stat, x, y, constructions) next_time = d0 + add_holdup(stat, x, y, holdups) movable, signal = signal_wait(x, y, signals, next_dir, next_time) return [] unless movable return [] if next_time > MaxTime next_stat = Truck.new(x, y, next_dir, next_time) tmp = field[y][x] return [next_stat] if signal if tmp return [] if tmp.time <= next_time end [field[y][x] = next_stat] } while (now = queue.shift) if now.x == goal[1] && now.y == goal[0] min_time = now.time if min_time > now.time else queue += go.(now, 0) queue += go.(now, 1) queue += go.(now, -1) end end puts min_time end
10秒で時間オーバー。
0195 What is the Most Popular Shop in Tokaichi?
Shop = "ABCDE" N = Shop.length until (data = [gets.chomp]) == ["0 0"] data.concat (N - 1).times.map {gets} result = data.map.with_index {|d, i| [d.split.map(&:to_i).sum, i]}.sort.last puts "#{Shop[result[1]]} #{result[0]}" end
0196 Baseball Championship
until (n = gets.to_i).zero? data = n.times.map {gets.chomp.split} scores = data.map {|n, *r| [n, r.count("0"), r.count("1")]} .sort {|a, b| (b[1] <=> a[1]).nonzero? || a[2] <=> b[2]} puts scores.map(&:first) end
複数キーのソート。
0197 Greatest Common Divisor: Euclidean Algorithm
until (given = gets.chomp) == "0 0" x, y = given.split.map(&:to_i) x, y = y, x if x < y count = 0 until y.zero? x = x % y x, y = y, x count += 1 end puts "#{x} #{count}" end
0198 Trouble in Shinagawa's Artifacts
table = [[0, 1, 2, 3, 4, 5], [3, 1, 0, 5, 4, 2], [1, 5, 2, 3, 0, 4], [4, 0, 2, 3, 5, 1], [2, 1, 5, 0, 4, 3], [0, 2, 4, 1, 3, 5], [0, 3, 1, 4, 2, 5], [5, 1, 3, 2, 4, 0], [1, 2, 0, 5, 3, 4], [4, 3, 0, 5, 2, 1], [3, 0, 4, 1, 5, 2], [3, 5, 1, 4, 0, 2], [5, 4, 2, 3, 1, 0], [2, 5, 4, 1, 0, 3], [1, 3, 5, 0, 2, 4], [2, 0, 1, 4, 5, 3], [4, 2, 5, 0, 3, 1], [0, 4, 3, 2, 1, 5], [1, 0, 3, 2, 5, 4], [4, 5, 3, 2, 0, 1], [5, 3, 4, 1, 2, 0], [5, 2, 1, 4, 3, 0], [2, 4, 0, 5, 1, 3], [3, 4, 5, 0, 1, 2]] color_table = %w(Red Yellow Blue Magenta Green Cyan).map .with_index {|c, i| [c, i]}.to_h until (n = gets.to_i).zero? dices = n.times.map { gets.split.map {|c_name| color_table[c_name]} } pool = [] count = 0 dices.each do |color| check_f = true table.each do |t| next_dice = t.map {|idx| color[idx]} if pool.include?(next_dice) count += 1 if check_f check_f = false else pool << next_dice end end end puts count end
0199 Chairs Where Demanding People Sit
def a(seats) seats[seats.index("#")] = "A" end def b(seats, n) (n - 1).downto(0) do |i| if (i - 1 < 0 || seats[i - 1] != "A") && seats[i + 1] != "A" && seats[i] == "#" seats[i] = "B" return end end seats[seats.index("#")] = "B" end def c(seats, n) if seats.count("#") == n idx = n / 2 else n.times do |i| if seats[i] != "#" if seats[i + 1] == "#" idx = i + 1 break elsif i - 1 >= 0 && seats[i - 1] == "#" idx = i - 1 break end end end end seats[idx] = "C" end def d(seats, n) idx = 0 if seats.count("#") != n max_dist = 0 n.times do |i| d = nearest_dist(seats, i) if d > max_dist max_dist = d idx = i end end end seats[idx] = "D" end def nearest_dist(seats, i) dist = 0 dist += 1 until /[A-D]/ =~ seats[i + dist] || (i - dist >= 0 && /[A-D]/ =~ seats[i - dist]) dist end until (given = gets.split.map(&:to_i)) == [0, 0] n, m = given seats = "#" * n m.times do case gets.chomp when "A" then a(seats) when "B" then b(seats, n) when "C" then c(seats, n) when "D" then d(seats, n) end end puts seats end
AtCoder(AtCoder Beginners Selection)
AtCoder Beginners Selection - AtCoder
PracticeA - はじめてのあっとこーだー(Welcome to AtCoder)
a = gets.to_i b, c = gets.split.map(&:to_i) s = gets print "#{a + b + c} #{s}"
ABC086A - Product
a, b = gets.split.map(&:to_i) puts (a * b).odd? ? "Odd" : "Even"
ABC081A - Placing Marbles
puts gets.chomp.count("1")
ABC081B - Shift only
def calc(ary, co) return co unless ary.all?(&:even?) calc(ary.map {|i| i / 2}, co + 1) end gets given = gets.split.map(&:to_i) puts calc(given, 0)
ABC087B - Coins
table = [500, 100, 50] coins = 3.times.map {gets.to_i} x = gets.to_i memo = Array.new(4) {[]} try = ->(i, yen) { return memo[i][yen] if memo[i][yen] return 1 if yen.zero? return 0 if i >= 3 co = 0 (0..coins[i]).each do |n| yen1 = yen - table[i] * n break if yen1 < 0 co += try.(i + 1, yen1) end memo[i][yen] = co } puts try.(0, x)
ABC083B - Some Sums
n, a, b = gets.split.map(&:to_i) puts (1..n).select {|i| i.to_s.bytes.map {|b| b - 48}.inject(&:+).between?(a, b)} .inject(&:+)
ABC088B - Card Game for Two
n = io.gets.to_i cards = io.gets.split.map(&:to_i).sort diff = 0 (0...n).each do |i| if i.even? diff += cards[n - 1 - i] else diff -= cards[n - 1 - i] end end puts diff
ABC085B - Kagami Mochi
n = gets.to_i puts n.times.map {gets.to_i}.uniq.size
ABC085C - Otoshidama
n, y = gets.split.map(&:to_i) limit1 = [y / 10000, n].min (0..limit1).each do |b1| yen1 = y - 10000 * b1 limit2 = [yen1 / 5000, n - b1].min (0..limit2).each do |b2| b3 = n - b1 - b2 if yen1 == 5000 * b2 + 1000 * b3 puts "#{b1} #{b2} #{b3}" exit end end end puts "-1 -1 -1"
これで 0.216秒。
よりよい方法がよく考えたらわかった。
n, y = gets.split.map(&:to_i) limit1 = [y / 10000, n].min (0..limit1).each do |b1| x = y / 1000 - n - 9 * b1 if x >= 0 and (x % 4).zero? b2 = x / 4 b3 = n - b1 - b2 if b3 >= 0 and 10000 * b1 + 5000 * b2 + 1000 * b3 == y puts "#{b1} #{b2} #{b3}" exit end end end puts "-1 -1 -1"
これで 0.009秒。
ABC049C - 白昼夢 / Daydream
table = %w(dream dreamer erase eraser).map(&:reverse) s = gets.chomp.reverse result = "YES" until s.length.zero? catch :jump do table.each do |word| n = word.length if s[0, n] == word s = s[n..-1] throw :jump end end result = "NO" s = "" end end puts result
ABC086C - Traveling
n = gets.to_i plans = n.times.map {gets.split.map(&:to_i)} f = plans.all? do |t, x, y| d = x.abs + y.abs if t < d false else t.odd? ? d.odd? : d.even? end end puts f ? "Yes" : "No"
AOJ(問題集)19
AIZU ONLINE JUDGE: Programming Challenge
0180 Demolition of Bridges
until (given = $<.gets.split.map(&:to_i)) == [0, 0] n, m = given bridges = m.times.map {$<.gets.split.map(&:to_i)}.sort_by(&:last) city = Array.new(n, false) city[0] = true appearance = 1 total_cost = 0 while appearance < n bridges.each_index do |i| a, b, cost = bridges[i] if city[a] or city[b] if !city[a] city[a] = true appearance += 1 total_cost += cost elsif !city[b] city[b] = true appearance += 1 total_cost += cost end bridges.delete_at(i) break end end end puts total_cost end
「0072 Carden Lantern」とほぼ同じ問題(最小全域木を求める)。ここで使ったのは「プリム法」というらしい。
0181 Bookshelf
Limit = 1500000 until (given = $<.gets.split.map(&:to_i)) == [0, 0] m, n = given book = n.times.map {$<.gets.to_i} narrowest = Limit pool = [] try = ->(from, h, pool) { return if !pool.empty? and pool.last > narrowest if h > m if from == n a = pool.max narrowest = a if a < narrowest end else width = 0 (from...n).each do |i| width += book[i] try.(i + 1, h + 1, pool + [width]) end if narrowest == Limit a = pool.max narrowest = a if a < narrowest end end } try.(0, 1, []) puts narrowest end
7.73秒で時間オーバー。
until (given = $<.gets.split.map(&:to_i)) == [0, 0] m, n = given books = n.times.map {$<.gets.to_i} smallest = 1500000 m = n if n < m if m == 1 puts books.sum next end [*1..n - 1].combination(m - 1) do |sep| i = 0 shelf = [] sep.each do |j| shelf << books[i...j] i = j end shelf << books[i..-1] len = shelf.map {|a| a.sum}.max smallest = len if len < smallest end puts smallest end
10秒で時間オーバー。
他の人の回答を見る。
Limit = 1500000 until (given = $<.gets.split.map(&:to_i)) == [0, 0] m, n = given books = n.times.map {$<.gets.to_i} memo = Array.new(m + 1) {[]} shelf = ->(h, from) { return 0 if from >= n return memo[h][from] if memo[h][from] if h == 1 width = books[from...n].sum return memo[h][from] = width end narrowest = Limit width = 0 to = n - h + 1 (from..to).each do |i| width1 = shelf.(h - 1, i) wider = [width, width1].max narrowest = wider if narrowest > wider width += books[i] break if narrowest <= width end memo[h][from] = narrowest } puts shelf.(m, 0) end
0.06秒ですよ。すごいなあ。
いやこれ、2分探索の典型的な問題なのだった。
Limit = 1500000 until (given = $<.gets.split.map(&:to_i)) == [0, 0] m, n = given books = n.times.map {$<.gets.to_i} f = ->(width) { need = 1 sum = 0 books.each do |book| return false if book > width sum += book if sum > width need += 1 sum = book end end need <= m } l = 1 r = Limit while l <= r mid = l + (r - l) / 2 if !f.(mid) l = mid + 1 else r = mid - 1 end end puts l end
0.04秒で正解なのだが、バグって死んだ。「まめめも」参照。2分探索超むづかしい。
Ruby の組み込みメソッドを使ってみた。
Limit = 1500000 until (given = $<.gets.split.map(&:to_i)) == [0, 0] m, n = given books = n.times.map {$<.gets.to_i} f = ->(width) { need = 1 sum = 0 books.each do |book| return false if book > width sum += book if sum > width need += 1 sum = book end end need <= m } puts (1..Limit).bsearch {|width| f.(width)} end
0183 Black-and-White
loop do board = Array.new(3) break if (board[0] = $<.gets.chomp) == "0" board[1] = $<.gets.chomp board[2] = $<.gets.chomp check = ->(c) { gl = c * 3 return true if board.map {|b| b == gl}.any? return true if 3.times.map {|i| board.map {|b| b[i]}.join == gl }.any? return true if board[0][0] + board[1][1] + board[2][2] == gl return true if board[0][2] + board[1][1] + board[2][0] == gl false } str = case when check.("b") then "b" when check.("w") then "w" else "NA" end puts str end
0184 Tsuruga Castle
table = 6.times.map {|i| [i * 10, (i + 1) * 10 - 1]} + [[60, 120]] until (n = $<.gets.to_i).zero? count = Array.new(7, 0) n.times.map {$<.gets.to_i}.each do |age| idx = table.index {|a, b| age.between?(a, b)} count[idx] += 1 end puts count end
0185 Goldbach's Conjecture II
N = 1000000 sieve = [*0..N] 2.upto(Math.sqrt(N).to_i) do |i| next if sieve[i].zero? 2.upto(N / i) {|j| sieve[i * j] = 0} end sieve = sieve[2..-1].reject {|x| x.zero?} def prime?(n) return false if n < 2 return true if n == 2 or n == 3 return false if (n % 2).zero? or (n % 3).zero? i, step = 5, 2 guard = Math.sqrt(n).to_i while i <= guard return false if (n % i).zero? i += step step = 6 - step end true end until (n = $<.gets.to_i).zero? co = 0 i = 0 loop do a = sieve[i] break if a > n / 2 co += 1 if prime?(n - a) i += 1 end puts co end
1.49秒かかった。標準添付ライブラリの Prime クラスを使うより高速な素数判定をしている。
さらに高速に。うまくエラトステネスの篩を使えばもっと速い。
N = 1000000 sieve = Array.new(N + 1, 0) 2.upto(Math.sqrt(N).to_i) do |i| next if sieve[i].nonzero? 2.upto(N / i) {|j| sieve[i * j] = 1} end num = (2..N).select {|i| sieve[i].zero?} until (n = $<.gets.to_i).zero? co = 0 num.each do |a| b = n - a break if a > b co += 1 if sieve[b].zero? end puts co end
これで 0.26秒。
0186 Aizu Chicken
until (given = $<.gets.split.map(&:to_i)) == [0] q1, b, c1, c2, q2 = given limit = [q2, b / c1].min str = "NA" limit.downto(1) do |aizu| tori = (b - aizu * c1) / c2 if tori >= 0 and aizu + tori >= q1 str = "#{aizu} #{tori}" break end end puts str end
これ、簡単そうなのにわからなかった。ここを参考にした。
0187 Stoning Fortune
require 'matrix' def cross(x1, y1, x2, y2, x3, y3, x4, y4) a = Matrix[[x2 - x1, x3 - x4], [y2 - y1, y3 - y4]].lup.solve([x3 - x1, y3 - y1]) rescue nil return false unless a s, t = a[0], a[1] f = ((0 <= s and s <= 1) and (0 <= t and t <= 1)) f ? Vector[x1 + s * (x2 - x1), y1 + s * (y2 - y1)] : false end until (given = $<.gets.split.map(&:to_i)) == [0] * 4 x, y = [], [] x[0], y[0], x[1], y[1] = given x[2], y[2], x[3], y[3] = $<.gets.split.map(&:to_i) x[4], y[4], x[5], y[5] = $<.gets.split.map(&:to_i) p1 = cross(x[0], y[0], x[1], y[1], x[2], y[2], x[3], y[3]) p2 = cross(x[2], y[2], x[3], y[3], x[4], y[4], x[5], y[5]) p3 = cross(x[4], y[4], x[5], y[5], x[0], y[0], x[1], y[1]) str = "kyo" if p1 and p2 and p3 v1 = p2 - p1 v2 = p3 - p1 s = Rational((v1[0] * v2[1] - v1[1] * v2[0]).abs, 2) if s.nonzero? idx = nil [Float::INFINITY, 1_900_000, 1_000_000, 100_000, 0].each_cons(2).with_index do |a, i| idx = i if a[1] <= s and s < a[0] end str = %w(dai-kichi chu-kichi kichi syo-kichi)[idx] end end puts str end
つまらぬバグを取るのが大変だった。f = true and false
は false
なのだけれど、f = true
になるのか。
0188 Search
until (n = $<.gets.to_i).zero? a = n.times.map {$<.gets.to_i} k = $<.gets.to_i co = 0 f = ->(from, to) { return co if from > to mid = (from + to) / 2 co += 1 return co if a[mid] == k (a[mid] < k) ? f.(mid + 1, to) : f.(from, mid - 1) } puts f.(0, n - 1) end
2分探索はどうもよくわからない。
0189 Convenient Location
until (n = $<.gets.to_i).zero? e = n.times.map {$<.gets.split.map(&:to_i)} edges = (e.map {|a, b, c| [[a, b], c]} + e.map {|a, b, c| [[b, a], c]}).to_h h = Hash.new([]) edges.keys.each {|a, b| h[a] += [b]} try = ->(start) { shortest = Hash.new(Float::INFINITY) done = h.keys.map {|k| [k, false]}.to_h shortest[start] = 0 loop do u = nil h.each_key do |node| next if done[node] u = node if !u or shortest[node] < shortest[u] end break unless u done[u] = true h[u].each do |v| if (a = shortest[u] + edges[[u, v]]) < shortest[v] shortest[v] = a end end end shortest.values.sum } puts h.keys.map {|k| [try.(k), k]}.sort.first.reverse.join(" ") end
ダイクストラ法。
AOJ(ALDS)その2
AIZU ONLINE JUDGE: Programming Challenge
ALDS1_9_A Complete Binary Tree
#完全二分木 $<.gets given = [nil] + $<.gets.split.map(&:to_i) a = nil given.drop(1).each_with_index do |key, i| j = i + 1 str = "node #{j}: key = #{key}, " str += "parent key = #{a}, " if (a = given[j / 2]) str += "left key = #{a}, " if (a = given[j * 2]) str += "right key = #{a}, " if (a = given[j * 2 + 1]) puts str end
ALDS1_9_B Maximum Heap
#最大ヒープ h = $<.gets.to_i given = [nil] + $<.gets.split.map(&:to_i) max_heapify = ->(i) { l, r = i * 2, i * 2 + 1 largest = (l <= h and given[l] > given[i]) ? l : i largest = r if r <= h and given[r] > given[largest] unless largest == i given[i], given[largest] = given[largest], given[i] max_heapify.(largest) end } (h / 2).downto(1) {|i| max_heapify.(i)} puts given.drop(1).map {|i| " #{i}"}.join
ALDS1_9_C Priority Queue
#優先度付きキュー class MaxHeap def initialize @heap = [nil] @size = 0 end def insert(key) @heap << key @size += 1 up_heap(@size / 2) end def up_heap(i) return if i.zero? l, r = i * 2, i * 2 + 1 largest = (l <= @size and @heap[l] > @heap[i]) ? l : i largest = r if r <= @size and @heap[r] > @heap[largest] unless largest == i @heap[i], @heap[largest] = @heap[largest], @heap[i] up_heap(i / 2) end end def remove_root a = @heap[1] @heap[1] = @heap.pop @size -= 1 down_heap(1) a end def down_heap(i) return if i > @size l, r = i * 2, i * 2 + 1 largest = (l <= @size and @heap[l] > @heap[i]) ? l : i largest = r if r <= @size and @heap[r] > @heap[largest] unless largest == i @heap[i], @heap[largest] = @heap[largest], @heap[i] down_heap(largest) end end end h = MaxHeap.new $<.readlines.map {|l| l.chomp.split}.each do |command| case command[0] when "insert" then h.insert(command[1].to_i) when "extract" then puts h.remove_root when "end" then break else raise "error" end end
ALDS1_10_A Fibonacci Number
#フィボナッチ数列 fib = Enumerator.new do |y| a, b = 1, 1 loop do y << a a, b = b, a + b end end puts fib.take($<.gets.to_i + 1).last
ALDS1_10_B: Matrix Chain Multiplication
連鎖行列積問題(Matrix-Chain Multiplication problem)。
INF = (1 << 31) - 1 n = gets.to_i ms = n.times.map {gets.split.map(&:to_i)} dp = Array.new(n + 1) {Array.new(n + 1, 0)} dim = [ms[0][0]] + ms.map(&:last) 2.upto(n) do |l| 1.upto(n - l + 1) do |i| j = i + l - 1 dp[i][j] = INF i.upto(j - 1) do |k| tmp = dp[i][k] + dp[j][k] + dp[k + 1][j] + dim[i - 1] * dim[k] * dim[j] dp[i][j] = [dp[i][j], tmp].min end end end puts dp[1][n]
ここのパクリ。むずかしい。
※参考
連鎖行列積問題 - Qiita
動的計画法4 連鎖行列積 - Daily Tech Blog
連鎖行列積問題 : がぶ飲みミルク珈琲
※追記
わたしがパクったコードは、じつは『アルゴリズムイントロダクション 第3版 第2巻: 高度な設計と解析手法・高度なデータ構造・グラフアルゴリズム (世界標準MIT教科書)』のパクリだったことがわかった。
Ruby/Opal サンプル
コード。Ruby 部分のみ。
require 'native' d = Native(`document`) area = d.getElementById("text") button = d.getElementById("start") interval = Native(`window.setInterval`) z, d = zd = ["ズン", "ドコ"] st = "" line = [] f = false zundoko = ->{ return if f line << zd[rand(2)] line = line.last(5) st += line.last area.textContent = st if line == [z, z, z, z, d] area.textContent = st + " キ・ヨ・シ!" f = true end } start = ->{interval.call(zundoko, 1000)} button.addEventListener("click", start)
AOJ(問題集)18
AIZU ONLINE JUDGE: Programming Challenge
0170 Lunch
until (n = $<.gets.to_i).zero? data = n.times.map {$<.gets.split}.map {|a, *b| [a] + b.map(&:to_i)} selected = [] all = [*0...n] solve = ->(left, order) { return if data[order.last][2] < (all - order).map {|i| data[i][1]}.sum if left.empty? selected << order else left.each {|i| solve.(left - [i], order + [i])} end } all.each {|i| solve.(all - [i], [i])} result = selected.sort_by do |order| w = order.map {|i| data[i][1]} [*1..order.size].zip(w).map {|a, b| a * b}.sum / w.sum.to_f end.first puts result.map {|i| data[i][0]} end
3.74秒。バックトラック法。もっといい方法があるらしい。検索してみても C++ とかの奴らは全然参考にならない。
また tnakao さんの回答を見る。驚愕。とりあえず(自己流に書き直して)コードを掲載してみる。
until (n = io.gets.to_i).zero? data = n.times.map {io.gets.split}.map {|a, *b| [a] + b.map(&:to_i)} wsum0 = data.map {|a| a[1]}.sum memo = [] check = ->(bits, wsum) { return memo[bits] if memo[bits] return [0, []] if bits.zero? min_gw = Float::INFINITY min_ids = [] n.times do |i| b = 1 << i if (bits & b).nonzero? name, w, s = data[i] if s >= wsum - w gw0, ids0 = check.(bits & ~b, wsum - w) gw = gw0 + wsum if gw < min_gw min_gw = gw min_ids = [i] + ids0 end end end end memo[bits] = [min_gw, min_ids] } gw, ids = check.((1 << n) - 1, wsum0) puts ids.map {|i| data[i][0]} end
なるほど、最後からやっていくわけか…。(n - 1) 個の場合の min を求めておいて、n 個の min を出す。動的計画法だな。これは思いつかなかった。すごい。
0171 Dice Puzzle
table = [[1, 2, 3, 4, 5, 6], [4, 2, 1, 6, 5, 3], [2, 6, 3, 4, 1, 5], [5, 1, 3, 4, 6, 2], [3, 2, 6, 1, 5, 4], [1, 3, 5, 2, 4, 6], [1, 4, 2, 5, 3, 6], [6, 2, 4, 3, 5, 1], [2, 3, 1, 6, 4, 5], [5, 4, 1, 6, 3, 2], [4, 1, 5, 2, 6, 3], [4, 6, 2, 5, 1, 3], [6, 5, 3, 4, 2, 1], [3, 6, 5, 2, 1, 4], [2, 4, 6, 1, 3, 5], [3, 1, 2, 5, 6, 4], [5, 3, 6, 1, 4, 2], [1, 5, 4, 3, 2, 6], [2, 1, 4, 3, 6, 5], [5, 6, 4, 3, 1, 2], [6, 4, 5, 2, 3, 1], [6, 3, 2, 5, 4, 1], [3, 5, 1, 6, 2, 4], [4, 5, 6, 1, 2, 3]] Table = table.map {|i| i.map(&:pred)} Dirs = [[2, 4, 5], [1, 2, 5], [3, 4, 5], [1, 3, 5], [2, 4, 0], [1, 2, 0], [3, 4, 0], [1, 3, 0]] Touch = [[2, 1, 4], [0, 3, 5], [0, 3, 6], [2, 1, 7], [6, 5, 0], [4, 7, 1], [4, 7, 2], [6, 5, 3]] def each_position(dice, d_num) Dirs[d_num].each do |fix_po| Table.select {|od| od[fix_po] == fix_po}.each do |order| yield order.map {|i| dice[i]} end end end until (s = $<.gets.chomp) == "0" dices = [s.chars] 7.times {dices << $<.gets.chomp.chars} ok = false try = ->(cube, memo, d_num) { if d_num == 8 ok = true else ([*0..7] - cube).each do |nxt| each_position(dices[nxt], d_num) do |d1| f = Dirs[d_num].map.with_index do |dir, i| d2 = memo[Touch[d_num][i]] next unless d2 d1[dir] == d2[5 - dir].swapcase end.compact.all? try.(cube + [nxt], memo + [d1], d_num + 1) if f end end end } Table.each {|order| try.([0], [order.map {|j| dices[0][j]}], 1)} puts ok ? "YES" : "NO" end
42秒で時間オーバー。
0173 Haunted House
9.times do name, a, b = $<.gets.split a, b = a.to_i, b.to_i puts "#{name} #{a + b} #{200 * a + 300 * b}" end
0174 Badminton
until (rec = $<.gets.chomp) == "0" record = rec.chars.drop(1) a = b = 0 loop do (record.shift == "A") ? a += 1 : b += 1 if record.empty? (a > b) ? a += 1 : b += 1 break end end puts "#{a} #{b}" end
0176 What Color?
table = %w(black blue lime aqua red fuchsia yellow white) until (rgb = $<.gets.chomp) == "0" color = rgb[1..-1].chars.each_slice(2).map {|a| a.join.to_i(16)} idx = [0, 0xff].repeated_permutation(3).map.with_index do |tc, i| [3.times.map {|i| (tc[i] - color[i]) ** 2}.sum, i] end.sort.first.last puts table[idx] end
ちょっと Ruby らしく圧縮しすぎて却ってわかりにくいかも。
0177 Distance Between Two Cities
require 'matrix' include Math R = 6378.1 until (given = $<.gets.split.map(&:to_f)) == [-1] * 4 a, b, c, d = given.map {|i| i / 180 * PI} rot = ->(θ, n) { vx = [cos(θ) + n[0] * n[0] * (1 - cos(θ)), n[0] * n[1] * (1 - cos(θ)) - n[2] * sin(θ), n[2] * n[0] * (1 - cos(θ)) + n[1] * sin(θ)] vy = [n[0] * n[1] * (1 - cos(θ)) + n[2] * sin(θ), cos(θ) + n[1] * n[1] * (1 - cos(θ)), n[1] * n[2] * (1 - cos(θ)) - n[0] * sin(θ)] vz = [n[2] * n[0] * (1 - cos(θ)) - n[1] * sin(θ), n[1] * n[2] * (1 - cos(θ)) + n[0] * sin(θ), cos(θ) + n[2] * n[2] * (1 - cos(θ))] Matrix[vx, vy, vz] } calc = ->(θ, φ) { po = Vector[1, 0, 0] po = rot.(θ, [0, 0, 1]) * po n = po.cross(Vector[0, 0, 1]) rot.(φ, n) * po } x1 = calc.(b, a) x2 = calc.(d, c) c = (x1 + x2) / 2 θ = atan2((x1 - c).norm, c.norm) * 2 puts (R * θ).round end
Ruby 便利だ…。
0178 TETORIS
テトリス。
W = 5 until (n = $<.gets.to_i).zero? field = [] n.times do d, p, q = $<.gets.split.map(&:to_i) if d == 1 block = ((1 << p) - 1) << W + 1 - p - q if field.empty? field = [block] else i = field.size - 1 while (field[i] & block).zero? i -= 1 break if i < 0 end i += 1 field[i] ||= 0 field[i] |= block end else block = 1 << W - q if field.empty? p.times {field.push(block)} else i = field.size - 1 while (field[i] & block).zero? i -= 1 break if i < 0 end p.times do i += 1 field[i] ||= 0 field[i] |= block end end end field.delete_at(i) while (i = field.index(31)) end puts field.map {|a| a.to_s(2)}.join.count("1") end
圧倒的に速いですぞ、これは。
0179 Mysterious Worm
color = %w(r g b) until (worm = io.gets.chomp) == "0" queue = [[worm, 0]] appear = [worm] catch :jump do while (worm = queue.shift) worm, t = worm.first.chars, worm.last if color.map {|c| worm.all? {|a| a == c}}.any? puts t throw :jump else (worm.size - 1).times do |i| tmp = worm.dup next if tmp[i] == tmp[i + 1] c = (color - [tmp[i], tmp[i + 1]]).first tmp[i] = c tmp[i + 1] = c tmp = tmp.join next if appear.include?(tmp) appear << tmp queue << [tmp, t + 1] end end end puts "NA" end end
幅優先探索なのだけれど、42秒で時間オーバー。
他の人の回答を見る。
table = {"rg"=>"bb", "gr"=>"bb", "gb"=>"rr", "bg"=>"rr", "br"=>"gg", "rb"=>"gg"} neighbours = ->(worm) { len = worm.length result = [] c0 = worm[0] (1...len).each do |i| c = worm[i] pair = c0 + c if table[pair] worm0 = worm.dup worm0[i - 1, 2] = table[pair] result << worm0 end c0 = c end result } until (worm = $<.gets.strip) == "0" queue = [worm] dists = {worm => 0} dist = "NA" n = worm.length goal = ["r" * n, "g" * n, "b" * n] while (worm = queue.shift) if goal.include?(worm) dist = dists[worm] break end neighbours.(worm).each do |worm0| unless dists[worm0] dists[worm0] = dists[worm] + 1 queue << worm0 end end end puts dist end
これだと 0.85秒でクリア。考え方は自分のとそんなにちがわない。何がちがうのかな。シンプルさがちがうのだな。
これを参考に、自分のを書き直してみる。
table = {"rg"=>"bb", "gr"=>"bb", "gb"=>"rr", "bg"=>"rr", "br"=>"gg", "rb"=>"gg"} until (worm = $<.gets.chomp) == "0" queue = [worm] dist = {worm => 0} n = worm.size catch :jump do while (worm = queue.shift) goal = ["r" * n, "g" * n, "b" * n] if goal.include?(worm) puts dist[worm] throw :jump else (n - 1).times do |i| tmp = worm.dup pair = worm[i, 2] next unless table[pair] tmp[i, 2] = table[pair] next if dist[tmp] dist[tmp] = dist[worm] + 1 queue << tmp end end end puts "NA" end end
これだと 0.77秒でクリア。うーん、勉強になるなあ。