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 だった。

キーエンス プログラミング コンテスト 2020

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

A

h, w, n = readlines.map(&:to_i)
puts (n / [h, w].max.to_f).ceil

B

imos法かと思ったが、ちがっていた。

n = gets.to_i
data = n.times.map {gets.split.map(&:to_i)}.map {|x, l| [x - l, x + l]}

result = 0
right_min = -Float::INFINITY

data.sort {|a, b| a[1] <=> b[1]}.each do |arm|
  next if right_min > arm[0]
  result += 1
  right_min = arm[1]
end

puts result

「区間スケジューリング問題」なのだそうである。知らなかった。コードはこれを参考にした。

区間を「終端が早い順」にソートして、とれる順にとる Greedy （貪欲法）で解くことができる

そうである。

C

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

a = Array.new(n)
n.times do |i|
  a[i] = if i < k
    s
  else
    s == 1 ? s + 1 : s - 1
  end
end

puts a.join(" ")

皆んなかしこいなあ。思いつかなかった。K個Sを置いて、あとは残りの部分列でSができないようにすると。

ABC151

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

A

puts gets.chomp.succ

B

n, k, m = gets.split.map(&:to_i)
sum = gets.split.map(&:to_i).inject(&:+)

target = m * n - sum
result = case
         when target < 0 then 0
         when target > k then -1
         else target
         end

puts result

C

'WA' だけの問題はペナルティにカウントされないことになかなか気づかなかった。'AC' が出て初めてカウントしないといけない。

n, m = gets.split.map(&:to_i)
ps = m.times.map {gets.split}

memo = Array.new(n + 1)
penalty_memo = Hash.new(0)
score = penalty = 0

ps.each do |p, s|
  pn = p.to_i    #problem number
  next if memo[pn]
  case s
  when "AC"
    score += 1
    penalty += penalty_memo[pn]
    memo[pn] = true
  else
    penalty_memo[pn] += 1
  end
end

puts "#{score} #{penalty}"    

D

最初はTLE。それから、まさかの Ruby 2.3.3 なのにハマった。
方針がまちがっていた。スタートとゴールを設定して二重ループでやっていたが、よく考えてみたらスタートを設定してあとはいちばん遠いところへ行けばよいのだ。迷路を解くのはBFS。781ms。

class Position
  def initialize(x = 0, y = 0, count = 0)
    @x = x
    @y = y
    @count = count
  end
  attr_reader :x, :y, :count
end

h, w = gets.split.map(&:to_i)
maze = h.times.map {gets.chomp}
field = nil

Position.send(:define_method, :succ) do
  x = @x + 1
  y = @y
  if x >= w
    x = 0
    y += 1
    return false if y >= h
  end
  Position.new(x, y)
end

Position.send(:define_method, :move) do |dir|
  x, y = @x, @y
  dx, dy = [[1, 0], [0, -1], [-1, 0], [0, 1]][dir]
  x += dx
  y += dy
  return false if x >= w || x < 0 || y >= h || y < 0
  return false if field[y][x] != "."
  Position.new(x, y, @count + 1).mark
end

Position.send(:define_method, :mark) do
  field[@y][@x] = "*"
  self
end

solve_maze = ->(start) {
  return 0 if maze[start.y][start.x] == "#"
  field = maze.map(&:dup)
  max = 0
  q = [start.mark]
  while (po = q.shift)
    max = po.count if po.count > max
    4.times do |dir|
      nxt = po.move(dir)
      q << nxt if nxt
    end
  end
  max
}


start = Position.new
max = 0
loop do
  hosuu = solve_maze.(start)
  max = hosuu if hosuu > max
  break unless (start = start.succ)
end

puts max

E

TLE。

LIMIT = 10 ** 9 + 7

def factorial(n)
  result = 1
  2.upto(n) {|i| result *= i}
  result
end

def permutation(a, b)
  [*1..a].last(b).inject(1, &:*)
end
  
def combination(a, b)
  permutation(a, b) / factorial(b)
end


n, k = gets.split.map(&:to_i)
as = gets.split.map(&:to_i).sort
sum = 0

if k == 1
  puts 0
  exit
end

(0..n - k).each do |min|
  (min + k - 1..n - 1).each do |max|
    f = as[max] - as[min]
    sum += f * combination(max - min - 1, k - 2)
  end
end

puts sum % LIMIT

TLE。

LIMIT = 10 ** 9 + 7

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

acc = 1
factorial = [1] + (1..n).map {|i| acc *= i}
factorial_r = factorial.map {|a| Rational(1, a)}
combination = ->(a, b) {factorial[a] * factorial_r[b] * factorial_r[a - b]}

result = 0
(n - k + 1).times {|i| result -= as[i] * combination.(n - i - 1, k - 1)}
as.reverse!
(n - k + 1).times {|i| result += as[i] * combination.(n - i - 1, k - 1)}

puts result.to_i % LIMIT