rbenv でバージョンを上げたときの注意（Ruby）

Gem が一切インストールされていないことになるので、該当ディレクトリで

$ rbenv exec gem install bundler
$ bundle install

を実行。全 Gem が再インストールされる。

Linux でスワップが有効にならない

Linux でスワップ領域をちゃんと取ったのに、スワップが有効にならない場合があります。ここでコマンドの swapon で
$ swapon /dev/sda2
などとするとスワップ領域を有効にできます。

ただし、これではまた起動時にスワップ領域が無効のままになることがあります。これは /etc/fstab に登録がされていないためです。なので /etc/fstab の末尾に

/dev/sda2 swap swap defaults

などを追加してみて下さい。これで再起動すると常にスワップ領域が有効になっている筈です。

※参考
びぎねっと - はじめる人のびぎねっと。

.conkyrc 設定メモ

基本的にここの設定を使わせてもらいました。ありがとうございます！

コンフィグ設定と変数設定。
https://github.com/brndnmtthws/conky/wiki/Configuration-Settings
https://github.com/brndnmtthws/conky/wiki/Configuration-Variables

conky.config = {
  use_spacer = 'left',
  pad_percents = 3,
  background = true,
  double_buffer = true,
  font = 'DejaVu Sans Mono:size=10',
  use_xft = true,
  alignment = 'top_right',
  gap_x = 10,
  gap_y = 40,
  own_window_argb_visual = true,
  own_window_argb_value = 100,
  own_window_type = 'desktop',
  own_window = true,
  update_interval = 5.0,
}

conky.text = [[
${color orange}Hostname: ${color}${nodename}
${color orange}Kernel:   ${color}${sysname} ${kernel} on ${machine}
${color orange}Uptime:   ${color}${uptime}
${hr}
${color orange}CPU:${color} ${freq_g} GHz
${color orange}1:${color} ${cpu cpu1}% ${cpubar cpu1}
${color orange}2:${color} ${cpu cpu2}% ${cpubar cpu2}
${color orange}3:${color} ${cpu cpu3}% ${cpubar cpu3}
${color orange}4:${color} ${cpu cpu4}% ${cpubar cpu4}
${cpugraph}
${color orange}Name               PID    CPU%   MEM%
${color lightgrey} ${top name 1} ${top pid 1} ${top cpu 1} ${top mem 1}
${color lightgrey} ${top name 2} ${top pid 2} ${top cpu 2} ${top mem 2}
${color lightgrey} ${top name 3} ${top pid 3} ${top cpu 3} ${top mem 3}
${color lightgrey} ${top name 4} ${top pid 4} ${top cpu 4} ${top mem 4}
${color orange}Load average: ${color}${loadavg}
${color orange}Processes: ${color}${processes} 
${color orange}Running:${color} ${running_processes}
${hr}
${color orange}RAM:  ${color}${mem}/${memmax}
${memperc}% ${membar 4}
${color orange}Swap: ${color}${swap}/${swapmax}
${swapperc}% ${swapbar 4}
${memgraph}
${hr}
${color orange} ${color}${fs_used /}/${fs_size /} ${fs_bar 6 /}
${hr}
${color orange}IP:   ${color}${addr wlp3s0}
${color orange}Up:   ${color}${upspeed wlp3s0}
${color orange}Down: ${color}${downspeed wlp3s0}
]]

　
こんな感じ。

Linux の Shutter の「編集」ができない

Linux のスクリーンショットを撮るソフトに Shutter というものがありますが、Linux Mint 18.3 で使ってみようとしたところ、「編集」の機能が使えなかったので調べてみました。

How To Fix Disabled Edit Option In Shutter in Ubuntu 18.04 & Mint 19
基本的にこのサイトに書いてあります。一応ここでも記しておきましょう。

Shutter は古いライブラリを使っているとのことなので、Synaptic から
libgoocanvas-common, libgoocanvas3, libgoo-canvas-perl
の各パッケージをインストールします。そして、Shutter を立ち上げていたのなら
$ sudo killall shutter
が必要かもしれません。で、ログアウトして再びログインすれば、Shutter の「編集」が使えるようになっている筈です。

なお、ウェブページのスクリーンショットを撮る機能は、Synaptic で「gnome-web-photo」をインストールする必要があるようです。

Lubuntu 18.04 をインストール

　
ダウンロードはここから。Torrent を使うと速くダウンロードできます。

インストールは特にむずかしいことはなし。ここなどを参考にして下さい。先にネット接続をしておいて、必要なソフトを自動でダウンロード＆インストールしてくれるようにしておくとよい。サイズの小さいディストリビューションなので、インストールは比較的早く終わる。

まずはアップデート。
$ sudo apt update
$ sudo apt upgrade

ホームフォルダの日本語名を英語に直す。
$ env LANGUAGE=C LC_MESSAGES=C xdg-user-dirs-gtk-update

日本語入力は何もしなくても fcitx-mozc が使えるようだ。

Firefox から Google Chrome のインストール。パッケージインストーラーでうまくインストールできなかったら、/tmp/mozilla_***/ というフォルダに Chrome がダウンロードされているので、ファイルマネージャで開いて [右クリック]→[ソフトウェアのインストール] でインストールできる。

パネルを好きにカスタマイズする。自分は Leafpad や LXTerminal、Chrome などを追加しておいた。

全体としてあまりカスタマイズの余地はない。そういうことがしたい人はちがうディストリビューションを選びましょう。Lubuntu はシンプル（昔の Windows に似ている）でサクサク動くことは確か。

Ruby をインストールする。
Linux Mint に rbenv で Ruby を入れる - Camera Obscura
　
「ソフトウェア」から Geany をインストール。

Ubuntu に Ruby/SDL を入れる

Ruby/SDL
GitHub
　

インストール

まずはライブラリを入れる。

$ sudo apt-get install libsdl2-2.0 libsdl-sge-dev

　
Bundler で Gem 'rubysdl' を入れる。

何か Gem の場所がわからない。

$ bundle exec gem which sdl
/home/tomoki/.rbenv/versions/2.3.4/lib/ruby/gems/2.3.0/gems/rubysdl-2.2.0/lib/sdl.rb

　
サンプルを実行してみる。

$ cd ~/.rbenv/versions/2.3.4/lib/ruby/gems/2.3.0/gems/rubysdl-2.2.0/sample
$ ruby testsprite.rb
$ ruby testgl.rb
$ ruby movesp.rb

