ある双曲線の整数解

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]

これしか見つかっていない。

AtCorder/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 はあるらしいのに…。

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ファイル関連の不具合 | ねこめも

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

動画の切り出し

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!