ABC161

https://atcoder.jp/contests/abc161
過去問。

A: ABC Swap

a, b, c = gets.split.map(&:to_i)

a, b = b, a
a, c = c, a

puts "#{a} #{b} #{c}"

B: Popular Vote

n, m = gets.split.map(&:to_i)
votes = gets.split.map(&:to_i)

limit = Rational(votes.inject(&:+), 4 * m)
num = votes.reject {|v| v < limit}.size

puts (m <= num) ? "Yes" : "No"

C: Replacing Integer

最初、以下でやってひとつだけ WA になった。

def solve(x, k, tmp_min)
  tmp_min0 = [x, tmp_min].min
  return tmp_min if tmp_min0 == tmp_min
  solve((x - k).abs, k, tmp_min0)
end

n, k = gets.split.map(&:to_i)
puts solve(n % k, k, n)

　
解説を見ると、実際は

n, k = gets.split.map(&:to_i)

t = n % k
puts [k - t, t].min

でいい。これはわかったのだが、上の何がいけなかったのだろう。
　

D: Lunlun Number

とりあえず最初の500個を出力してみる。

def lunlun?(x)
  return true if x < 10
  str = x.to_s
  pred = str[0].to_i
  str[1..-1].each_char do |c|
    tmp = c.to_i
    return false unless (pred - tmp).abs <= 1
    pred = tmp
  end
  true
end

result = []
count = 0
1.step do |i|
  if lunlun?(i)
    result << i
    count += 1
    break if count >= 500
  end
end
p result

すると、こんな感じ。

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 21, 22, 23, 32, 33, 34, 43, 44, 45, 54, 55, 56, 65, 66, 67, 76, 77, 78, 87, 88, 89, 98, 99, 100, 101, 110, 111, 112, 121, 122, 123, 210, 211, 212, 221, 222, 223, 232, 233, 234, 321, 322, 323, 332, 333, 334, 343, 344, 345, 432, 433, 434, 443, 444, 445, 454, 455, 456, 543, 544, 545, 554, 555, 556, 565, 566, 567, 654, 655, 656, 665, 666, 667, 676, 677, 678, 765, 766, 767, 776, 777, 778, 787, 788, 789, 876, 877, 878, 887, 888, 889, 898, 899, 987, 988, 989, 998, 999, 1000, 1001, 1010, 1011, 1012, 1100, 1101, 1110, 1111, 1112, 1121, 1122, 1123, 1210, 1211, 1212, 1221, 1222, 1223, 1232, 1233, 1234, 2100, 2101, 2110, 2111, 2112, 2121, 2122, 2123, 2210, 2211, 2212, 2221, 2222, 2223, 2232, 2233, 2234, 2321, 2322, 2323, 2332, 2333, 2334, 2343, 2344, 2345, 3210, 3211, 3212, 3221, 3222, 3223, 3232, 3233, 3234, 3321, 3322, 3323, 3332, 3333, 3334, 3343, 3344, 3345, 3432, 3433, 3434, 3443, 3444, 3445, 3454, 3455, 3456, 4321, 4322, 4323, 4332, 4333, 4334, 4343, 4344, 4345, 4432, 4433, 4434, 4443, 4444, 4445, 4454, 4455, 4456, 4543, 4544, 4545, 4554, 4555, 4556, 4565, 4566, 4567, 5432, 5433, 5434, 5443, 5444, 5445, 5454, 5455, 5456, 5543, 5544, 5545, 5554, 5555, 5556, 5565, 5566, 5567, 5654, 5655, 5656, 5665, 5666, 5667, 5676, 5677, 5678, 6543, 6544, 6545, 6554, 6555, 6556, 6565, 6566, 6567, 6654, 6655, 6656, 6665, 6666, 6667, 6676, 6677, 6678, 6765, 6766, 6767, 6776, 6777, 6778, 6787, 6788, 6789, 7654, 7655, 7656, 7665, 7666, 7667, 7676, 7677, 7678, 7765, 7766, 7767, 7776, 7777, 7778, 7787, 7788, 7789, 7876, 7877, 7878, 7887, 7888, 7889, 7898, 7899, 8765, 8766, 8767, 8776, 8777, 8778, 8787, 8788, 8789, 8876, 8877, 8878, 8887, 8888, 8889, 8898, 8899, 8987, 8988, 8989, 8998, 8999, 9876, 9877, 9878, 9887, 9888, 9889, 9898, 9899, 9987, 9988, 9989, 9998, 9999, 10000, 10001, 10010, 10011, 10012, 10100, 10101, 10110, 10111, 10112, 10121, 10122, 10123, 11000, 11001, 11010, 11011, 11012, 11100, 11101, 11110, 11111, 11112, 11121, 11122, 11123, 11210, 11211, 11212, 11221, 11222, 11223, 11232, 11233, 11234, 12100, 12101, 12110, 12111, 12112, 12121, 12122, 12123, 12210, 12211, 12212, 12221, 12222, 12223, 12232, 12233, 12234, 12321, 12322, 12323, 12332, 12333, 12334, 12343, 12344, 12345, 21000, 21001, 21010, 21011, 21012, 21100, 21101, 21110, 21111, 21112, 21121, 21122, 21123, 21210, 21211, 21212, 21221, 21222, 21223, 21232, 21233, 21234, 22100, 22101, 22110, 22111, 22112, 22121, 22122, 22123, 22210, 22211, 22212, 22221, 22222, 22223, 22232, 22233, 22234, 22321, 22322, 22323, 22332, 22333, 22334, 22343, 22344, 22345, 23210, 23211, 23212, 23221, 23222, 23223, 23232, 23233, 23234, 23321, 23322, 23323, 23332, 23333, 23334, 23343, 23344, 23345, 23432, 23433, 23434, 23443, 23444, 23445, 23454, 23455, 23456, 32100, 32101, 32110, 32111, 32112, 32121, 32122, 32123, 32210, 32211, 32212, 32221, 32222, 32223, 32232, 32233, 32234, 32321, 32322, 32323, 32332, 32333, 32334, 32343, 32344, 32345, 33210, 33211, 33212, 33221, 33222, 33223, 33232, 33233, 33234, 33321, 33322]