OK ですね！

Ruby/SDL はもうメンテされていないようだけれども、ちゃんと動くではないか。
　

SGE（SDL Graphics Extension）

$ sudo apt-get install libsdl-sge-dev

これをやってから rubysdl を入れないと、使えないメソッドがいろいろある。

赤い円を描いてみる。

require 'sdl'

SDL.init(SDL::INIT_VIDEO)
screen = SDL::Screen.open(300, 300, 16, SDL::SWSURFACE)
SDL::WM::set_caption("SDL", "")

red   = screen.format.map_rgb(255,   0,   0)
white = screen.format.map_rgb(255, 255, 255)

screen.draw_rect(0, 0, 300, 300, white, true)
screen.draw_circle(150, 150, 150, red, true, true)

screen.flip

loop do
  while event = SDL::Event.poll
    case event
    when SDL::Event::KeyDown, SDL::Event::Quit
      exit
    end
  end
  sleep 0.2
end

　
線が移動していくアニメーション。

require 'sdl'

def draw(&blk)
  SDL.init(SDL::INIT_VIDEO)
  screen = SDL::Screen.open(300, 300, 16, SDL::SWSURFACE)
  SDL::WM::set_caption("SDL", "")
  
  class << screen
    def color(r, g, b)
      format.map_rgb(r, g, b)
    end
  end
  
  Thread.new {screen.instance_eval(&blk)}
  
  loop do
    while event = SDL::Event.poll
      case event
      when SDL::Event::KeyDown, SDL::Event::Quit
        exit
      end
    end
    sleep 0.2
  end
end

draw do
  green = color(  0, 255,   0)
  white = color(255, 255, 255)
  
  draw_rect(0, 0, 300, 300, white, true)
  
  300.times do |x|
    draw_line(x, 0, 299 - x, 299, green, true)
    flip
    sleep(0.05)
  end
end

SDL::TTF

フォント描画。

　
Linux Mint 18.3 の TakaoExMincho.ttf を使ってみる。
sdl_sample5.rb

require_relative 'sdl_draw'

draw(300, 150) do
  SDL::TTF.init
  font = SDL::TTF.open("/usr/share/fonts/truetype/takao-mincho/TakaoExMincho.ttf", 40)
  font.draw_solid_utf8(self, "Ruby", 10, 10, 0, 255, 255)
  font.draw_blended_utf8(self, "Ruby", 10, 50, 0, 255, 0)
  font.draw_blended_utf8(self, "岐阜", 10, 100, 255, 0, 0)
  flip
  font.close
end

ちゃんと漢字も描画可能だ。draw_solid_utf8() よりも draw_blended_utf8() の方がアンチエイリアスが効いていたりして、きれいである。

sdl_draw.rb は描画の定型を簡単にライブラリ化したもので、ここを参照。
　

require_relative 'sdl_draw'

draw(300, 100) do
  fill_rect(0, 0, 300, 100, color(255, 255, 255))
  
  SDL::TTF.init
  font = SDL::TTF.open("/usr/local/share/fonts/CHEESE__.TTF", 40)
  font.draw_blended_utf8(self, "Ruby/SDL", 47, 30, 0, 0, 0)
  flip
  font.close
end

#Font: http://www.cfont.jp/bitmap/cheese.html

SDL::Kanji

bdfフォントで漢字を使ってみる。

　
まず bdfフォント（いまでは一般的でない）を入手しなければならない。例えばここが参考になります。自分は東雲 ビットマップフォントファミリーを使わせて頂きました。ダウンロードはここから。これを解凍して、適当な場所に置きます。

コード。
sdl_sample4.rb

require_relative 'sdl_draw'

Dir.chdir("/home/tomoki/Documents/shinonome-0.9.11/bdf/")

draw(300, 300) do
  ["shnmk16", "shnmk16b", "shnmk16min", "shnmk16minb"].each_with_index do |font, i|
    kanji = SDL::Kanji.open(font + ".bdf", 16)
    ["Ｒｕｂｙ", "ルビイ", "浅野"].each_with_index do |text, j|
      kanji.put(self, text, 10, i * 70 + j * 20, 255, 255, 0)
      flip
      sleep(0.5)
    end
    kanji.close
  end
end

SDL::TTF できれいに漢字が描画できるので、わざわざ SDL::Kanji を使う必要はあまりないだろう。懐かしさを体験してみるとか。
　

require_relative 'sdl_draw'

Dir.chdir("/home/tomoki/Documents/shinonome-0.9.11/bdf/")

draw(300, 100) do
  ["shnmk12min", "shnmk12maru", "shnmk12p"].each_with_index do |font, i|
    kanji = SDL::Kanji.open(font + ".bdf", 12)
    kanji.put(self, "魔法の杖を手に入れた！", 10, i * 20 + 15, 0, 255, 0)
    flip
    sleep(0.5)
    kanji.close
  end
end

SDL::BMFont

ビットマップフォントを使ってみる。

　
フォントは SFont 形式を使った。ダウンロード、解凍して適当な場所に置く。
sdl_sample6.rb

require_relative 'sdl_draw'

Dir.chdir("/home/tomoki/Documents/SFont-2.03")

draw(300, 150) do
  fill_rect(0, 0, 300, 150, color(0xe7, 0xfc, 0xb5))
  
  flag = SDL::BMFont::TRANSPARENT | SDL::BMFont::SFONT
  
  font = SDL::BMFont.open("24P_Arial_NeonYellow.png", flag)
  font.textout(self, "Ruby", 10, 10)
  font.close
  
  font = SDL::BMFont.open("24P_Copperplate_Blue.png", flag)
  font.textout(self, "SDL", 10, 50)
  font.close
  
  flip
end

SFont だと色も使えないし大きさも選べない上に、ASCIIコードしか表示できない。あまり使い道はなさそう。

ネット上の Sinatra 掲示板サンプルコードを動かしてみる（Ruby）

スクリーンショット。

yharaさんの作られたサンプル。
https://github.com/yhara/sinatbbs
　
Sqlite3 が必要なので入れる。

$ sudo apt-get install sqlite3 libsqlite3-dev

git clone。

$ git clone git://github.com/yhara/sinatbbs.git

　
実行。「bundle exec」が面倒なら「start.rb」に「require "bundler/setup"」を追加。

