結果

問題 No.319 happy b1rthday 2 me
ユーザー lam6er
提出日時 2025-03-20 20:39:22
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 61 ms / 2,000 ms
コード長 3,915 bytes
コンパイル時間 307 ms
コンパイル使用メモリ 82,580 KB
実行使用メモリ 67,288 KB
最終ジャッジ日時 2025-03-20 20:39:29
合計ジャッジ時間 3,282 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

def count_internal(s):
    if s == "-1":
        return 0
    digits = list(map(int, s))
    n = len(digits)
    from collections import defaultdict

    # DP[i][is_tight][prev_digit] = (total_count, num_count)
    dp = [defaultdict(lambda: defaultdict(lambda: (0, 0))) for _ in range(n + 1)]
    # Initialize with 0 digits, tight=True, prev_digit=None, (count=0, num=1)
    dp[0][True][None] = (0, 1)
    
    for pos in range(n):
        current_digit = digits[pos]
        for is_tight in [True, False]:
            for prev_d in list(dp[pos][is_tight].keys()):
                current_count, current_num = dp[pos][is_tight][prev_d]
                # Determine the maximum digit we can choose at current position
                max_d = current_digit if is_tight else 9
                for d in range(0, max_d + 1):
                    new_is_tight = is_tight and (d == max_d)
                    # Update new_prev_d (if previous was None and this is the first digit)
                    if prev_d is None:
                        if d == 0 and pos == 0:
                            # Still leading zero, prev remains None
                            new_prev = None
                        else:
                            new_prev = d
                    else:
                        new_prev = d
                    # Calculate additional count
                    add_count = 0
                    if prev_d is not None:
                        if prev_d == 1 and d == 2:
                            add_count = current_num
                    new_total_count = current_count + add_count
                    new_num_count = current_num
                    # Update the next state
                    new_prev_key = new_prev
                    entry = dp[pos + 1][new_is_tight]
                    prev_total, prev_num = entry.get(new_prev_key, (0, 0))
                    entry[new_prev_key] = (prev_total + new_total_count, prev_num + new_num_count)
    
    total = 0
    for is_tight in [True, False]:
        for key in dp[n][is_tight]:
            cnt, num = dp[n][is_tight][key]
            total += cnt
    return total

def compute_part2(a_plus_1, b):
    a_plus_1 = max(a_plus_1, 1)  # m must be >=1 since m >= A+1 could be 0 but m starts from 2
    max_k = len(str(b)) if b !=0 else 1
    total =0
    for k in range(1, max_k +1):
        lower = 2 * 10 ** (k-1)
        upper = 3 * 10 ** (k-1) -1
        actual_lower = max(lower, a_plus_1)
        actual_upper = min(upper, b)
        if actual_lower > actual_upper:
            continue
        # Now find the numbers between actual_lower and actual_upper with last digit 2
        # and check if they start with 2 (which they do because of lower and upper)
        # last digit must be 2
        # Compute start and end in [actual_lower, actual_upper] where last digit is 2
        start = actual_lower
        if start %10 !=2:
            start = start + (2 - start %10) %10
            if start < actual_lower:
                start +=10
        if start > actual_upper:
            continue
        end = actual_upper
        if end %10 !=2:
            end = end - ( (end %10 -2) %10 )
            if end < actual_lower:
                continue
        if end < start:
            continue
        # Now count the numbers from start to end inclusive with step 10
        count = ((end - start) //10) +1
        total += count
    return total

def main():
    A, B = map(int, input().split())
    # Part 1: Internal occurrences from A to B
    # Compute f(B) - f(A-1)
    def f(x):
        return count_internal(str(x)) if x >=0 else 0
    part1 = f(B) - f(A-1)
    # Part 2: m = n+1, where n is from A to B-1 inclusive, n ends with 1, m starts with 2
    # m is from (A+1) to B, inclusive. m must be of form: starts with 2, ends with 2
    part2 = compute_part2(A +1, B)
    print(part1 + part2)

if __name__ == "__main__":
    main()
0