ふーむ。

よくわからないので、他の人の解答を参考にしてみる。

def solve(k)
  q = [*1..9]
  cnt = 0
  loop do
    return q[k - 1] if k < 10
    
    x = q[cnt]
    3.times do |i|
      return q.last if q.length == k
      
      d = x % 10 + (i - 1)
      next if d < 0 || d > 9
      
      q << x * 10 + d
    end
    cnt += 1
  end
end

puts solve(gets.to_i)

うーん、かしこい。これだと計算量は O(n) かあ。
　

E: Yutori

全然わからない。解答例。

n, k, c = gets.split.map(&:to_i)
str = gets.chomp

left  = Array.new(k)
right = Array.new(k)
l, r = 0, n - 1

k.times do |i|
  l += 1 while str[l] == "x"
  r -= 1 while str[r] == "x"
  left[i] = l
  right[k - i - 1] = r
  l += c + 1
  r -= c + 1
end

result = []
k.times do |i|
  if left[i] == right[i]
    result << left[i] + 1
  end
end

puts result

かしこいなあ。

Ruby で超簡単な CGI

エラーが出て全然わからない。

$ ruby test_webrick.rb
[2020-04-01 22:31:56] INFO  WEBrick 1.6.0
[2020-04-01 22:31:56] INFO  ruby 2.7.0 (2019-12-25) [x86_64-linux]
[2020-04-01 22:31:56] INFO  WEBrick::HTTPServer#start: pid=15497 port=19681
[2020-04-01 22:32:00] ERROR CGIHandler: test_cgi.rb:\n/home/tomoki/.rbenv/versions/2.7.0/lib/ruby/2.7.0/webrick/httpservlet/cgi_runner.rb:47:in `exec': Not a directory - test_cgi.rb (Errno::ENOTDIR)\n\tfrom /home/tomoki/.rbenv/versions/2.7.0/lib/ruby/2.7.0/webrick/httpservlet/cgi_runner.rb:47:in `<main>'\n
[2020-04-01 22:32:00] ERROR CGIHandler: test_cgi.rb exit with 1
[2020-04-01 22:32:00] ERROR Premature end of script headers: test_cgi.rb
192.168.11.4 - - [01/Apr/2020:22:31:59 JST] "GET /cgi HTTP/1.1" 500 328
- -> /cgi

解決

ここでようやく解決。CGIInterpreter: WEBrick::HTTPServlet::CGIHandler::Ruby の指定が必要だった。
　
サーバ側。これは先に実行する。
test_webrick_localhost.rb

require "webrick"

server = WEBrick::HTTPServer.new({
  DocumentRoot: './',
  BindAddress: "127.0.0.1",
  CGIInterpreter: WEBrick::HTTPServlet::CGIHandler::Ruby,
  Port: 19681
})

server.mount('/test_cgi', WEBrick::HTTPServlet::CGIHandler, 'test_cgi.rb')
server.mount('/test', WEBrick::HTTPServlet::FileHandler, 'test.html')
Signal.trap(:INT) {server.shutdown}
server.start

　
で、CGI用のコード。
test_cgi.rb