$ cd sinatbbs
$ bundle install
$ ruby start.rb

ブラウザでhttp://localhost:4567/をアクセス。

※技評での連載
第9回 SinatraとSequel・Hamlで掲示板アプリを作る：Ruby Freaks Lounge｜gihyo.jp … 技術評論社

23.101.169.3

どうもよくわからないアクセスがある。

$ whois 23.101.169.3

#
# ARIN WHOIS data and services are subject to the Terms of Use
# available at: https://www.arin.net/whois_tou.html
#
# If you see inaccuracies in the results, please report at
# https://www.arin.net/resources/whois_reporting/index.html
#


NetRange:       23.96.0.0 - 23.103.255.255
CIDR:           23.96.0.0/13
NetName:        MSFT
NetHandle:      NET-23-96-0-0-1
Parent:         NET23 (NET-23-0-0-0-0)
NetType:        Direct Assignment
OriginAS:       AS8075
Organization:   Microsoft Corporation (MSFT)
RegDate:        2013-06-18
Updated:        2013-06-18
Ref:            https://whois.arin.net/rest/net/NET-23-96-0-0-1



OrgName:        Microsoft Corporation
OrgId:          MSFT
Address:        One Microsoft Way
City:           Redmond
StateProv:      WA
PostalCode:     98052
Country:        US
RegDate:        1998-07-09
Updated:        2017-01-28
Comment:        To report suspected security issues specific to traffic emanating from Microsoft online services, including the distribution of malicious content or other illicit or illegal material through a Microsoft online service, please submit reports to:
Comment:        * https://cert.microsoft.com.  
Comment:        
Comment:        For SPAM and other abuse issues, such as Microsoft Accounts, please contact:
Comment:        * abuse@microsoft.com.  
Comment:        
Comment:        To report security vulnerabilities in Microsoft products and services, please contact:
Comment:        * secure@microsoft.com.  
Comment:        
Comment:        For legal and law enforcement-related requests, please contact:
Comment:        * msndcc@microsoft.com
Comment:        
Comment:        For routing, peering or DNS issues, please 
Comment:        contact:
Comment:        * IOC@microsoft.com
Ref:            https://whois.arin.net/rest/org/MSFT


OrgAbuseHandle: MAC74-ARIN
OrgAbuseName:   Microsoft Abuse Contact
OrgAbusePhone:  +1-425-882-8080 
OrgAbuseEmail:  abuse@microsoft.com
OrgAbuseRef:    https://whois.arin.net/rest/poc/MAC74-ARIN

OrgTechHandle: MRPD-ARIN
OrgTechName:   Microsoft Routing, Peering, and DNS
OrgTechPhone:  +1-425-882-8080 
OrgTechEmail:  IOC@microsoft.com
OrgTechRef:    https://whois.arin.net/rest/poc/MRPD-ARIN


#
# ARIN WHOIS data and services are subject to the Terms of Use
# available at: https://www.arin.net/whois_tou.html
#
# If you see inaccuracies in the results, please report at
# https://www.arin.net/resources/whois_reporting/index.html
#

　
マイクロソフトが間欠的に自分のブログに訪れる筈がないので、何らかのなりすましの気がする。
「Internet Explorer 9」＋「Windows Vista」とかも、怪しすぎる。
アクセスしているページにも疑問がある。どうもあまりいい気がしない。アク禁にする。

Googleユーザーのあなた、おめでとうございます！(1)件のGoogleギフトが当選しました！

　
悪質なフィッシング詐欺。なんと Wikipedia からリンクされていた（ここの外部リンクから）。URLは以下。
http://play.net-do39.stream/sweep/g-ix-rl/index-jp-g-fx.html

AOJ（Introduction to Algorithms and Data Structures）その1

AIZU ONLINE JUDGE: Programming Challenge
　
ALDS1_1_A

#挿入ソート
gets
ar = gets.split.map(&:to_i)
n = ar.size
putout = ->{puts ar.join(" ")}

putout.()
1.upto(n - 1) do |i|
  v = ar[i]
  j = i - 1
  while j >= 0 and ar[j] > v
    ar[j + 1] = ar[j]
    j -= 1
  end
  ar[j + 1] = v
  putout.()
end

ALDS1_1_B

#最大公約数
gcd = ->(x, y) {
  return x if y.zero?
  gcd.(y, x % y)
}
puts gcd.(*gets.split.map(&:to_i))

ALDS1_1_C

#高速な素数の判定
is_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?
  k, step = 5, 2
  guard = Math.sqrt(n).to_i
  while k <= guard
    return false if (n % k).zero?
    k += step
    step = 6 - step
  end
  true
}

gets
co = 0
$stdin.readlines.map(&:to_i).each {|num| co += 1 if is_prime.(num)}
puts co

ALDS1_1_D

#FX取引の利益の最大値
n = $<.gets.to_i
r = n.times.map {$<.gets.to_i}

min_r = r.first
max = -Float::INFINITY
(n - 1).times do |i|
  a = r[i + 1]
  dif = a - min_r
  max = dif if dif > max
  min_r = a if a < min_r
end
puts max

　
ALDS1_2_A

#バブルソート
gets
ar = gets.split.map(&:to_i)
co = 0
(ar.size - 2).downto(0) do |i|
  (i + 1).times do |j|
    if ar[j] > ar[j + 1]
      ar[j], ar[j + 1] = ar[j + 1], ar[j]
      co += 1
    end
  end
end
puts ar.join(" ")
puts co

ALDS1_2_B

#選択ソート
gets
ar = gets.split.map(&:to_i)
l = ar.size
co = 0
(l - 1).times do |i|
  min = i
  (i + 1).upto(l - 1) {|j| min = j if ar[j] < ar[min]}
  ar[min], ar[i] = ar[i], ar[min]
  co += 1 if i != min
end
puts ar.join(" ")
puts co

ALDS1_2_C

n = gets.to_i
cards = gets.split

value = ->(card) {
  card[1].to_i
}

bubble_sort = ->(ar) {
  n.times do |i|
    (n - 1).downto(i + 1) do |j|
      ar[j], ar[j - 1] = ar[j - 1], ar[j] if value.(ar[j]) < value.(ar[j - 1])
    end
  end
  ar
}

