AtCoder/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)
tree = Array.new(n + 1) {[]}
(n - 1).times do
  a, b = gets.split.map(&:to_i)
  tree[a] << b
  tree[b] << a
end
 
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秒。

E: ロック /var/lib/dpkg/lock-frontend が取得できませんでした - open (11: リソースが一時的に利用できません)

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

これだけでもいけると書いてあるサイトもある。

※参考
Ubuntu 18.04でlockファイル関連の不具合 | ねこめも

Windows 8.1, Ruby 2.6.3 に gtk2

Windows 8.1, Ruby 2.6.3 に gem 'glib2' が入らない

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

散歩