#!/usr/bin/env/ruby
require "cgi"

cgi = CGI.new "html4"

cgi.out do
  cgi.html do
    cgi.head { cgi.title {"CGI TEST"} } +
    cgi.body do
      cgi.p {"CGI TEST"}
    end
  end
end

実行権限を与えておく。で、ブラウザで http://localhost:19681/test_cgi にアクセスする。

また、test.html を書いておいて http://localhost:19681/test にアクセスすると、HTML がブラウザで実行される。

Ruby 2.7.0、Linux Mint 19.3、ブラウザは Chrome 80.0 で確認。
　

他の例

nyanko.rb

#!/usr/bin/env/ruby
require "cgi"

cgi = CGI.new "html4"

cgi.out do
  cgi.html do
    cgi.head { cgi.meta({charset: "UTF-8"}) + cgi.title {"CGI TEST"} } +
    cgi.body do
      cgi.p {"にゃんこ"} +
      cgi.img({src: "neko.jpg"})
    end
  end
end

http://localhost:19681/nyanko。

ABC159

https://atcoder.jp/contests/abc159
過去問。

A: The Number of Even Pairs

偶数から2個か奇数から2個取ればよい。

#x個の中から2個取る組み合わせの数
def c(x)
  return 0 if x == 0 || x == 1
  x * (x - 1) / 2
end

n, m = gets.split.map(&:to_i)
puts c(n) + c(m)

B: String Palindrome

#回文（palindrome）か
def pl?(str)
  str == str.reverse
end

s = gets.chomp
n = s.length
f = pl?(s) && pl?(s[0..(n - 3) / 2]) && pl?(s[(n + 1) / 2..-1])

puts f ? "Yes" : "No"

C: Maximum Volume

立方体になるときがいちばん体積が大きくなる。

x = gets.to_r / 3
puts (x ** 3).to_f

D: Banned K

まずは組み合わせの数をすべて足し合わせたもの（sum）を求めておく。

#x個の中から2個取る組み合わせの数
def c(x)
  return 0 if x == 0 || x == 1
  x * (x - 1) / 2
end

gets
balls = gets.split.map(&:to_i)

numbers_table = Hash.new(0)
balls.each {|n| numbers_table[n] += 1}

sum = numbers_table.map {|n, i| c(i)}.inject(&:+)

balls.each do |n|
  puts sum - c(numbers_table[n]) + c(numbers_table[n] - 1)
end

ABC158

https://atcoder.jp/contests/abc158
過去問。

A:Station and Bus

s = gets.chomp
puts (s == "AAA" || s == "BBB") ? "No" : "Yes"

B:Count Balls

n, a, b = gets.split.map(&:to_i)

blue_ball = (n / (a + b)) * a
remainder = n % (a + b)
blue_ball += (remainder >= a) ? a : remainder

puts blue_ball

C:Tax Increase

8%と10%の場合それぞれにおいて、消費税分から考えられる税抜価格の下限と上限を Rational で求める。それが f1() と f2()。そこから、条件に適合する税抜価格が存在するか、存在するならその下限を求めれば、それが答え。その判定を行うのが find()。上限の小さい方が整数の場合とそうでない場合で判定がちがってくるので注意。

def f1(a)
  [a / (8/100r), (a + 1) / (8/100r)]
end

def f2(b)
  [b / (10/100r), (b + 1) / (10/100r)]
end

def find(a1, a2)
  bgn = [a1[0], a2[0]].max.ceil
  ed = [a1[1], a2[1]].min
  f = if ed == ed.floor
    bgn < ed
  else
    bgn <= ed.floor
  end
  f ? bgn : -1
end

a, b = gets.split.map(&:to_i)
puts find(f1(a), f2(b))

なかなかむずかしかった。一発でいってホッとした。

D:String Formation

str = gets.chomp
q = gets.to_i
querys = q.times.map {gets.split}

querys.each do |ary|
  if ary[0] == "1"
    str.reverse!
  else
    if ary[1] == "1"
      str = ary[2] + str
    else
      str += ary[2]
    end
  end
end

puts str

TLE。素直に reverse を使ってはいけないということらしい。かしこい回答は例えばこれ。
ちょっと改良してみる。

str = gets.chomp
q = gets.to_i
querys = q.times.map {gets.split}

dir = true

querys.each do |ary|
  if ary[0] == "1"
    dir = !dir
  else
    if (ary[1] == "1" && dir) || (ary[1] == "2" && !dir)
      str = ary[2] + str
    else
      str += ary[2]
    end
  end