selection_sort = ->(ar) {
  result = "Stable"
  n.times do |i|
    minj = i
    f = false
    (i + 1).upto(n - 1) do |j|
      f = true if value.(ar[i]) == value.(ar[j])
      if value.(ar[j]) < value.(ar[minj])
        minj = j
        result = "Not stable" if f
      end
    end
    ar[i], ar[minj] = ar[minj], ar[i]
  end
  return ar, result
}

puts bubble_sort.(cards.dup).join(" ")
puts "Stable"
ar, result = selection_sort.(cards)
puts ar.join(" ")
puts result

ALDS1_2_D
制限時間ギリギリだった。

#シェルソート
n = gets.to_i
a = Array.new(n, 0)
n.times {|i| a[i] = gets.to_i}
cnt = 0

insertion_sort = ->(a, g) {
  g.upto(n - 1) do |i|
    v = a[i]
    j = i - g
    while j >= 0 and a[j] > v
      a[j + g] = a[j]
      j -= g
      cnt += 1
    end
    a[j + g] = v
  end
}

i = (n == 1) ? 1 : n / 2
g = []
while i > 0
  g << i
  i /= 2
end
m = g.size
g.each {|i| insertion_sort.(a, i)}

puts m
puts g.join(" ")
puts cnt
puts a

　
ALDS1_3_A

#逆ポーランド記法
data = gets.chomp.split
stack = []

while (x = data.shift)
  if /^[\+\-\*]$/.match(x)
    a, b = stack.pop, stack.pop
    stack << eval(b + x + a).to_s
  else
    stack << x
  end
end
puts stack.last

ALDS1_3_B

#ラウンドロビンスケジューリング
n, q = gets.split.map(&:to_i)
queue = []
n.times do
  name, time = gets.chomp.split
  queue << [name, time.to_i]
end
t = 0

while (x = queue.shift)
  if x[1] <= q
    t += x[1]
    puts "#{x[0]} #{t}"
  else
    t += q
    queue << [x[0], x[1] - q]
  end
end

ALDS1_3_C
制限時間オーバーしているのに許されている（笑）。でも Ruby でこれ以上速くってたぶん無理だよね。

n = gets.to_i
commands = []
n.times {commands << gets.chomp.split}
list = []

commands.each do |co|
  case co[0]
  when "insert"
    list.unshift(co[1])
  when "delete"
    i = list.index(co[1])
    list.delete_at(i) if i
  when "deleteFirst"
    list.shift
  when "deleteLast"
    list.pop
  end
end
puts list.join(" ")

ALDS1_3_D
むずかしかったー。何とか正解。よくこんなの解けたな。模範解答はどうなのだろう。
このアルゴリズムだと highest.() を何度も呼ばないといけない。これが無駄なのだけれど、O(n) でいけるのかねえ。

#Areas on the Cross-Section Diagram
diagram = gets.chomp.chars

upper_skip = ->{
  loop do
    a = diagram[0]
    return false if a == "\\"
    return true unless a
    diagram.shift
  end
}

downer_skip = ->(target_height) {
  height = index = 0
  until height == target_height
    height -= 1 if diagram.shift == "\\"
    index += 1
  end
  index
}

highest = ->{
  index = height = 0
  max_height = -Float::INFINITY 
  diagram.size.times do |j|
    case diagram[j]
    when "\\"
      height -= 1
    when "/"
      height += 1
      max_height, index = height, j if max_height < height
      return [0, j] if height.zero?
    end
  end
  [max_height, index]
}

calc_area = ->(from, to) {
  depth = area = 0
  from.upto(to) do
    case diagram.shift
    when "\\"
      area += depth + 1/2r
      depth += 1
    when "_"
      area += depth
    when "/"
      depth -= 1
      area += depth + 1/2r
    end
  end
  area.to_i
}


pools = []
loop do
  break if upper_skip.()
  height, last_index = highest.()
  if height == -Float::INFINITY
    break
  else
    first_index = downer_skip.(height)
    pools << calc_area.(first_index, last_index)
  end
end

if pools.empty?
  puts 0, 0
else
  puts pools.inject(&:+)
  puts pools.size.to_s + " " + pools.join(" ")
end

別解。思いついたのだが、こちらの方が遅い。コードも読みにくい。

diagram = gets.chomp.chars

search = ->{
  max = min = height = 0
  diagram.each_with_index do |x, i|
    case x
    when "\\"
      height -= 1
      min = height if height < min
    when "/"
      height += 1
      max = height if height > max
    end
  end
  [max - min, max]
}

n, level = search.()
table = Array.new(n) {[]}

diagram.each_with_index do |x, i|
  case x
  when "\\"
    table[level] << i
    level += 1
  when "/"
    level -= 1
    a = table[level].last
    table[level] << i if a
  end
  table
end
table.map! do |one_level|
  one_level.each_slice(2).with_object([]) {|x, ar| ar << x if x.size == 2}
end

calc_area = ->(pair, level) {
  area = pair[1] - pair[0]
  return area if level == n
  one_level = table[level]
  table[level].each do |downer_pair|
    if pair[0] < downer_pair[0] and downer_pair[1] < pair[1]
      one_level -= [downer_pair]
      area += calc_area.(downer_pair, level + 1)
    end
  end
  table[level] = one_level
  area
}

pools = []
solve = ->{
  min = [[Float::INFINITY, 0], 0]
  table.each_with_index do |one_level, i|
    next if one_level.empty?
    pair = one_level[0]
    min = [pair, i] if pair[0] < min[0][0]
  end
  table[min[1]] -= [min[0]]
  pools << calc_area.(min[0], min[1] + 1) if min[0][0] != Float::INFINITY
  solve.() unless table.flatten.empty?
}

solve.() unless table.empty?

if pools.empty?
  puts 0, 0
else
  puts pools.inject(&:+)
  puts pools.size.to_s + " " + pools.join(" ")
end

模範解答的なのは例えばこれ。すごいですね…。
　
ALDS1_4_A

#Linear Search
n = gets.to_i
s = gets.split.map(&:to_i)
q = gets.to_i
t = gets.split.map(&:to_i)

count = 0
s.each do |x|
  t1 = t
  t.each do |y|
    if x == y
      count += 1
      t1 -= [y]
      break
    end
  end
  t = t1
end
puts count

ALDS1_4_B

