結果
| 問題 | No.3136 F,B in FizzBuzzString16 |
| コンテスト | |
| ユーザー |
 LyricalMaestro
|
| 提出日時 | 2026-07-05 03:12:46 |
| 言語 | PyPy3 (7.3.17) |
| 結果 |
AC
|
| 実行時間 | 101 ms / 2,000 ms |
| コード長 | 5,267 bytes |
| 記録 | |
| コンパイル時間 | 519 ms |
| コンパイル使用メモリ | 95,984 KB |
| 実行使用メモリ | 85,072 KB |
| 最終ジャッジ日時 | 2026-07-05 03:13:01 |
| 合計ジャッジ時間 | 5,200 ms |
|
ジャッジサーバーID （参考情報） |
judge2_0 / judge3_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 7 |
| other | AC * 32 |
ソースコード
# https://yukicoder.me/problems/no/3136
def FizzBuzz16(i):
if i % 15 == 0:
return "FizzBuzz"
elif i % 3 == 0:
return "Fizz"
elif i % 5 == 0:
return "Buzz"
else:
return "%X" % i
def solve_(n):
# 3の倍数の数を計算
n3 = n // 3
# 5の倍数の数を計算
n5 = n // 5
# nについて16進数で表現してみる
n_digits = []
while n > 0:
n_digits.append(n % 16)
n //= 16
n_digits.reverse()
# n以下の16進値の計算
dp_count = [[[0] * 15 for _ in range(2)] for _ in range(2)]
dp_count[0][0][0] = 1
dp_length = [[[0] * 15 for _ in range(2)] for _ in range(2)]
for m in n_digits:
new_dp_count = [[[0] * 15 for _ in range(2)] for _ in range(2)]
new_dp_length = [[[0] * 15 for _ in range(2)] for _ in range(2)]
for less in range(2):
for leader_zero in range(2):
for mod15 in range(15):
count = dp_count[less][leader_zero][mod15]
legnth = dp_length[less][leader_zero][mod15]
if less == 0:
for l in range(m + 1):
new_leader_zero = (0 if l == 0 and leader_zero == 0 else 1)
if new_leader_zero == 0:
new_less = 1
else:
new_less = (1 if l < m else 0)
new_mod15 = (l + mod15) % 15
new_dp_count[new_less][new_leader_zero][new_mod15] += count
if new_leader_zero == 1:
new_dp_length[new_less][new_leader_zero][new_mod15] += legnth + count
else:
for l in range(16):
new_leader_zero = (0 if l == 0 and leader_zero == 0 else 1)
new_less = 1
new_mod15 = (l + mod15) % 15
new_dp_count[new_less][new_leader_zero][new_mod15] += count
if new_leader_zero == 1:
new_dp_length[new_less][new_leader_zero][new_mod15] += legnth + count
dp_count = new_dp_count
dp_length = new_dp_length
ans_length = 4 * (n3 + n5)
for less in range(2):
for mod15 in range(15):
if mod15 % 3 != 0 and mod15 % 5 != 0:
ans_length += dp_length[less][1][mod15]
return ans_length
def solve2(N):
# NについてFの数+Bの数がどれくらいあるか調べる
# 3の倍数の数を計算
n3 = N // 3
# 5の倍数の数を計算
n5 = N // 5
# nについて16進数で表現してみる
n_digits = []
while N > 0:
n_digits.append(N % 16)
N //= 16
n_digits.reverse()
dp_count = [[0] * 15 for _ in range(2)]
dp_count[0][0] = 1
dp_score = [[0] * 15 for _ in range(2)]
for m in n_digits:
new_dp_count = [[0] * 15 for _ in range(2)]
new_dp_score = [[0] * 15 for _ in range(2)]
for less in range(2):
for mod15 in range(15):
count = dp_count[less][mod15]
score = dp_score[less][mod15]
if less == 0:
for l in range(m + 1):
new_less = (1 if l < m else 0)
new_mod15 = (l + mod15) % 15
new_dp_count[new_less][new_mod15] += count
if l in (11, 15):
new_dp_score[new_less][new_mod15] += score + count
else:
new_dp_score[new_less][new_mod15] += score
else:
for l in range(16):
new_less = 1
new_mod15 = (l + mod15) % 15
new_dp_count[new_less][new_mod15] += count
if l in (11, 15):
new_dp_score[new_less][new_mod15] += score + count
else:
new_dp_score[new_less][new_mod15] += score
dp_count = new_dp_count
dp_score = new_dp_score
answer = n3 + n5
for less in range(2):
for mod15 in range(15):
if mod15 % 3 != 0 and mod15 % 5 != 0:
answer += dp_score[less][mod15]
return answer
def solve(Y):
# 長さがY以上になるようなNの最小値をもとめる
low = 1
high = Y
while high - low > 1:
mid = (high + low) // 2
if solve_(mid) >= Y:
high = mid
else:
low = mid
if solve_(low) >= Y:
N = low
else:
N = high
x = FizzBuzz16(N)
length = solve_(N)
# print(N, length, x)
y = Y - (length - len(x))
x0 = x[:y]
answer = solve2(N - 1)
for x in x0:
if x in ("F", "B"):
answer += 1
return answer
def main():
X = int(input())
Y = int(input())
ans = solve(Y)
if X > 1:
ans -= solve(X - 1)
print(ans)
if __name__ == "__main__":
main()