ABC174

AtCoder Ruby

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

A: Air Conditioner

x = gets.to_i
puts (x >= 30) ? "Yes" : "No"

B: Distance

n, d = gets.split.map(&:to_i)
coordinates = n.times.map {gets.split.map(&:to_i)}

puts coordinates.count {|x, y| x * x + y * y <= d * d}

2020-05-17

ABC167

AtCoder Ruby

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

A: Registration

s = gets.chomp
t = gets.chomp

puts (t[0..-2] == s) ? "Yes" : "No"

B: Easy Linear Programming

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

score = 0

if a <= k
  score += a
  k -= a
  if b <= k
    k -= b
    if c <= k
      score -= c
    else
      score -= k
    end
  end
else
  score += k
end

puts score

C: Skill Up

全探索なのだけれど、ちょっと自信がなかった。一発で通ってホッ。

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

min = 1200001

(1..n).each do |i|
  books.combination(i) do |selected|
    cost = 0
    f = selected.map {|price, *up|
      cost += price
      up
    }.transpose.map(&:sum).all? {_1 >= x}
    if f
      min = cost if cost < min
    end
  end
end

puts (min == 1200001) ? -1 : min

D: Teleporter

これは考えた。エッジケースがむずかしかった。

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

teleport = [1]
visited = Array.new(200001)
visited[1] = true

now = 1
while true
  nxt = destinations[now - 1]
  teleport << nxt
  break if visited[nxt]
  visited[nxt] = true
  now = nxt
end

idx = teleport.index(nxt)
ts = teleport.size
ans = if k < ts
        teleport[k]
      else
        loop_size = ts - idx - 1
        teleport[(k - idx) % loop_size + idx]
      end

puts ans

2020-05-07

Rubyで「分野別初中級者が解くべき過去問精選100問」を解く

Ruby

レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】 - Qiita
　
全探索：全列挙

ITP1_7_B - How Many Ways?

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_7_B&lang=ja

loop do
  n, x = gets.split.map(&:to_i)
  break if (n + x).zero?
  
  count = 0
  [*1..n].combination(3) do |given|
    count += 1 if given.inject(:+) == x
  end
  
  puts count
end

AtCoder Beginner Contest 106 B - 105

https://atcoder.jp/contests/abc106/tasks/abc106_b

n = gets.to_i

puts 1.step(n, 2).map {|i|
       (1..i).select {|x| (i % x).zero?}.size == 8
     }.count(true)

AtCoder Beginner Contest 122 B - ATCoder

https://atcoder.jp/contests/abc122/tasks/abc122_b

str = gets.chomp
result = str.split(/[^ACGT]/).map(&:size).max
puts result || 0

　
全列挙で解いてみる。

s = gets.chomp

max = 0

doit = ->(str) {
  return if str.empty?
  (str.length).downto(1) do |l|
    next if /[^ACGT]/.match(str[0, l])
    max = l if l > max
  end
  doit.(str[1..-1])
}
doit.(s)

puts max

パ研杯2019 C - カラオケ

https://atcoder.jp/contests/pakencamp-2019-day3/tasks/pakencamp_2019_day3_c

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

puts [*0...m].combination(2).map {|t1, t2|
       n.times
        .map {|student| [table[student][t1], table[student][t2]].max}
        .inject(:+)
     }.max

　
全探索：工夫して通り数を減らす全列挙

AtCoder Beginner Contest 095 C - Half and Half

https://atcoder.jp/contests/abc095/tasks/arc096_a

a, b, ab, x, y = gets.split.map(&:to_i)

z = [x, y].max * 2
puts 0.step(z, 2).map {|n_ab|
       n_a = [x - n_ab / 2, 0].max
       n_b = [y - n_ab / 2, 0].max
       a * n_a + b * n_b + ab * n_ab
     }.min

三井住友信託銀行 プログラミングコンテスト 2019 D - Lucky PIN

https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_d

require "set"

gets
s = gets.chomp.chars

pool = Set.new
s.combination(3) {|code| pool << code.join}

puts pool.size

予想どおり TLE。

考え直す。

gets.to_i
str = gets.chomp

is_included = ->(i) {
  pointer = 0
  table = sprintf("%03d", i).chars
  str.each_char do |c|
    if c == table[pointer]
      pointer += 1
      return true if pointer == 3
    end
  end
  false
}

puts (0..999).map {|i| is_included.(i)}.count(true)

TLE。

考え直す。

n = gets.to_i
str = gets.chomp

check = Array.new(1000, 0)

0.upto(n - 3) do |i|
  (i + 1).upto(n - 2) do |j|
    (j + 1).upto(n - 1) do |k|
      num = (str[i] + str[j] + str[k]).to_i
      check[num] = 1
    end
  end
