ARC 173

Sun, Mar 16, 2025

A. Neq Number

https://atcoder.jp/contests/arc173/tasks/arc173_a

$x$ 以下の Neq Number の個数を求める関数を書いて二分探索すれば良いという方針は立ったが実装に手間取った。結局うまく実装できず解説を読んだり解説放送を見たが詳細な実装方法については触れておらず結局自分で考えた。

$f(x)$ を $x$ 以下の Neq Number の個数とする。$f(x) = K$ となる最小の $x$ が求める答えとなる。 $f(x)$ は広義単調増加関数であるから二分探索で答えを求めることができる。

$d$ 桁の Neq Number の個数を考える。左の桁を 0 桁目とすると 0 桁目は 1 から 9 までの 9 通りである。 $i > 0$ 桁目の数は 0~9 の10通りのうち $i-1$ 桁目とは異なる数であるであるから 9 通りである。よって $d$ 桁の Neq Number の個数は $9^{d}$ 通りである。

$f(x)$ の実装について考える。

$x$ が1桁のとき

$f(x) = x$ である。

$x$ が $d$ 桁のとき

まず $d$ 桁未満の Neq Number の個数は $\sum_{k=1}^{d-1} 9^{k}$ である。

$x = a_0 a_1 \cdots a_{d-1}$ とかけたとする。 leading number が $a_0$ 未満の数は明らかに $x$ 未満であるから、そのような場合の Neq Number の個数は $(a_0 - 1) \times 9^{d-1}$ である。

$a_0 \times 10^{d-1}$ 以上 $x$ 未満の Neq Number の個数を考える。 $0 \sim i-1$ 桁目までの数は $x$ と同じで、$i$ 桁目の数が $0$ 以上 $a_i$ 未満のときの Neq Number の個数は

$a_{i-1} \geq a_i$ のとき $a_i \times 9^{d-i-1}$ 通り
$a_{i-1} < a_i$ のとき $(a_i-1) \times 9^{d-i-1}$ 通り
- $a_{i-1} = a_i$ のときの分を引いているのが $a_{i-1} \geq a_i$ のときとの違い

これを $i=1$ から順に足し合わせていくことで $a_0 \times 10^{d-1}$ 以上 $x$ 未満の Neq Number の個数が求まる。ただし、$a_{i-1} = a_i$ になったらそこで処理を止める。

最後に $x$ が Neq Number であれば更に 1 を足す。

ll intpow(ll x, ll n) {
    long long ret = 1;
    while (n > 0) {
        if (n & 1)
            ret *= x;
        x *= x;
        n >>= 1;
    }
    return ret;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    auto f = [](auto f, ll x) -> ll {
        string s = to_string(x);
        int n = s.size();

        if (n == 1)
            return x;

        ll ans = 0;
        // n 桁未満の neq number の数
        rep2(i, 1, n) {
            ans += intpow(9, i);
        }

        // leading number が s[0] 未満場合の数
        ans += (ll)((s[0] - '0') - 1) * intpow(9, n - 1);

        // (s[0] - '0') * intpow(10,n-1) 以上、x 未満の neq number の個数
        // s[0] ~ s[i-1] までの数字は s と同じで、i 番目の文字が s[i] 未満の数字のうち neq number になる個数
        rep2(i, 1, n) {
            ans += (ll)(s[i] - '0') * intpow(9, n - i - 1);
            if (s[i - 1] == s[i]) {
                break;
            }
            if (s[i - 1] < s[i]) {
                ans -= intpow(9, n - i - 1);
            }
        }

        // 現在見ている数が neq number ならば +1 する
        int ok = 1;
        rep2(i, 1, n) {
            if (s[i - 1] == s[i])
                ok = 0;
        }
        if (ok)
            ans++;

        return ans;
    };

    auto cal = [f](ll k) -> ll {
        ll ac = INF, wa = 0;
        while (abs(ac - wa) > 1) {
            ll wj = (ac + wa) / 2;
            ll v = f(f, wj);
            if (v >= k) {
                ac = wj;
            } else {
                wa = wj;
            }
        }
        return ac;
    };

    int t;
    cin >> t;
    rep(_, t) {
        ll k;
        cin >> k;
        cout << cal(k) << endl;
    }
}