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 はスタックオーバーフローになっていたみたいだ。
ある双曲線の整数解
36*x^2-4*x-71*y^2+8=0 の整数解の導出。
Ruby でできるだけ解いてみる。
solve.rb
dir = [[1, 0], [0, 1], [-1, 0], [0, -1]] x = y = 0 step = 1 f = ->{p [x, y] if 36 * x ** 2 - 4 * x - 71 * y ** 2 + 8 == 0} add = ->(i) { dx, dy = dir[i] x += dx y += dy } loop do 2.times do |j| step.times do f.() add.(j * 2) end step.times do f.() add.(j * 2 + 1) end step += 1 end end
実行。
$ ruby solve.rb [-1629, 1160] [-1629, -1160]
これしか見つかっていない。
AtCoder/ABC137
A - +-x
a, b = gets.split.map(&:to_i)
puts [a + b, a - b, a * b].max
B - One Clue
k, x = gets.split.map(&:to_i) puts [*x - k + 1..x + k - 1].join(" ")
C - Green Bin
words = gets.to_i.times.map {gets.chomp.chars.sort.join}.group_by(&:itself)
ans = words.inject(0) do |acc, (_, ary)|
l = ary.size
l == 1 ? acc : acc + l * (l - 1) / 2
end
puts ans
これは他の人の回答を見た。
あとで自分で考えたもの。
table = {}
count = 0
gets.to_i.times.map {gets.chomp.chars.sort}.each do |word|
if table[word]
table[word] += 1
count += table[word]
else
table[word] = 0
end
end
puts count
D - Summer Vacation
class MaxHeap def initialize @heap = [nil] @size = 0 end def insert(key) @heap << key @size += 1 up_heap(@size / 2) end def up_heap(i) return if i.zero? l, r = i * 2, i * 2 + 1 largest = (l <= @size and @heap[l] > @heap[i]) ? l : i largest = r if r <= @size and @heap[r] > @heap[largest] unless largest == i @heap[i], @heap[largest] = @heap[largest], @heap[i] up_heap(i / 2) end end def remove_root a = @heap[1] b = @heap.pop @size -= 1 return b if @heap.size == 1 @heap[1] = b down_heap(1) a end def down_heap(i) return if i > @size l, r = i * 2, i * 2 + 1 largest = (l <= @size and @heap[l] > @heap[i]) ? l : i largest = r if r <= @size and @heap[r] > @heap[largest] unless largest == i @heap[i], @heap[largest] = @heap[largest], @heap[i] down_heap(largest) end end def size @heap.size - 1 end end n, m = gets.split.map(&:to_i) given = Hash.new {|h, v| h[v] = []} n.times.each do a, b = gets.split.map(&:to_i) given[a] << b end mh = MaxHeap.new sum = 0 (1..m).each do |left_day| given[left_day].each {|reward| mh.insert(reward)} sum += mh.remove_root unless mh.size.zero? end puts sum
これを参考にして、優先度付きキューを実装して頑張った。優先度付きキューは以前に自分で実装したのだけれど、バグがあったりして直した。きちんと使える実装（参照）が手に入ってうれしいけれど、そもそも Ruby では標準添付ライブラリにこれがないのだよなあ。Python はあるらしいのに…。
E - Coins Respawn
全然わからないのでいろいろ参考にする。これが参考になりまくり。パクった。
INF = 1 << 60 n, m ,p = gets.split.map(&:to_i) g = [] to = Array.new(n + 1) {[]} ot = Array.new(n + 1) {[]} m.times do a, b, c = gets.split.map(&:to_i) g << [a, b, -(c - p)] to[a] << b ot[b] << a end toflag = [0] * (n + 1) toflag[1] = 1 iki = ->(v) { to[v].each do |u| if toflag[u].zero? toflag[u] = 1 iki.(u) end end } iki.(1) otflag = [0] * (n + 1) otflag[n] = 1 kaeri = ->(v) { ot[v].each do |u| if otflag[u].zero? otflag[u] = 1 kaeri.(u) end end } kaeri.(n) cand = toflag.zip(otflag).map {|a, b| a * b} max_count = cand.count(1) g.select! {|a, b, _| cand[a] == 1 && cand[b] == 1} bellman_ford = ->{ inf = INF d = Array.new(n + 1, inf) d[1] = 0 max_count.times do update = false g.each do |v, u, cost| if d[v] != inf && d[u] > (a = d[v] + cost) d[u] = a update = true end end return -d[n] unless update end inf } ans = bellman_ford.() ans = (ans == INF) ? -1 : [ans, 0].max puts ans
なんと、Float::INFINITY を 1 << 60 に直したら TLE が解消された。ははあ、なるほど。
AtCorder/ABC（その1）
ABC001
A - 積雪深差
puts gets.to_i - gets.to_i
B - 視程の通報
ans = case (m = gets.to_i) when 0...100 then 0 when 100..5000 then m / 100 when 6000..30000 then m / 1000 + 50 when 35000..70000 then (m / 1000 - 30) / 5 + 80 else 89 end puts sprintf "%02d", ans
C - 風力観測
Houi = %W(NNE NE ENE E ESE SE SSE S SSW SW WSW W WNW NW NNW) Fuuryoku_table = [[0.0, 0.2], [0.3, 1.5], [1.6, 3.3], [3.4, 5.4], [5.5, 7.9], [8.0, 10.7], [10.8, 13.8], [13.9, 17.1], [17.2, 20.7], [20.8, 24.4], [24.5, 28.4], [28.5, 32.6]] deg, dis = gets.split.map(&:to_i) kazamuki = "N" 112.5.step(3265.5, 225).with_index do |d, i| kazamuki = Houi[i] if d <= deg && deg < d + 225 end fuusoku = (dis / 60.0).round(1) fuuryoku = 12 Fuuryoku_table.each_with_index do |f, i| fuuryoku = i if fuusoku.between?(f.first, f.last) end kazamuki = "C" if fuuryoku.zero? puts "#{kazamuki} #{fuuryoku}"
D - 感雨時刻の整理
memo = gets.to_i.times.map {gets.split("-").map(&:to_i)}
modified = memo.map do |t0|
t0.map.with_index do |t, i|
m = (t / 100) * 60 + t % 100
m += 4 if i > 0
m = (m / 5) * 5
(m / 60) * 100 + m % 60
end
end.sort
be, af = modified.shift
modified.each do |s, e|
if s.between?(be, af)
af = e if e > af
else
puts sprintf "%04d-%04d", be, af
be, af = s, e
end
end
puts sprintf "%04d-%04d", be, af
5分単位の時刻に丸めるのが上手くいっていなかった。きちんと分に直してやらないといけないのね。
別解。
Day = 60 * 24 work = Array.new(Day + 1, 0) gets.to_i.times.map {gets.split("-").map(&:to_i)}.each do |t0| t0.each_with_index do |t, i| m = (t / 100) * 60 + t % 100 m += 4 if i > 0 m = (m / 5) * 5 work[m] += i.zero? ? 1 : -1 end end Day.times {|i| work[i + 1] += work[i]} be = nil (Day + 1).times do |t| if !be && work[t] > 0 be = (t / 60) * 100 + t % 60 elsif be && work[t] < 1 af = (t / 60) * 100 + t % 60 puts sprintf "%04d-%04d", be, af be = nil end end
いもす法。
ABC002
A - 正直者
a, b = gets.split.map(&:to_i)
puts a > b ? a : b
あるいは
puts gets.split.map(&:to_i).max
B - 罠
puts (gets.chomp.chars - %W(a i u e o)).join
C - 直訴
xa, ya, xb, yb, xc, yc = gets.split.map(&:to_i) puts ((xa - xc) * (yb - yc) - (xb - xc) * (ya - yc)).abs / 2.0
D - 派閥
n, m = gets.split.map(&:to_i) relations = Hash.new {|h, k| h[k] = [k]} m.times do x, y = gets.split.map(&:to_i) relations[x] << y relations[y] << x end n.downto(1) do |i| [*1..n].combination(i) do |persons| if persons.all? {|p| persons & relations[p] == persons} puts i exit end end end
最大クリーク問題だってさ。最大で12人しかいないので、総当りで解いている。
ABC003
A - AtCoder社の給料
n = gets.to_i puts (1..n).inject(0) {|acc, i| acc + 10000 * i * Rational(1, n)}.to_i
AOJ（問題集）21
0200 Traveling Alone: One-way Ticket of Youth
until (given = gets.split.map(&:to_i)) == [0, 0] n, m = given edge = Array.new(m) {[]} h = Array.new(m) {[]} n.times do a, b, cost, time = gets.split.map(&:to_i) a -= 1 b -= 1 edge[a][b] = edge[b][a] = [cost, time] h[a] << b h[b] << a end gets.to_i.times do p, q, r = gets.split.map(&:to_i) p -= 1 q -= 1 shortest = Array.new(m, Float::INFINITY) done = m.times.map(&:itself) shortest[p] = 0 until done.empty? u = done.min {|a, b| shortest[a] <=> shortest[b]} done.delete(u) h[u].each do |v| if (a = shortest[u] + edge[u][v][r]) < shortest[v] shortest[v] = a end end end puts shortest[q] end end
ダイクストラ法なのだが、他の人の回答を見て徹底的に高速化する。これで 3.30秒。
0201 Wrought Gold Master
until (n = gets.to_i).zero? costs = n.times.map { gets.split.tap {|a| a[1] = a[1].to_i} }.to_h m = gets.to_i recipe = Hash.new {|hash, key| hash[key] = []} m.times do given = gets.split recipe[given[0]] += given[2..-1] end goal = gets.chomp try = ->(parent) { r = recipe[parent] c = costs[parent] if r.empty? c else made = r.map {|child| try.(child)}.sum [made, c].min end } puts try.(goal) end
0202 At Boss's Expense
require "prime" until (given = io.gets.split.map(&:to_i)) == [0, 0] dishes = given[0].times.map {io.gets.to_i} result = 0 dp = Array.new(given[1] + 1, false) dp[0] = true (1..given[1]).each do |i| dishes.each do |price| if i >= price && dp[i - price] dp[i] = true break end end result = i if dp[i] && i.prime? end puts result.zero? ? "NA" : result end
時間オーバー。これは Ruby ではかなり無理っぽい。出来ている人は一人しかいない。
0203 A New Plan of Aizu Ski Resort
loop do w, h = gets.split.map(&:to_i) break if w + h == 0 field = h.times.map {gets.split.map(&:to_i)} dp = Array.new(h) {Array.new(w, 0)} w.times {|x| dp[h - 1][x] = 1 if field[h - 1][x] != 1} (h - 2).downto(0) do |y| w.times do |x| case field[y][x] when 2 if y + 2 == h dp[y][x] = 1 else dp[y][x] = dp[y + 2][x] end when 0 s = 0 [-1, 0, 1].each do |dx| x1 = x + dx next if x1 < 0 || x1 == w next if dx.nonzero? && field[y + 1][x1] == 2 s += dp[y + 1][x1] end dp[y][x] = s end end end puts dp[0].sum end
0204 UFO Shooting Down Operation
class Ufo def initialize(x, y, r, v) @dist = Math.sqrt(x ** 2 + y ** 2) @x = x @y = y @r = r @v = v @ex = x / @dist @ey = y / @dist @vx = -v * @ex @vy = -v * @ey end attr_reader :x, :y, :r, :dist, :ex, :ey def move @dist -= @v @x += @vx @y += @vy end end loop do radius, n = gets.split.map(&:to_i) break if (radius + n).zero? ufos = n.times.map {Ufo.new(*gets.split.map(&:to_i))} count = 0 loop do ufos.each(&:move) ufos.sort_by! {|u| u.dist} ufos1 = ufos.select {|u| u.dist <= radius} count += ufos1.size ufos -= ufos1 break if ufos.size.zero? min = ufos.shift ufos = ufos.reject do |u| r = (min.y * u.x - min.x * u.y).abs / min.dist r < u.r && u.dist * (min.ex * u.ex + min.ey * u.ey) + Math.sqrt(u.r ** 2 - r ** 2) > radius end break if ufos.size.zero? end puts count end
これむずかしすぎでしょう。検索して初めてわかった。
0205 Rock, Paper, Scissors
until (a = gets.to_i).zero? given = [a] + 4.times.map {gets.to_i} hands = given.uniq if hands.size == 3 || hands.size == 1 result = [3] * 5 else point = (hands[0] - hands[1]) % 3 == 2 ? 1 : 2 result = given.map do |hand| hand == hands[0] ? point : 3 - point end end puts result end
突然簡単に。
0206 Next Trip
until (l = gets.to_i).zero? data = 12.times.map {gets.split.map(&:to_i)} month_number = "NA" acc = 0 data.each_with_index do |mn, i| acc += mn[0] - mn[1] if acc >= l month_number = i + 1 break end end puts month_number end
簡単。
0207 Block
Position = Struct.new(:x, :y) loop do w, h = gets.split.map(&:to_i) break if (w + h).zero? field = Array.new(h + 1) {Array.new(w + 1, 0)} xs, ys = gets.split.map(&:to_i) xg, yg = gets.split.map(&:to_i) start = Position.new(xs, ys) gets.to_i.times do color, direction, x, y = gets.split.map(&:to_i) width, height = direction.zero? ? [4, 2] : [2, 4] height.times do |h1| width.times {|w1| field[y + h1][x + w1] = color} end end start_color = field[ys][xs] field[ys][xs] = 100 stack = [start] result = "NG" while (po = stack.shift) if po.x == xg && po.y == yg result = "OK" break else [[1, 0], [0, -1], [-1, 0], [0, 1]].each do |dx, dy| next_x, next_y = po.x + dx, po.y + dy next if next_x <= 0 || next_x > w || next_y <= 0 || next_y > h if field[next_y][next_x] == start_color stack << Position.new(next_x, next_y) field[next_y][next_x] = 100 end end end end puts result end
幅優先探索。簡単。
0208 Room Numbers of a Hospital
Table = [0, 1, 2, 3, 3, 4 ,4, 5, 6, 7] def func(num) num1 = num.to_s.chars result = 0 loop do top = num1.shift.to_i digits = num1.size result += Table[top] * 8 ** digits break if digits.zero? end result end until (num = gets.to_i).zero? puts (1..9358757000).bsearch {|i| num <= func(i)} end
何かダメ。検索してみる。
Table = [0, 1, 2, 3, 5, 7, 8, 9] def f(n) f(n / 8) if n >= 8 print Table[n % 8] end until (num = gets.to_i).zero? f(num) puts end
世の中にはかしこい人がいますな。
0209 Scene in a Picture
loop do n, m = gets.split.map(&:to_i) break if (n + m).zero? scene = n.times.map {gets.split.map(&:to_i)} picture = m.times.map {gets.split.map(&:to_i)} pictures = [] 4.times do pictures << picture picture = picture.reverse.transpose #右回転 end check = ->{ result = [] (0..n - m).each do |y| (0..n - m).each do |x| pictures.each do |pic| catch :jump { nx = ny = nil m.times do |dy| m.times do |dx| next if pic[dy][dx] == -1 nx, ny = x + dx, y + dy unless nx throw :jump if pic[dy][dx] != scene[y + dy][x + dx] end end result << [nx + 1, ny + 1] } end end return result unless result.empty? end "NA" } result = check.() if result != "NA" result = result.sort! {|a, b| (a[1] <=> b[1]).nonzero? || a[0] <=> b[0]}[0].join(" ") end puts result end
凡庸なコード。でも Ruby では三人しか出来ていないね。
E: ロック /var/lib/dpkg/lock-frontend が取得できませんでした - open (11: リソースが一時的に利用できません)
追記
ここへいらっしゃった方は、たぶん unattended-upgrades のせいで apt が使えないのだと思います。以下を見ることをお勧めします。
marginalia.hatenablog.com
Ubuntu で apt を使おうとしたら以下が出る。
E: ロック /var/lib/dpkg/lock-frontend が取得できませんでした - open (11: リソースが一時的に利用できません) E: Unable to acquire the dpkg frontend lock (/var/lib/dpkg/lock-frontend), is another process using it?
対策
$ sudo rm /var/lib/apt/lists/lock $ sudo rm /var/lib/dpkg/lock $ sudo rm /var/lib/dpkg/lock-frontend
これでダメなら
$ sudo apt autoremove
これだけでもいけると書いてあるサイトもある。
追記
上の原因が unattended-upgrades によるものなら、以下を試した方がよい。
Ubuntu で unattended-upgrades を無効にする - Marginalia
Ruby 2.6 と RubyInstaller2
ridk use というコマンドが使える。
C:\Users\知生\Documents\code\Ruby>ridk use 1 - C:/Ruby25 ruby 2.5.5p157 (2019-03-15 revision 67260) [i386-mingw32] 2 - C:/Ruby25-x64 ruby 2.5.5p157 (2019-03-15 revision 67260) [x64-mingw32] 3 - C:/Ruby26 ruby 2.6.3p62 (2019-04-16 revision 67580) [i386-mingw32] 4 - C:/Ruby26-x64 ruby 2.6.3p62 (2019-04-16 revision 67580) [x64-mingw32] Select ruby version to enable: 3 Disable C:/Ruby25 Disable C:/Ruby25 Disable C:/Ruby26 Disable C:/Ruby26-x64 Enable C:/Ruby26 C:\Users\知生\Documents\code\Ruby>ruby -v ruby 2.6.3p62 (2019-04-16 revision 67580) [i386-mingw32]
※参考
WindowsにおけるRubyやRailsの環境構築方法をいろいろ調べてみた（2017年3月版） - Qiita
