結果

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

ソースコード

diff #
raw source code 

from collections.abc import Iterable
from itertools import product


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, i):
    global digits
    p0, p1, lt = k
    if lt:
        for d in range(10):
            if is_kadomatu(p0, p1, d):
                yield (p1, d, lt), v
    else:
        for d in range(10):
            if d > digits[i]: continue
            if is_kadomatu(p0, p1, d):
                nlt = d < digits[i]
                yield (p1, d, nlt), v


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


def digit_dp(nd: int) -> int:
    global digits

    if nd < 3:
        return 0
    elif nd < len(digits):
        init = {}
        for a, b in product(range(1, 10), range(10)):
            if a == b: continue
            init[(a, b, True)] = 1

        dp = accum_dp(range(2, nd), f, op, 0, init)
        return sum(dp.values())
    else:
        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

        dp = accum_dp(range(2, len(digits)), f, op, 0, init)
        return sum(dp.values())


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

    lo = 0
    hi = INF
    ans = INF
    while lo <= hi:
        m = (lo + hi) // 2
        digits = [int(c) for c in str(m)]
        res = 0
        for i in range(len(digits)+1):
            res += digit_dp(i)

        if res >= K:
            ans = min(ans, m)
            hi = m - 1
        else:
            lo = m + 1

    print(ans)
0