結果

問題 No.3136 F,B in FizzBuzzString16
コンテスト
ユーザー ID 21712
提出日時 2025-04-28 17:40:44
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 90 ms / 2,000 ms
コード長 3,396 bytes
コンパイル時間 672 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 11,008 KB
最終ジャッジ日時 2025-04-28 17:40:50
合計ジャッジ時間 5,008 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 7
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

#!/bin/python3

# F,B in FizzBuzzString16
# author: Leonardone @ NEETSDKASU

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


# FizzBuzzString16(v)のFとBの個数の合計を求める
def CountFBofFizzBuzzString16(v):
    if v < 1:
        return 0
    
    # 桁の組み合わせの総数
    # DP[桁数][桁の和][F,Bの個数]
    DP = [[[0]*11 for _b in range(150+16)] for _a in range(10)]
    
    # DPの初期値の設定
    b = 0
    c = 0
    for a in range(10):
        d = int(("%010X" % v)[a], 16)
        for t in range(d):
            if t == 0xB:
                DP[a][b+t][c+1] += 1
            else:
                DP[a][b+t][c] += 1
        if d == 0xF or d == 0xB:
            c += 1
        b += d
    DP[9][b][c] += 1
    
    for a in range(9):
        for b in range(150):
            for c in range(10):
                for d in range(0x10):
                    if d == 0xF or d == 0xB:
                        DP[a+1][b+d][c+1] += DP[a][b][c]
                    else:
                        DP[a+1][b+d][c] += DP[a][b][c]
    
    count = 0
    for b in range(1,150):
        for c in range(11):
            if b % 15 == 0:
                count += 2 * DP[9][b][c]
            elif b % 3 == 0:
                count += DP[9][b][c]
            elif b % 5 == 0:
                count += DP[9][b][c]
            else:
                count += c * DP[9][b][c]
    
    return count


# FizzBuzzString16(v)の文字列長を求める
def FizzBuzzString16Length(v):
    if v < 1:
        return 0
    length = 0
    digit_size = 1
    while True:
        lower = pow(16, digit_size-1)
        if lower > v:
            return length
        upper = min(v, lower*16-1)
        
        count15 = (upper // 15) - ((lower-1) // 15)
        count3 = (upper // 3) - ((lower-1) // 3)
        count5 = (upper // 5) - ((lower-1) // 5)
        count = upper - (lower-1)
        
        fizzbuzz = 8 * count15
        fizz = 4 * (count3 - count15)
        buzz = 4 * (count5 - count15)
        hex_number = digit_size * (count - (count3 + count5 - count15))
        
        length += fizzbuzz + fizz + buzz + hex_number
        
        digit_size += 1


# FizzBuzzString16(1000000000000)のv文字目において
#   FizzBuzzString16Length(N - 1) < v <= FizzBuzzString16Length(N)
# となるNを求める
def FindNfromPosition(v):
    lower = 0
    upper = 1000000000001
    while lower + 1 < upper:
        middle = (lower + upper) // 2
        count = FizzBuzzString16Length(middle)
        if count < v:
            lower = middle
        else:
            upper = middle
    return upper


# FizzBuzzString16(1000000000000)の1文字目からv文字目までのFとBの個数の合計を求める
def CountFBtoPosition(v):
    if v < 1:
        return 0
    N = FindNfromPosition(v)
    count = CountFBofFizzBuzzString16(N - 1)
    length = v - FizzBuzzString16Length(N - 1)
    for ch in FizzBuzz16(N)[:length]:
        if ch == 'F' or ch == 'B':
            count += 1
    return count


def solve(X, Y):
    a = CountFBtoPosition(Y)
    b = CountFBtoPosition(X - 1)
    answer = a - b
    return answer


if __name__ == '__main__':
    X = int(input().strip())
    Y = int(input().strip())    
    ans = solve(X,Y)
    print(ans)
0