ABC167

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

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

レッドコーダーが教える、競プロ・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 をメソッド呼び出しに変えてもさほど改善しなかった。

ABC166

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。何ですか、この簡潔さは。

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

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

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

$ sudo apt install blueman

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

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 の内蔵よりよい数値が出ている。

AGC033A

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

ABC165

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

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

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 を立ち上げたら、カラー絵文字が表示されていればよい。💮 💯

ABC162

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。小手先のテクニックだなあ。

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

かしこいなあ。