#Binary Search
n = gets.to_i
s = gets.split.map(&:to_i)
q = gets.to_i
t = gets.split.map(&:to_i).sort

count = 0
i = j = 0
while i < n and j < q
  if s[i] == t[j]
    count += 1
    i += 1
    j += 1
  elsif s[i] < t[j]
    i += 1
  else
    j += 1
  end
end
puts count

ALDS1_4_C
最初時間オーバーばかりしていて苦労してもダメだったが、解決策はコロンブスの卵だった…。

#Dictionary
require 'set'

n = gets.to_i
commands = []
n.times {commands << gets.chomp.split}

dict = Set.new
commands.each do |c, str|
  case c
  when "insert"
    dict << str
  when "find"
    puts dict.include?(str) ? "yes" : "no"
  end
end

ALDS1_4_D
むずかしい。模範解答を参考にした。

n, k = gets.split.map(&:to_i)
weights = []
n.times {weights << gets.to_i}

#最大積載量pのとき積める荷物の数
pack_num = ->(p) {
  i = truck_n = 0
  while truck_n < k
    truck_w = 0
    while i < n
      truck_w += weights[i]
      break if truck_w > p.to_i
      i += 1
    end
    truck_n += 1
  end
  i
}

left, right = 0.0, 100_000 * 10_000
until right - left < 1
  mid = (left + right) / 2
  num = pack_num.(mid)
  if num >= n
    right = mid
  else
    left  = mid
  end
end
puts right.to_i

　
ALDS1_5_A
制限時間以内にできない。模範解答を参考にした。メモ化は自分で加えた。

#全探索
n = gets.to_i
a = gets.split.map(&:to_i)
q = gets.to_i
m = gets.split.map(&:to_i)

memo = {}

solve = ->(i, m) {
  return memo[[i, m]] if memo.has_key?([i, m])
  return true if m.zero?
  return false if i >= n || m < 0
  memo[[i, m]] = solve.(i + 1, m) || solve.(i + 1, m - a[i])
}

m.each do |target|
  puts solve.(0, target) ? "yes" : "no"
end

ALDS1_5_B
指定してある擬似コードどおりにコーディングすると、時間オーバーになるのですが…。そもそも擬似コードに無駄がある。
Rubyでの高速な解答例を見ると、インチキしてあるのが多い。ひどいな。

#マージソート
n = gets.to_i
s = gets.split.map(&:to_i)
$co = 0

class Array
  def merge_sort
    merge = ->(a, b) {
      result = []
      while a.size > 0 and b.size > 0
        result.push((a[0] <= b[0]) ? a.shift : b.shift)
      end
      result + a + b
    }
    
    l = length
    return self if l <= 1
    q = l / 2
    $co += l
    merge.(self[0...q].merge_sort, self[q..-1].merge_sort)
  end
end

puts s.merge_sort.join(" ")
puts $co

ALDS1_5_C

#コッホ曲線
require 'matrix'
include Math

n = gets.to_i
rot = ->(v, θ) {
  t = θ / 180.0 * PI
  Matrix[[cos(t), -sin(t)], [sin(t), cos(t)]] * v
}
result = []

koch_curve = ->(p1, p2, level) {
  if level == n
    result << p1
    result << p2
  else
    l1 = (p2 - p1) / 3
    l2 = rot.(l1, 60)
    koch_curve.(p1, p3 = p1 + l1, level + 1)
    koch_curve.(p3, p4 = p3 + l2, level + 1)
    koch_curve.(p4, p5 = p3 + l1, level + 1)
    koch_curve.(p5, p2, level + 1)
  end
}

koch_curve.(Vector[0.0, 0.0], Vector[100.0, 0.0], 0)
([result[0]] + result + [result[-1]]).each_slice(2) do |a, _|
  printf "%.8f %.8f\n", a[0], a[1]
end

ALDS1_5_D
これはわからなかった。解答例を見てみたら、マージソートを使っている。なるほど。これはすごい。

#反転数
n = gets.to_i
a = gets.split.map(&:to_i)
$co = 0

class Array
  def merge_sort
    merge = ->(a, b) {
      result = []
      while a.size > 0 and b.size > 0
        result << if a[0] <= b[0]
          a.shift
        else
          $co += a.size
          b.shift
        end
      end
      result + a + b
    }
    
    l = length
    return self if l <= 1
    q = l / 2
    merge.(self[0...q].merge_sort, self[q..-1].merge_sort)
  end
end

a.merge_sort
puts $co

　
ALDS1_6_A

#計数ソート
n = gets.to_i
a = gets.split.map(&:to_i)

equal = Array.new(10001, 0)
n.times {|i| equal[a[i]] += 1}

equal[-1] = 0
10000.times {|i| equal[i] += equal[i - 1]}

result = Array.new(n)
n.times do |i|
  result[equal[a[i] - 1]] = a[i]
  equal[a[i] - 1] += 1
end

puts result.join(" ")

ALDS1_6_B

#分割
n = gets.to_i
a = gets.split.map(&:to_i)

class Array
  def partition
    x = self[-1]
    i = -1
    (size - 1).times do |j|
      if self[j] <= x
        i += 1
        self[i], self[j] = self[j], self[i]
      end
    end
    self[i + 1], self[-1] = self[-1], self[i + 1]
    i + 1
  end
end

r = a.partition
puts a[0, r].join(" ") + " [#{a[r]}] " + a[r + 1..-1].join(" ")

ALDS1_6_C
クイックソートの安定性は、安定なソートであるマージソートの結果と比較している。

#クイックソート
n = gets.to_i
cards = []
n.times do
  a, b = gets.chomp.split
  cards << [a, b.to_i]
end

class Array
  def partition(p, r)
    x = self[r][1]
    i = p - 1
    p.upto(r - 1) do |j|
      if self[j][1] <= x
        i += 1
        self[i], self[j] = self[j], self[i]
      end
    end
    self[i + 1], self[r] = self[r], self[i + 1]
    i + 1
  end
  
  def quick_sort(p, r)
    return if p >= r
    q = partition(p, r)
    quick_sort(p, q - 1)
    quick_sort(q + 1, r)
  end
  
  def merge_sort
    merge = ->(a, b) {
      result = []
      while a.size > 0 and b.size > 0
        result.push((a[0][1] <= b[0][1]) ? a.shift : b.shift)
      end
      result + a + b
    }
    
    l = length
    return self if l <= 1
    q = l / 2
    merge.(self[0...q].merge_sort, self[q..-1].merge_sort)
  end
