#1142821 (C++23) No.362 門松ナンバー

• 問題: No.362 門松ナンバー
• ユーザー: norioc
• 提出日時: 2026-01-04 14:00:34
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: TLE
• 実行時間: -
• コード長: 3,863 bytes
• コンパイル時間: 3,799 ms
• コンパイル使用メモリ: 356,928 KB
• 実行使用メモリ: 7,852 KB
• 最終ジャッジ日時: 2026-01-04 14:01:26
• 合計ジャッジ時間: 49,566 ms
• ジャッジサーバーID （参考情報）: judge4 / judge1

ファイルパターン	結果
sample	AC * 3
other	AC * 11 TLE * 8

ソースコード

#include <bits/stdc++.h>
using namespace std;

using int64 = long long;
const int64 INF = (int64)1 << 62;

vector<int> digits;

struct Key {
    int p0, p1;
    bool lt;
    bool operator<(const Key& other) const {
        if (p0 != other.p0) return p0 < other.p0;
        if (p1 != other.p1) return p1 < other.p1;
        return lt < other.lt;
    }
};

bool is_kadomatu(int a, int b, int c) {
    if (a == c) return false;
    return (a < b && b > c) || (a > b && b < c);
}

map<Key, int64> accum_dp(const vector<int>& xs,
                         function<vector<pair<Key,int64>>(const Key&, int64, int)> f,
                         function<int64(int64,int64)> op,
                         int64 e,
                         const map<Key,int64>& init,
                         bool is_reset = true) {
    map<Key,int64> dp = init;
    for (int x : xs) {
        map<Key,int64> pp = is_reset ? map<Key,int64>() : dp;
        dp.swap(pp);
        for (auto& [fm_key, fm_val] : pp) {
            auto nexts = f(fm_key, fm_val, x);
            for (auto& [to_key, to_val] : nexts) {
                dp[to_key] = op(dp.count(to_key) ? dp[to_key] : e, to_val);
            }
        }
    }
    return dp;
}

vector<pair<Key,int64>> f_func(const Key& k, int64 v, int i) {
    vector<pair<Key,int64>> res;
    int p0 = k.p0, p1 = k.p1;
    bool lt = k.lt;
    if (lt) {
        for (int d = 0; d < 10; d++) {
            if (is_kadomatu(p0, p1, d)) {
                res.push_back({Key{p1, d, lt}, v});
            }
        }
    } else {
        for (int d = 0; d < 10; d++) {
            if (d > digits[i]) continue;
            if (is_kadomatu(p0, p1, d)) {
                bool nlt = d < digits[i];
                res.push_back({Key{p1, d, nlt}, v});
            }
        }
    }
    return res;
}

int64 digit_dp(int nd) {
    if (nd < 3) {
        return 0;
    } else if (nd < (int)digits.size()) {
        map<Key,int64> init;
        for (int a = 1; a < 10; a++) {
            for (int b = 0; b < 10; b++) {
                if (a == b) continue;
                init[Key{a, b, true}] = 1;
            }
        }
        vector<int> xs;
        for (int i = 2; i < nd; i++) xs.push_back(i);
        auto dp = accum_dp(
            xs,
            f_func,
            [](int64 a, int64 b){ return a + b; },
            0,
            init
        );
        int64 s = 0;
        for (auto& [_, v] : dp) s += v;
        return s;
    } else {
        map<Key,int64> init;
        for (int a = 1; a < 10; a++) {
            for (int b = 0; b < 10; b++) {
                if (a == b) continue;
                if (make_pair(a, b) > make_pair(digits[0], digits[1])) continue;
                bool lt = make_pair(a, b) < make_pair(digits[0], digits[1]);
                init[Key{a, b, lt}] = 1;
            }
        }
        vector<int> xs;
        for (int i = 2; i < (int)digits.size(); i++) xs.push_back(i);
        auto dp = accum_dp(
            xs,
            f_func,
            [](int64 a, int64 b){ return a + b; },
            0,
            init
        );
        int64 s = 0;
        for (auto& [_, v] : dp) s += v;
        return s;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int64 K;
        cin >> K;
        int64 lo = 0, hi = INF, ans = INF;
        while (lo <= hi) {
            int64 m = (lo + hi) / 2;
            digits.clear();
            for (char c : to_string(m)) digits.push_back(c - '0');
            int64 res = 0;
            for (int i = 0; i <= (int)digits.size(); i++) {
                res += digit_dp(i);
            }
            if (res >= K) {
                ans = min(ans, m);
                hi = m - 1;
            } else {
                lo = m + 1;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}