end

puts dir ? str : str.reverse!

やっぱりTLE。「+」でなく「<<」で String を結合しないと遅いらしい。

パナソニックプログラミングコンテスト2020

https://atcoder.jp/contests/panasonic2020
過去問。

A:Kth Term

ary = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
puts ary[gets.to_i - 1]

B:Bishop

HかWが 1 の場合を忘れていた。

h, w = gets.split.map(&:to_i)
puts (h == 1) || (w == 1) ? 1 : (w * h * 1/2r).ceil

C:Sqrt Inequality

必要十分条件をちょっと勘違いしていた。

a, b, c = gets.split.map(&:to_i)
result = if c - a - b <= 0
           "No"
         else
           (4 * a * b < (c - a - b) ** 2) ? "Yes" : "No"
         end
puts result

D:String Equivalence

よくわからなかった。解説を見た。

n = gets.to_i

solve = ->(str, max_char) {
  if str.length == n
    puts str
  else
    ("a"..max_char).each do |c|
      next_max = (c == max_char) ? max_char.succ : max_char
      solve.(str + c, next_max)
    end
  end
}

solve.("", "a")

BunsenLabs Hydrogen apt error

$ lsb_release -a
No LSB modules are available.
Distributor ID:	BunsenLabs
Description:	BunsenLabs GNU/Linux 8.9 (Hydrogen)
Release:	8.9
Codename:	bunsen-hydrogen

W: 署名照合中にエラーが発生しました。リポジトリは更新されず、過去のインデックスファイルが使われます。GPG エラー: http://pkg.bunsenlabs.org jessie-backports InRelease: 以下の署名が無効です: KEYEXPIRED 1561897138 KEYEXPIRED 1561897138 KEYEXPIRED 1561897138 KEYEXPIRED 1561897138 KEYEXPIRED 1561897138

W: 署名照合中にエラーが発生しました。リポジトリは更新されず、過去のインデックスファイルが使われます。GPG エラー: http://pkg.bunsenlabs.org bunsen-hydrogen InRelease: 以下の署名が無効です: KEYEXPIRED 1561897138 KEYEXPIRED 1561897138 KEYEXPIRED 1561897138 KEYEXPIRED 1561897138 KEYEXPIRED 1561897138

W: http://pkg.bunsenlabs.org/debian/dists/jessie-backports/InRelease の取得に失敗しました  

W: http://pkg.bunsenlabs.org/debian/dists/bunsen-hydrogen/InRelease の取得に失敗しました  

W: http://httpredir.debian.org/debian/dists/jessie-backports/main/binary-amd64/Packages の取得に失敗しました  404  Not Found [IP: 151.101.90.133 80]

W: http://httpredir.debian.org/debian/dists/jessie-backports/contrib/binary-amd64/Packages の取得に失敗しました  404  Not Found [IP: 151.101.90.133 80]

W: http://httpredir.debian.org/debian/dists/jessie-backports/non-free/binary-amd64/Packages の取得に失敗しました  404  Not Found [IP: 151.101.90.133 80]

W: いくつかのインデックスファイルのダウンロードに失敗しました。これらは無視されるか、古いものが代わりに使われます。

　
bunsen-jessie-backports.list

# added by bl-welcome
# BunsenLabs backports
#deb http://pkg.bunsenlabs.org/debian jessie-backports main

　
debian-jessie-backports.list

# added by bl-welcome
# Debian backports
#deb http://httpredir.debian.org/debian jessie-backports main contrib non-free

$ wget -O bunsen-keyring.deb https://eu.pkg.bunsenlabs.org/debian/pool/main/b/bunsen-keyring/bunsen-keyring_2019.01.19%2Bbl9-2_all.deb
$ sudo dpkg -i bunsen-keyring.deb

$ sudo apt dist-upgrade

RubyGem "gdk3" が Linux Mint にインストールできない

Linux Mint 19.3 に gem "gtk3" をインストールしようとしてハマりました。Gem "gdk3" がインストールできない。

正解はここ。

$ sudo apt install libgtk-3-dev

これでした。

RubyGem "gobject-introspection" が Linux Mint にインストールできない

Linux Mint 19.3 に gem "gtk2" をインストールしようとしてハマりました。

Fetching gobject-introspection 3.4.1
Installing gobject-introspection 3.4.1 with native extensions
Gem::Ext::BuildError: ERROR: Failed to build gem native extension.