end

another_cards = cards.merge_sort
cards.quick_sort(0, n - 1)
puts (cards == another_cards) ? "Stable" : "Not stable"
puts cards.map {|x| x.join(" ")}

　
ALDS1_7_A

#根付き木
n = gets.to_i
tree = Struct.new(:parent, :depth, :type, :children)
node = Array.new(n) {tree.new}
n.times do
  ar = gets.split.map(&:to_i)
  node[ar[0]].children = ar[2..-1]
  node[ar[0]].parent = -1
  node[ar[0]].type = "leaf"
end

node.each_with_index do |nd, i|
  nd.children.each {|child| node[child].parent = i}
  nd.type = "internal node" unless nd.children.empty?
end

root_index = 0
node.each_with_index {|nd, i| root_index = i if nd.parent == -1}
node[root_index].type = "root"

search = ->(index, depth) {
  node[index].depth = depth
  children = node[index].children
  return if children.empty?
  children.each {|child| search.(child, depth + 1)}
}
search.(root_index, 0)

node.each_with_index do |nd, i|
  puts "node #{i}: parent = #{nd.parent}, depth = #{nd.depth}, #{nd.type}, #{nd.children.inspect}"
end

別様にやってみた（2019/3/12）。

#根付き木
Node = Struct.new(:id, :c, :parent, :depth, :type)

nodes = $<.gets.to_i.times.map do
  id, k, *c = $<.gets.split.map(&:to_i)
  Node.new(id, c)
end.sort_by(&:id)

h = nodes.map {|n| [n.id, n]}.to_h
nodes.each {|n| n.c.each {|c| h[c].parent = n.id} }

root = nodes.find {|n| !n.parent}
root.parent = -1

search = ->(node, depth) {
  node.depth = depth
  if node.c.empty?
    node.type = "leaf"
  else
    node.type = "internal node"
    node.c.each {|c| search.(h[c], depth + 1)}
  end
}
search.(root, 0)
root.type = "root"

puts nodes.map {|n| "node #{n.id}: parent = #{n.parent}, depth = #{n.depth}, #{n.type}, #{n.c}"}

ALDS1_7_B

#二分木
n = gets.to_i
tree = Struct.new(:parent, :sibling, :degree, :depth, :height, :type, :children)
node = Array.new(n) {tree.new}
n.times do
  ar = gets.split.map(&:to_i)
  node[ar[0]].children = a = ar[1..-1].reject {|x| x == -1}
  node[ar[0]].degree = a.size
  node[ar[0]].parent = -1
  node[ar[0]].sibling = -1
  node[ar[0]].type = "internal node"
end

node.each_with_index do |nd, i|
  nd.children.each {|child| node[child].parent = i}
  case nd.degree
  when 0
    nd.type = "leaf"
    nd.height = 0
  when 1
    node[nd.children[0]].sibling = -1
  when 2
    node[nd.children[0]].sibling = nd.children[1]
    node[nd.children[1]].sibling = nd.children[0]
  end
end

root_index = 0
node.each_with_index {|nd, i| root_index = i if nd.parent == -1}
node[root_index].type = "root"

search = ->(index, depth) {
  node[index].depth = depth
  children = node[index].children
  height_max = 0
  children.each do |child|
    h = search.(child, depth + 1) + 1
    height_max = h if h > height_max
  end
  node[index].height = height_max
}
search.(root_index, 0)

node.each_with_index do |nd, i|
  puts "node #{i}: parent = #{nd.parent}, sibling = #{nd.sibling}, degree = #{nd.degree}, depth = #{nd.depth}, height = #{nd.height}, #{nd.type}"
end

上はたまたま通過したけれども、不備がある。改善したコード。

n = gets.to_i
tree = Struct.new(:parent, :sibling, :degree, :depth, :height, :type, :children)
node = Array.new(n) {tree.new}
n.times do
  ar = gets.split.map(&:to_i)
  node[ar[0]].children = ar[1..-1]
  node[ar[0]].degree = ar[1..-1].reject {|x| x == -1}.size
  node[ar[0]].parent = -1
  node[ar[0]].sibling = -1
  node[ar[0]].type = "internal node"
end

node.each_with_index do |nd, i|
  nd.children.each {|child| node[child].parent = i unless child == -1}
  case nd.degree
  when 0
    nd.type = "leaf"
    nd.height = 0
  else
    node[nd.children[0]].sibling = nd.children[1] unless nd.children[0] == -1
    node[nd.children[1]].sibling = nd.children[0] unless nd.children[1] == -1
  end
end

root_index = 0
node.each_with_index {|nd, i| root_index = i if nd.parent == -1}
node[root_index].type = "root"

search = ->(index, depth) {
  node[index].depth = depth
  children = node[index].children.reject {|x| x == -1}
  return 0 if children.empty?
  height_max = 0
  children.each do |child|
    h = search.(child, depth + 1) + 1
    height_max = h if h > height_max
  end
  node[index].height = height_max
}
search.(root_index, 0)

node.each_with_index do |nd, i|
  puts "node #{i}: parent = #{nd.parent}, sibling = #{nd.sibling}, degree = #{nd.degree}, depth = #{nd.depth}, height = #{nd.height}, #{nd.type}"
end

別様にやってみた。（2019/3/12）

#二分木
n = $<.gets.to_i
Node = Struct.new(:id, :left, :right, :depth, :type, :sibling, :degree, :parent, :height)

nodes = n.times.map { Node.new(*$<.gets.split.map(&:to_i)) }.sort_by(&:id)
root = [*0...n] - nodes.flat_map {|n| [n.left, n.right]}.uniq
root = nodes[root.first]
h = nodes.map {|n| [n.id, n]}.to_h

build_tree = ->(node, depth) {
  node.depth = depth
  l, r = node.left, node.right
  degree = 0
  hi1 = hi2 = 0
  try = ->(next_node, s) {
    next_node.sibling = s
    next_node.parent = node.id
    build_tree.(next_node, depth + 1)
    degree += 1
    next_node.height + 1
  }
  hi1 = try.(h[l], r) if l != -1
  hi2 = try.(h[r], l) if r != -1
  node.degree = degree
  if l == -1 and r == -1
    node.height = 0
    node.type = "leaf"
  else
    node.height = [hi1, hi2].max
    node.type = "internal node"
  end
}
build_tree.(root, 0)

