結果

問題 No.319 happy b1rthday 2 me
ユーザー rpy3cpprpy3cpp
提出日時 2015-12-13 00:29:41
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 31 ms / 2,000 ms
コード長 2,523 bytes
コンパイル時間 333 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 10,752 KB
最終ジャッジ日時 2024-09-15 10:39:27
合計ジャッジ時間 2,300 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

def solve(A, B):
    return count12(B, 12) - count12(A - 1, 12) - corner_case(A, 12)


def corner_case(N, target):
    '''N-1, N の連続部分で 12 を含む場合
    '''
    return str(N)[0] == '2' and str(N - 1)[-1] == '1'


def count12(N, target):
    return count12within(N, target) + count12between(N, target)
    

def count12within(N, target):
    '''0 から　N までの各整数の中に、target (2桁の数値) が何個含まれているかを返す。
    0 から　N までに、7が何個あるか？という問題の解法を、100進数に適用。
    ただし、開始位置をずらして2回計算している。
    '''
    count1 = count12within_core(N, target, 1, 1)
    count2 = count12within_core(N//10, target, 10, (N % 10) + 1)
    return count1 + count2

def count12within_core(N, target, tens, tail):
    unit = 10 ** len(str(target))
    count = 0
    while N:
        N, R = divmod(N, unit)
        if R > target:
            count += tens
        elif R == target:
            count += tail
        count += N * tens
        tail += R * tens
        tens *= unit
    return count

def count12between(N, target):
    '''0 から　N までの整数をつなげた数値のうち、２つの数値をまたいで12が何個含まれているかを返す。
    当該の２つの数値を m, m+1　とすると、m の末尾は1で、m+1 の先頭は2となる。
    このようなケースは、m が 1桁ならば、1, 2 のみ。
    m が 2桁ならば、21, 22 のみ。
    m が 3桁ならば、2x1, 2x2 が該当し、x=0..9 までの10個があり得る。
    m が 4桁ならば、2xy1, 2xy2 が該当し、xy = 00..99 までの100個があり得る。
    N が k 桁の場合は、(k-1)桁までの該当数の和 = 1 + sum(10**(i-1) for i in range(1, k))
    および、
    k桁目の数値が　1ならば、 + 0
    k桁目の数値が　2ならば、 (N % (10**k))//10 + (1 if (N % 10) >= 2 else 0)
    k桁目の数値が　3以上ならば、10**(k-2)
    を足した数となる。
    '''
    if N < 2:
        return 0
    if N < 22:
        return 1
    if N < 100:
        return 2
    k = len(str(N))
    head, tail = divmod(N, 10**(k - 1))
    count = 1 + sum(10**i for i in range(k - 2))    
    if head == 1:
        return count
    elif head == 2:
        count += tail // 10
        if (tail % 10) >= 2:
            count += 1
        return count
    else:
        return count + 10**(k - 2)


A, B = map(int, input().split())
print(solve(A, B))
0