結果

問題 No.362 門松ナンバー
コンテスト
ユーザー norioc
提出日時 2026-01-04 23:34:56
言語 PyPy3
(7.3.17)
結果
AC  
実行時間 1,932 ms / 3,000 ms
コード長 2,380 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 406 ms
コンパイル使用メモリ 82,944 KB
実行使用メモリ 89,672 KB
最終ジャッジ日時 2026-01-04 23:35:29
合計ジャッジ時間 32,641 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from collections.abc import Iterable
from itertools import product
from functools import cache


def bsearch_right(low: int, high: int, pred) -> int:
    assert pred(high)
    lo = low
    hi = high
    res = high
    while lo <= hi:
        m = (lo + hi) // 2
        if pred(m):
            res = min(res, m)
            hi = m - 1
        else:
            lo = m + 1

    return res


def accum_dp(xs: Iterable, f, op, e, init: dict, *, is_reset=True):
    dp = init.copy()
    for x in xs:
        pp = {} if is_reset else dp.copy()
        dp, pp = pp, dp
        for fm_key, fm_val in pp.items():
            for to_key, to_val in f(fm_key, fm_val, x):
                dp[to_key] = op(dp.get(to_key, e), to_val)

    return dp


def is_kadomatu(a, b, c) -> bool:
    if a == c: return False
    return (a < b > c) or (a > b < c)


def f(k, v, ix):
    p0, p1, lt = k  # (ふたつ前の数字, ひとつ前の数字, 未満か?)
    if lt:
        for d in range(10):
            if is_kadomatu(p0, p1, d):
                yield (p1, d, lt), v
    else:
        i, digit = ix
        for d in range(10):
            if d > digit: continue
            if is_kadomatu(p0, p1, d):
                nlt = d < digit
                yield (p1, d, nlt), v


def op(a, b):
    return a + b


@cache
def digit_dp_unbounded(nd: int) -> int:
    if nd < 3: return 0

    init = {}
    for a, b in product(range(1, 10), range(10)):
        if a != b:
            init[(a, b, True)] = 1

    xs = [(i, 9) for i in range(2, nd)]  # digits は参照しないので数字は何でも良い
    dp = accum_dp(xs, f, op, 0, init)
    return sum(dp.values())


def digit_dp(nd: int, digits: list[int]) -> int:
    if nd < 3 or nd < len(digits):
        return digit_dp_unbounded(nd)

    init = {}
    for a, b in product(range(1, 10), range(10)):
        if a == b: continue
        if [a, b] > [digits[0], digits[1]]: continue

        lt = [a, b] < [digits[0], digits[1]]
        init[(a, b, lt)] = 1

    xs = list(enumerate(digits))
    dp = accum_dp(xs[2:], f, op, 0, init)
    return sum(dp.values())


INF = 1 << 62
T = int(input())
for _ in range(T):
    K = int(input())

    def fn(m: int) -> bool:
        digits = [int(c) for c in str(m)]
        s = sum(digit_dp(i, digits) for i in range(len(digits)+1))
        return s >= K

    res = bsearch_right(0, INF, fn)
    print(res)
0