end

puts check.inject(:+)

TLE。

他の人の答えを見た。すごい工夫だな。たった 8ms。

n = gets.to_i
s = gets.chomp

puts [*"0".."9"].repeated_permutation(3).count {|i, j, k|
       (a = s.index(i, 0)) && (b = s.index(j, a + 1)) && s.index(k, b + 1)
     }

でも、よく考えたらこれ、is_included を使う解法とアルゴリズムは一緒じゃないか。Ruby の組み込みを使うかどうかだけだな。
　

JOI 2007 本選 3 - 最古の遺跡

n = gets.to_i
pillars = n.times.map {gets.split.map(&:to_i)}

max = 0

pillars.combination(2) do |p1, p2|
  vy = p2[0] - p1[0]
  vx = p1[1] - p2[1]
  calc = ->(x, y) {
    return false unless pillars.include?([p1[0] + x, p1[1] + y])
    return false unless pillars.include?([p2[0] + x, p2[1] + y])
    x * x + y * y
  }
  area = calc.(vx, vy)
  max = area if area && area > max
  area = calc.(-vx, -vy)
  max = area if area && area > max
end

puts max

TLE。Ruby では正解者なし。

高速化。

n = gets.to_i
pillars_str = n.times.map {gets.chomp}

max = 0
pillars = pillars_str.map {|pl| pl.split.map(&:to_i)}

pillars.combination(2) do |p1, p2|
  vy = p2[0] - p1[0]
  vx = p1[1] - p2[1]
  calc = ->(x, y) {
    return false unless pillars_str.include?("#{p1[0] + x} #{p1[1] + y}")
    return false unless pillars_str.include?("#{p2[0] + x} #{p2[1] + y}")
    x * x + y * y
  }
  area = calc.(vx, vy)
  max = area if area && area > max
  area = calc.(-vx, -vy)
  max = area if area && area > max
end

puts max

3/10 AC だったのが、6/10 AC に改善された。でもやはり TLE。
lambda をメソッド呼び出しに変えてもさほど改善しなかった。

2020-05-07

ABC166

AtCoder Ruby

https://atcoder.jp/contests/abc166
　

A: A?C

puts (gets.chomp == "ABC") ? "ARC" : "ABC"

B: Trick or Treat

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

sunuke = Array.new(n, 0)
k.times do
  gets
  gets.split.each {|a| sunuke[a.to_i - 1] += 1}
end

puts sunuke.count(0)

C: Peaks

できた。うれしい。

n, m = gets.split.map(&:to_i)
heights = [0] + gets.split.map(&:to_i)

graph = Array.new(n + 1) {[]}
m.times do
  a, b = gets.split.map(&:to_i)
  graph[a] << b
  graph[b] << a
end

visited = Array.new(n + 1)
count = 0

dfs = ->(node) {
  return if visited[node]
  visited[node] = true
  highest = graph[node].map {|nxt| heights[nxt]}.max
  count += 1 if !highest || heights[node] > highest
  graph[node].each {|child| dfs.(child)}
}

(1..n).each do |node|
  next if visited[node]
  dfs.(node)
end

puts count

321ms。

しかし、かしこい人たちがいる。

n, m = gets.split.map(&:to_i)
heights = [0] + gets.split.map(&:to_i)

f = Array.new(n + 1, 1)
f[0] = 0

m.times do
  a, b = gets.split.map(&:to_i)
  f[a] = 0 if heights[a] <= heights[b]
  f[b] = 0 if heights[b] <= heights[a]
end

puts f.sum

166ms。何ですか、この簡潔さは。

2020-05-05

Ubuntu でロジクールの Bluetoothマウス M557 を使う

Linux

ペアリングしても、再起動すると自動で再接続しなくなってしまう。

解決策：
blueman をインストールする。

$ sudo apt install blueman

Ubuntu 19.10 と18.04 LTS で確認済。
　
※参考
https://forums.ubuntulinux.jp/viewtopic.php?id=17539

2020-05-05

Linux でディスクアクセス速度を測定する

Linux

SSD のアクセス速度を測ってみた。メイン機の VAIO の外付け。下は VAIO 内臓の HDD で、これと比較する。

$ sudo hdparm -tT /dev/sdb

/dev/sdb:
 Timing cached reads:   13626 MB in  1.99 seconds = 6839.35 MB/sec
 Timing buffered disk reads: 1182 MB in  3.00 seconds = 393.49 MB/sec
$ sudo hdparm -tT /dev/sda

/dev/sda:
 Timing cached reads:   13208 MB in  1.99 seconds = 6628.43 MB/sec
 Timing buffered disk reads: 332 MB in  3.01 seconds = 110.32 MB/sec