current directory:
/home/tomoki/Documents/Ruby265/vendor/bundle/ruby/2.6.0/gems/gobject-introspection-3.4.1/ext/gobject-introspection
/home/tomoki/.rbenv/versions/2.6.5/bin/ruby -I
/home/tomoki/.rbenv/versions/2.6.5/lib/ruby/2.6.0 -r
./siteconf20200306-4424-xngtrx.rb extconf.rb
checking for --enable-debug-build option... no
checking for -Wall option to compiler... yes
checking for -Waggregate-return option to compiler... yes
checking for -Wcast-align option to compiler... yes
checking for -Wextra option to compiler... yes
checking for -Wformat=2 option to compiler... yes
checking for -Winit-self option to compiler... yes
checking for -Wlarger-than-65500 option to compiler... yes
checking for -Wmissing-declarations option to compiler... yes
checking for -Wmissing-format-attribute option to compiler... yes
checking for -Wmissing-include-dirs option to compiler... yes
checking for -Wmissing-noreturn option to compiler... yes
checking for -Wmissing-prototypes option to compiler... yes
checking for -Wnested-externs option to compiler... no
checking for -Wold-style-definition option to compiler... yes
checking for -Wpacked option to compiler... yes
checking for -Wp,-D_FORTIFY_SOURCE=2 option to compiler... yes
checking for -Wpointer-arith option to compiler... yes
checking for -Wundef option to compiler... yes
checking for -Wout-of-line-declaration option to compiler... no
checking for -Wunsafe-loop-optimizations option to compiler... yes
checking for -Wwrite-strings option to compiler... yes
checking for Homebrew... no
checking for gobject-introspection-1.0... no
*** extconf.rb failed ***
Could not create Makefile due to some reason, probably lack of necessary
libraries and/or headers.  Check the mkmf.log file for more details.  You may
need configuration options.

Provided configuration options:
	--with-opt-dir
	--without-opt-dir
	--with-opt-include
	--without-opt-include=${opt-dir}/include
	--with-opt-lib
	--without-opt-lib=${opt-dir}/lib
	--with-make-prog
	--without-make-prog
	--srcdir=.
	--curdir
	--ruby=/home/tomoki/.rbenv/versions/2.6.5/bin/$(RUBY_BASE_NAME)
	--enable-debug-build
	--disable-debug-build
	--with-pkg-config
	--without-pkg-config
	--with-override-variables
	--without-override-variables

To see why this extension failed to compile, please check the mkmf.log which can
be found here:

/home/tomoki/Documents/Ruby265/vendor/bundle/ruby/2.6.0/extensions/x86_64-linux/2.6.0/gobject-introspection-3.4.1/mkmf.log

extconf failed, exit code 1

Gem files will remain installed in
/home/tomoki/Documents/Ruby265/vendor/bundle/ruby/2.6.0/gems/gobject-introspection-3.4.1
for inspection.
Results logged to
/home/tomoki/Documents/Ruby265/vendor/bundle/ruby/2.6.0/extensions/x86_64-linux/2.6.0/gobject-introspection-3.4.1/gem_make.out

An error occurred while installing gobject-introspection (3.4.1), and
Bundler cannot continue.
Make sure that `gem install gobject-introspection -v '3.4.1' --source
'https://rubygems.org/'` succeeds before bundling.

In Gemfile:
  gio2 was resolved to 3.4.1, which depends on
    gobject-introspection

　
パッケージがないのかと思って apt-get install してみましたが、

$ sudo apt-get install -y gobject-introspection
パッケージリストを読み込んでいます... 完了
依存関係ツリーを作成しています                
状態情報を読み取っています... 完了
gobject-introspection はすでに最新バージョン (1.56.1-1) です。

という感じ。
　
正解はここにありました。

$ sudo apt install libgirepository1.0-dev

これで OK。

端末を特定のディレクトリで立ち上げる（Ubuntu）

$ gnome-terminal --working-directory=/path/to/dir

Linux の Thunderbird の移行

元のデータ保存先は 922vkyux.default で、これをコピーしてきて続けて使いたい。しかし default-release とか、よくわからないことになっている。

Linux インストール時の .thunderbird/profiles.ini の内容は

[Profile1]
Name=default
IsRelative=1
Path=o2l4hc2s.default
Default=1

[InstallFDC34C9F024745EB]
Default=6scqjmh7.default-release
Locked=1

[Profile0]
Name=default-release
IsRelative=1
Path=6scqjmh7.default-release

[General]
StartWithLastProfile=1
Version=2

こんな感じ。

これをこう書き換えた。

[Profile0]
Name=defaul
IsRelative=1
Path=922vkyux.default
Default=1

[General]
StartWithLastProfile=1
Version=2

これで OK だった。