#1055860 (PyPy3) No.319 happy b1rthday 2 me

• 問題: 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

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
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()
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX