提出 #61474069

---

ソースコード 拡げる

"""
<方針>
- 明らかに `O(N)` は間に合わない．
- 桁ごとでうまくみていけば，あとは実装力の問題だ．
  - `L~R` という条件が知りたければ，`X` 以下さえ分かる関数 `snake` を求めれば， `snake(R) - snake(L-1)` を求めれば良い．
  - <パターンA> `X` の桁数よりも小さい桁を全部列挙すれば良い．
  - <パターンB> `X` の桁数において，`X` の先頭の数を `X` の実際の先頭の数いかを試せば良い．
  - <パターンC> `X` の桁数において，`X` の先頭も固定した状態で考える．その時，「`X` の先頭の数」進数で考えると良さそう．
"""
# 入力
L, R = map(int, input().split())

def snake(X):
  # L==10の時，L-1==0になるため，その対処
  if X<=9:return 0
  
  # 基本情報
  block = str(X)
  head = int(block[0])
  length = len(block)
  
  # 出力
  ans = 0
  
  ## パターンA
  for i in range(2, length):
    for j in range(1, 10):
      ans += j**(i-1)
  
  ## パターンB
  for i in [length]:
    for j in range(1, head):
      ans += j**(i-1)

  ## パターンC
  tmp = "" # head進数を作る
  fla = True # head<=iを見てないフラグ
  for ind, s in enumerate(block[1:]):
    i = int(s)
    if(head>i and fla):
      tmp += s
    else:
      tmp += str(head-1)
      fla = False
  # head進数の計算
  for i, s in enumerate(reversed(tmp)):
    ans += int(s)*(head**i)
  
  # 「10」のパターンを足す
  ans += 1
  
  # 出力
  return ans

ans = snake(R)-snake(L-1)

print(ans)

提出情報

ジャッジ結果