やはり速い。

いまサブ機にしている ThinkPad L560 の内蔵 HDD が、結構速く感じるのだが。外付け HDD と比較する。

$ sudo hdparm -tT /dev/sda

/dev/sda:
 Timing cached reads:   10978 MB in  1.99 seconds = 5511.74 MB/sec
 Timing buffered disk reads: 362 MB in  3.01 seconds = 120.18 MB/sec
tomoki@tomoki-ThinkPad-L560:~$ sudo hdparm -tT /dev/sdb

/dev/sdb:
 Timing cached reads:   10330 MB in  1.99 seconds = 5185.40 MB/sec
 Timing buffered disk reads: 252 MB in  3.02 seconds =  83.40 MB/sec

これもやはり、結構速い。VAIO の内蔵よりよい数値が出ている。

2020-05-05

AGC033A

AtCoder Ruby

A - Darker and Darker
　

TLE のコード

H, W = gets.split.map(&:to_i)
$field = H.times.map {gets.chomp}

Area = W * H

class Step
  @@count = 0
  @@max_step = 0

  def initialize(x, y, step = 0)
    @x = x
    @y = y
    @step = step

    @@count += 1
    @@max_step = step if step > @@max_step
  end

  def dir(i)
    dx, dy = [[1, 0], [0, -1], [-1, 0], [0, 1]][i]
    x = @x + dx
    y = @y + dy
    if x < 0 || x >= W || y < 0 || y >= H
      nil
    else
      ($field[y][x] == ".") ? Step.new(x, y, @step + 1) : nil
    end
  end

  def set
    $field[@y][@x] = "#"
    self
  end

  def self.last?
    @@count >= Area
  end

  def self.number
    @@max_step
  end
end


q = []

H.times do |y|
  W.times {|x| q << Step.new(x, y) if $field[y][x] == "#"}
end

until Step.last?
  now = q.shift
  4.times do |i|
    nxt = now.dir(i)
    q << nxt.set if nxt
  end
end

puts Step.number

Pythonコードの例

https://atcoder.jp/contests/agc033/submissions/12504219
numpyを使っている。

import numpy as np
h,w=map(int,input().split())
field=[list(input()) for i in range(h)]
field=[[0 if field[j][i]=='#' else h+w for i in range(w)]for j in range(h)]
field=np.array(field)
for i in range(1,h):
  field[i,:]=np.minimum(field[i,:],field[i-1,:]+1)
for i in range(h-1,0,-1):
  field[i-1,:]=np.minimum(field[i,:]+1,field[i-1,:])
for i in range(1,w):
  field[:,i]=np.minimum(field[:,i],field[:,i-1]+1)
for i in range(w-1,0,-1):
  field[:,i-1]=np.minimum(field[:,i]+1,field[:,i-1])
print(np.max(field))

NArrayを使って移植

require "numo/narray"
include Numo

h, w = gets.split.map(&:to_i)
a = h.times.map {gets.chomp.chars.map {|e| e == "#" ? 0 : h + w}}

field = Int16.cast(a)

1.upto(h - 1) do |i|
  a = field[i, true]
  b = field[i - 1, true] + 1
  a[a > b] = b[a > b]
end

(h - 1).downto(1) do |i|
  a = field[i, true] + 1
  b = field[i - 1, true]
  b[a < b] = a[a < b]
end

1.upto(w - 1) do |i|
  a = field[true, i]
  b = field[true, i - 1] + 1
  a[a > b] = b[a > b]
end

(w - 1).downto(1) do |i|
  a = field[true, i] + 1
  b = field[true, i - 1]
  b[a < b] = a[a < b]
end

puts field.max

a[a > b] = b[a > b]は、aでbより大きいところをbで置き換える（aとbの小さい方がaに入る）。これはビューなので、もとのfieldも変化する。

※参考
NArrayの簡単なつかい方 - Qiita
Numo::NArray Overview (Japanese) · ruby-numo/numo-narray Wiki · GitHub

2020-05-02

ABC165

AtCoder Ruby

https://atcoder.jp/contests/abc165
30分くらい時間が経ってから始めた。A, B, C 3完。
　

A: We Love Golf

gets.to_i
a, b = gets.split.map(&:to_i)
 
if (a % k).zero?
  puts "OK"
else
  i = (a / k + 1) * k
  puts i <= b ? "OK" : "NG"
end

B: 1%

x = gets.to_i
 
y = 1
tmp = 100
 
loop do
  tmp = (tmp * 1.01).to_i
  break if tmp >= x
  y += 1
end
 
puts y

C: Many Requirements

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

maximum = 0

