ABC295 F問題 substr = S

atcoder.jp

求めるのは ですが、式のとおりにを求めてから和の計算をするのは効率が悪いです。
そこで、Sと一致する桁の位置を固定して、それ以外の桁の数を任意とする数のうち、 以上 以下になるのはいくつかを数えて、
これを桁をずらして和をとることを考えます。
以上 以下の範囲の数は、 以下および以下の範囲でそれぞれ数えて、その差から求められます。

例として、 以下の数のうち、 を含む数を考えます。
と一致する桁の位置を変えて和を計算することになりますが、その中で、678901 の桁の部分が と等しくなるケースについて考えてみます。

のより上位の桁は 12345、下位の桁は23456 です。上位の桁が 0～12344 の場合、下位の桁の値にかかわらずより小さな値になるため、条件を満たす個数はです。(の先頭が0の場合、上位の桁は0～ではなく、1～になるため、その分を減らします。)
上位の桁がと同じ12345の数については、それより下位の桁を見る必要があります。(の先頭が0の場合、上位の桁が0のケースは除きます。)
と重なるの桁の数よりが小さければ、より下位の桁にかかわらずより小さな値になるため、条件を満たす個数にを追加し、
逆に大きければ、より下位の桁にかかわらずより大きな値になるため、条件を満たす個数は 0 です。
等しい場合は、より下位の桁で大小が決まります。0～23456 であればR以下の数になるので、条件を満たす個数にを追加します。

コード例 (Julia)

function sum_f(NS, NR, digit_S, digit_R, S0)

  ans = 0

  for digit = 0: digit_R - digit_S    # S より下の桁数

    N1 = 10^digit
    N2 = 10^(digit+digit_S)

    N_low  = mod(NR, N1)              # S より下の桁の数値
    N_cent = div(mod(NR, N2), N1)     # S と重なる桁の数値
    N_up   = div(NR, N2)              # S より上の桁の数値

    if N_up > 0
      if S0
        ans += (N_up - 1) * N1
      else
        ans += N_up * N1
      end
    end

    if S0 && N_up == 0
      continue
    end

    if N_cent > NS
      ans += N1
    elseif N_cent == NS
      ans += N_low + 1
    end
  end

  return(ans)

end  # function solve

function solve()

  # 入力
  readInts() =  parse.(Int,split(readline()))
  readInt()  =  parse(Int,readline())

  T = readInt()

  for t = 1:T

    SS,SL,SR = split(readline())            # 文字列として読み込む

    SL = string(parse(Int,SL) - 1)          # L ==> L-1 に置き換え

    S0 = false                              # S の先頭が 0 かどうか
    if SS[1] == '0'
      S0 = true
    end

    digit_S = length(SS)                    # 桁数
    digit_L = length(SL)
    digit_R = length(SR)

    NS = parse(Int,SS)                      # 整数型へ
    NL = parse(Int,SL)
    NR = parse(Int,SR)

    ans = sum_f(NS, NR, digit_S, digit_R, S0) - sum_f(NS, NL, digit_S, digit_L, S0)

    println(ans)

  end

end

# main
solve()