root.type = "root"
root.sibling = -1
root.parent = -1

puts nodes.map {|n| "node #{n.id}: parent = #{n.parent}, sibling = #{n.sibling}, " +
  "degree = #{n.degree}, depth = #{n.depth}, height = #{n.height}, #{n.type}"}

ALDS1_7_C

#木の巡回
n = gets.to_i
tree = Struct.new(:parent, :children)
node = Array.new(n) {tree.new}
n.times do
  ar = gets.split.map(&:to_i)
  node[ar[0]].children = ar[1..-1]
  node[ar[0]].parent = -1
end

node.each_with_index do |nd, i|
  nd.children.each {|child| node[child].parent = i unless child == -1}
end

root_index = 0
node.each_with_index {|nd, i| root_index = i if nd.parent == -1}

preorder = ->(root) {
  @result << root
  a = node[root].children[0]
  preorder.(a) unless a == -1
  a = node[root].children[1]
  preorder.(a) unless a == -1
}

inorder = ->(root) {
  a = node[root].children[0]
  inorder.(a) unless a == -1
  @result << root
  a = node[root].children[1]
  inorder.(a) unless a == -1
}

postorder = ->(root) {
  a = node[root].children[0]
  postorder.(a) unless a == -1
  a = node[root].children[1]
  postorder.(a) unless a == -1
  @result << root
}

def putout(title)
  @result = []
  puts title
  yield
  puts @result.map {|x| " " + x.to_s}.join
end

putout("Preorder")  {preorder .(root_index)}
putout("Inorder")   {inorder  .(root_index)}
putout("Postorder") {postorder.(root_index)}

ALDS1_8_A

#二分探索木I
node = Struct.new(:key, :parent, :left, :right)
root = nil

insert = ->(z) {
  pa = nil
  x = root
  while x
    pa = x
    x = (z.key < x.key) ? x.left : x.right
  end
  z.parent = pa
  
  if pa.nil?
    root = z
  elsif z.key < pa.key
    pa.left  = z
  else
    pa.right = z
  end
}

inorder = ->(x) {
  a = x.left
  inorder.(a) if a
  print " " + x.key.to_s
  a = x.right
  inorder.(a) if a
}

preorder = ->(x) {
  print " " + x.key.to_s
  a = x.left
  preorder.(a) if a
  a = x.right
  preorder.(a) if a
}

gets.to_i.times do
  command = gets.split(" ")
  case command[0]
  when "insert"
    z = node.new
    z.key = command[1].to_i
    insert.(z)
  when "print"
    inorder .(root)
    puts
    preorder.(root)
    puts
  end
end

別様にやってみた。（201/3/12）

#二分探索木I
Node = Struct.new(:key, :left, :right)

class Tree
  def initialize
    @root = nil
  end
  
  def insert(key)
    unless @root
      @root = Node.new(key)
      return
    end
    node = @root
    while node
      if key < node.key
        if node.left
          node = node.left
        else
          node.left = Node.new(key)
          break
        end
      else
        if node.right
          node = node.right
        else
          node.right = Node.new(key)
          break
        end
      end
    end
  end
  
  def preorder
    traverse = ->(node) {
      if node
        yield(node.key)
        traverse.(node.left)
        traverse.(node.right)
      end
    }
    traverse.(@root)
  end
  
  def inorder
    traverse = ->(node) {
      if node
        traverse.(node.left)
        yield(node.key)
        traverse.(node.right)
      end
    }
    traverse.(@root)
  end
end

t = Tree.new

$<.gets.to_i.times do
  com, key = $<.gets.split
  case com
  when "insert" then t.insert(key.to_i)
  when "print"
    t.inorder  {|key| print " #{key}"}
    puts
    t.preorder {|key| print " #{key}"}
    puts
  end
end

2.33秒かかった。

ALDS1_8_B
これだとタイムオーバーしてしまう。

node = Struct.new(:key, :parent, :left, :right)
root = nil

insert = ->(z) {
  pa = nil
  x = root
  while x
    pa = x
    x = (z.key < x.key) ? x.left : x.right
  end
  z.parent = pa
  
  if pa.nil?
    root = z
  elsif z.key < pa.key
    pa.left  = z
  else
    pa.right = z
  end
}

inorder = ->(x) {
  a = x.left
  inorder.(a) if a
  print " " + x.key.to_s
  a = x.right
  inorder.(a) if a
}

preorder = ->(x) {
  print " " + x.key.to_s
  a = x.left
  preorder.(a) if a
  a = x.right
  preorder.(a) if a
}

memo = []

gets.to_i.times do
  command = gets.split(" ")
  case command[0]
  when "insert"
    z = node.new
    memo << z.key = command[1].to_i
    insert.(z)
  when "print"
    inorder .(root)
    puts
    preorder.(root)
    puts
  when "find"
    puts memo.include?(command[1].to_i) ? "yes" : "no"
  end
end

他の回答を参考にして find.() を書き直した。find.() は二分木の特性を利用して最短でのルートで探索する。ついでに insert.() も修正。

node = Struct.new(:key, :left, :right)
root = nil

insert = ->(pa, z) {
  if pa.key > z
    if pa.left
      insert.(pa.left, z)
    else
      pa.left = node.new(z)
    end
  else
    if pa.right
      insert.(pa.right, z)
    else
      pa.right = node.new(z)
    end
  end
}

inorder = ->(x) {
  a = x.left
  inorder.(a) if a
  print " " + x.key.to_s
  a = x.right
  inorder.(a) if a
}

preorder = ->(x) {
  print " " + x.key.to_s
  a = x.left
  preorder.(a) if a
  a = x.right
  preorder.(a) if a
}

find = ->(x, k, bool) {
  if x.key == k
    bool = true
  else
    if x.left && x.key > k
      bool = find.(x.left,  k, bool)
    end
    if x.right && x.key < k
      bool = find.(x.right, k, bool)
    end
  end/
  bool
}

gets.to_i.times do
  command = gets.split(" ")
  case command[0]
  when "insert"
    if root
      insert.(root, command[1].to_i)
    else
      root = node.new(command[1].to_i)
    end
  when "print"
    inorder .(root)
    puts
    preorder.(root)
    puts
  when "find"
    puts find.(root, command[1].to_i, false) ? "yes" : "no"
  end
