ABC194F

https://gyazo.com/1a17a7ce598564aed0e289ec0fd8e3cf

考えたこと

サンプルは通ったんだけど遅い、TLEが解消しない

「16通りの数字が既に出てるかどうかを記録」で6万~になり2×10^5回更新するから厳しいよな

公式解説

僕は「何が既に出てるかわからないと、たとえば次に1が出た時に、出現済みの数字の個数が増えるのかどうかわからない」と考えた

それは真

だけど0〜Fの16通りを計算するのだから、どれが出現済みかわからなくても「16個のうちでいくつで出現済み個数が増えるか」はわかる

よって出現済みの数字の個数だけを保持すれば良い

コンテスト後AC

code:py

def solve(N, K):

MOD = 1_000_000_007

D = 16 + 1

equal = 0

for digit in N:

digit = int(digit, 16)

for d in range(D):

if d == 0:

elif d != 16:

for new_digit in range(16):

if new_digit < digit:

new_d = equal

new_d += 1

if new_digit == 0 and equal == 0:

new_d = 0

for d in range(D):

less = new_less

equal += 1

if equal == K:

ret += 1

return ret % MOD