[*1..m].repeated_combination(n) do |seq|
  score = 0
  set.each do |a, b, c, d|
    score += d if seq[b - 1] - seq[a - 1] == c
  end
  maximum = [maximum, score].max
end

puts maximum

遅くなるけれどこうも書ける。

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

maximum = 0

[*1..m].repeated_combination(n) do |seq|
  score = set.select {|a, b, c, d| seq[b - 1] - seq[a - 1] == c}.sum {_4}
  maximum = [maximum, score].max
end

puts maximum

2020-04-18

Ubuntu の Google Chrome でカラー絵文字を表示させる

Linux

Ubuntu は 18.04 LTS から「Noto Color Emoji」がインストールされている筈。

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

しかし、Ubuntu 19.10 でも自分の環境では Chrome でカラー絵文字が出ない。Firefox ではちゃんと出る。

対策は以下にありました。
Linuxで絵文字フォントを利用する(Ubuntu18.04 LTS/その他ディストリビューション) - Qiita

まず、

$ mkdir -p ~/.config/fontconfig/conf.d
$ touch ~/.config/fontconfig/conf.d/50-noto-color-emoji.conf

で、fonts.conf を作る。そしてこの 50-noto-color-emoji.conf ファイルの中身だが、リンク先のようでもいいし、自分はここの方を使った。

<?xml version="1.0"?>
<!DOCTYPE fontconfig SYSTEM "fonts.dtd">
<fontconfig>
  <alias>
    <family>sans-serif</family>
    <prefer>
      <family>Noto Color Emoji</family>
    </prefer>
  </alias>
  <alias>
    <family>monospace</family>
    <prefer>
      <family>Noto Color Emoji</family>
    </prefer>
  </alias>
</fontconfig>

　
そして、font キャッシュを更新する。

$ fc-cache -f

　
これで Chrome を立ち上げたら、カラー絵文字が表示されていればよい。💮 💯

2020-04-17

ABC162

AtCoder Ruby

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

A: Lucky 7

n = gets.chomp
puts n.include?("7") ? "Yes" : "No"

B: FizzBuzz Sum

n = gets.to_i
result = 0

(1..n).each do |i|
  next if i % 3 == 0 || i % 5 == 0
  result += i
end

puts result

C: Sum of gcd of Tuples (Easy)

とりあえずメモ化してみた。

def gcd(a, b, c)
  a.gcd(b).gcd(c)
end

k = gets.to_i
memo = {}
sum = 0

(1..k).each do |a|
  (1..k).each do |b|
    (1..k).each do |c|
      ary = [a, b, c].sort
      if memo[ary]
        sum += memo[ary]
      else
        n = gcd(a, b, c)
        memo[ary] = n
        sum += n
      end
    end
  end
end

puts sum

これでは全然ダメ。
少し工夫してみる。

k = gets.to_i
sum = 0

(1..k).each do |a|
  (a..k).each do |b|
    (b..k).each do |c|
      case
      when a == b && b == c
        sum += a
      when a == b
        sum += b.gcd(c) * 3
      when b == c
        sum += c.gcd(a) * 3
      when c == a
        sum += a.gcd(b) * 3
      else
        sum += a.gcd(b).gcd(c) * 6
      end
    end
  end
end

puts sum

これで 265ms で AC だった。
　

D: RGB Triplets

とりあえず単純にやってみる。

n = gets.to_i
s = gets.chomp

if n < 3
  puts 0
else
  count = 0
  (0...n).each do |i|
    (i + 1...n).each do |j|
      (j + 1...n).each do |k|
        next if j - i == k - j
        if s[i] != s[j] && s[j] != s[k] && s[k] != s[i]
          count += 1
        end
      end
    end
  end
  puts count
end

これはあっさり TLE。
解説を見る。結構いいところまでいっていたようだった。

n = gets.to_i
s = gets.chomp

r = g = b = 0

s.each_char do |c|
  case c
  when "R" then r += 1
  when "G" then g += 1
  when "B" then b += 1
  end
end

result = r * g * b

(0...n).each do |i|
  (i + 1...n).each do |j|
    k = 2 * j - i
    next if k < 0 || k >= n
    if s[i] != s[j] && s[j] != s[k] && s[k] != s[i]
      result -= 1
    end
  end
end

puts result

しかしこれも一つだけ TLE。ループを while 文に変更してみる。

n = gets.to_i
s = gets.chomp

result = s.count("R") * s.count("G") * s.count("B")

n.times do |i|
  j = i + 1
  while j < n
    k = 2 * j - i
    if j < k && k < n && s[i] != s[j] && s[j] != s[k] && s[k] != s[i]
      result -= 1
    end
    j += 1
  end
end

puts result

1810ms で AC。小手先のテクニックだなあ。