D - 2020に似た数

c.rb

=begin
2020のように、ある文字列の2回以上の繰り返しとして表せる自然数を「2020に似た数」と呼ぶことにします。
Q個のクエリA_iとB_iが入力されたとき、A_iからB_iまでに2020に似た数が何個含まれるか求めなさい。

制約
1≦Q≦1e+5
1≦A_i≦B_i≦1e+5

入力
Q
A_1 B_1
...
A_Q B_Q
=end

Query = Struct.new(:a, :b)

q = gets.to_i

a_min = 100000
b_max = 0

queries = q.times.map {
  a, b = gets.split.map &:to_i
  a_min = [a, a_min].min
  b_max = [b, b_max].max
  Query[a, b]
}

# O(|s|): 繰り返しを検出
def check_repetition(s)
  n = 0 # 繰り返しの長さ
  is_repeating = s.each_char.with_index.inject(false) { |prev, (c, j)|
    if prev and c == s[j % n]
      true
    elsif c == s[0]
      n = [1, j].max
      true
    else
      false
    end
  }
  is_repeating and s.size % n == 0 and s.size > n
end

# O(N): 累積和を求める
count_sums = [0] # 最初は番兵
(a_min..b_max).each { |n|
  count_sum = count_sums.last
  count_sum += 1 if check_repetition n.to_s
  count_sums << count_sum
}

# O(Q): 累積和から区間の総和を計算する
queries.each { |query|
  puts count_sums[query.b - a_min + 1] - count_sums[query.a - a_min]
}