end

別様にやってみた。（2019/3/12）

#二分探索木II
Node = Struct.new(:key, :left, :right)

class Tree
  def initialize
    @root = nil
  end
  
  def insert(key)
    unless @root
      @root = Node.new(key)
      return
    end
    node = @root
    while node
      if key < node.key
        if node.left
          node = node.left
        else
          node.left = Node.new(key)
          break
        end
      else
        if node.right
          node = node.right
        else
          node.right = Node.new(key)
          break
        end
      end
    end
  end
  
  def search(key)
    node = @root
    while node
      if key < node.key
        node = node.left
      elsif key > node.key
        node = node.right
      else
        return node
      end
    end
    nil
  end
  
  def preorder
    traverse = ->(node) {
      if node
        yield(node.key)
        traverse.(node.left)
        traverse.(node.right)
      end
    }
    traverse.(@root)
  end
  
  def inorder
    traverse = ->(node) {
      if node
        traverse.(node.left)
        yield(node.key)
        traverse.(node.right)
      end
    }
    traverse.(@root)
  end
end

t = Tree.new

$<.gets.to_i.times do
  com, key = $<.gets.split
  case com
  when "insert" then t.insert(key.to_i)
  when "print"
    t.inorder  {|key| print " #{key}"}
    puts
    t.preorder {|key| print " #{key}"}
    puts
  when "find"
    puts t.search(key.to_i) ? "yes" : "no"
  end
end

2.04秒かかった。

ALDS1_8_C

#二分探索木III
Node = Struct.new(:key, :left, :right)

class Tree
  def initialize
    @root = nil
  end
  
  def insert(key)
    unless @root
      @root = Node.new(key)
      return
    end
    node = @root
    while node
      if key < node.key
        if node.left
          node = node.left
        else
          node.left = Node.new(key)
          break
        end
      else
        if node.right
          node = node.right
        else
          node.right = Node.new(key)
          break
        end
      end
    end
  end
  
  def search(key)
    node = @root
    while node
      if key < node.key
        node = node.left
      elsif key > node.key
        node = node.right
      else
        return node
      end
    end
    nil
  end
  
  def delete(key)
    delete_min = ->(node) {
      return node.right unless node.left
      node.left = delete_min.(node.left)
      node
    }
    del = ->(node) {
      if node
        if key == node.key
          if node.left.nil?
            return node.right
          elsif node.right.nil?
            return node.left
          else
            min_node = search_min(node.right)
            node.key = min_node.key
            node.right = delete_min.(node.right)
          end
        elsif key < node.key
          node.left  = del.(node.left)
        else
          node.right = del.(node.right)
        end
      end
      return node
    }
    
    @root = del.(@root)
  end
  
  def preorder
    traverse = ->(node) {
      if node
        yield(node.key)
        traverse.(node.left)
        traverse.(node.right)
      end
    }
    traverse.(@root)
  end
  
  def inorder
    traverse = ->(node) {
      if node
        traverse.(node.left)
        yield(node.key)
        traverse.(node.right)
      end
    }
    traverse.(@root)
  end
  
  private
  
  def search_min(node)
    node = node.left while node.left
    node
  end
end

t = Tree.new

$<.gets.to_i.times do
  com, key = $<.gets.split
  key = key.to_i
  case com
  when "insert" then t.insert(key)
  when "print"
    t.inorder  {|key| print " #{key}"}
    puts
    t.preorder {|key| print " #{key}"}
    puts
  when "find"
    puts t.search(key) ? "yes" : "no"
  when "delete" then t.delete(key)
  end
end

2.15秒かかった。

ALDS1_8_D

#Treap
Node = Struct.new(:key, :priority, :left, :right)

class Tree
  def initialize
    @root = nil
  end
  
  def insert(key, priority)
    unless @root
      @root = Node.new(key, priority)
      return
    end
    insert = ->(node) {
      return Node.new(key, priority) unless node
      return node if key == node.key
      if key < node.key
        node.left  = insert.(node.left)
        node = right_rotate(node) if node.priority < node.left.priority
      else
        node.right = insert.(node.right)
        node = left_rotate(node)  if node.priority < node.right.priority
      end
      node
    }
    @root = insert.(@root)
  end
  
  def search(key)
    node = @root
    while node
      if key < node.key
        node = node.left
      elsif key > node.key
        node = node.right
      else
        return node
      end
    end
    nil
  end
  
  def delete(key)
    delete1 = nil
    
    delete = ->(node) {
      return nil unless node
      if key < node.key
        node.left  = delete.(node.left)
      elsif key > node.key
        node.right = delete.(node.right)
      else
        return delete1.(node)
      end
      node
    }
    delete1 = ->(node) {
      return nil if !node.left and !node.right
      node = if node.left.nil?
        left_rotate(node)
      elsif node.right.nil?
        right_rotate(node)
      else
        if node.left.priority > node.right.priority
          right_rotate(node)
        else
          left_rotate(node)
        end
      end
      delete.(node)
    }
    @root = delete.(@root)
  end
  
  def right_rotate(node)
    tmp = node.left
    node.left = tmp.right
    tmp.right = node
    tmp
  end
  
  def left_rotate(node)
    tmp = node.right
    node.right = tmp.left
    tmp.left = node
    tmp
  end
  
  def preorder
    traverse = ->(node) {
      if node
        yield(node.key)
        traverse.(node.left)
        traverse.(node.right)
      end
    }
    traverse.(@root)
  end
  
  def inorder
    traverse = ->(node) {
      if node
        traverse.(node.left)
        yield(node.key)
        traverse.(node.right)
      end
    }
    traverse.(@root)
  end
end

t = Tree.new

$<.gets.to_i.times do
  com, key, priority = $<.gets.split
  key = key.to_i
  priority = priority.to_i
  case com
  when "insert" then t.insert(key, priority)
  when "print"
    t.inorder  {|key| print " #{key}"}
    puts
    t.preorder {|key| print " #{key}"}
    puts
  when "find"
    puts t.search(key) ? "yes" : "no"
  when "delete" then t.delete(key)
  end
end

2.32秒かかった。できているのは Ruby で 3人だけ。よくできたな。