[Q] A. Neq Number

BよりもAのほうが難しかったように思う。
考察
0. 数え上げる状況が複雑なので、わかることから詰めていきたい
1. まず何桁になりそうか考える。

1-9: 9通り
01-99: 90通り ... 99 - {11, 22, 33, ..., 99} = 90通り。
001-999: 819通り ... 0XX は 上の行で求めた90通り。
                   1XX は 9 * 9 = 81通り。10の位のXには1以外が入る。1の位のXには、10の位と違う値が入る。
                   2XX は 9 * 9 = 81通り。これが9XXまである。
                   81 * 9 = 729通り
                   あわせて819通り。
0001-9999: 7380通り。 ... 819 + (9 * 9 * 9) * 9 = 7380通り。

桁数をdigits[i]として
digits[0] = 0
digits[1] = digits[0] + pow(9, 1)
digits[2] = digits[1] + pow(9, 2)
digits[3] = digits[2] + pow(9, 3)
digits[n] = digits[n - 1] + pow(9, n)
として求まることが分かった。

2. 桁数が分かったら、数字を特定していく。注意点がこまごまと2つ。
a. 先頭の場合。
まず先頭は0でない。0XXのパターン数を引く。K -= digits[digit]をする。
1XX, 2XX, …, 9XXのどこに含まれているかを、(K - 1) / pow9[digit]で特定する。

b. 先頭以外の桁の場合。
前の桁と同じ値を考えてはいけない。
a.で1XXにあると分かった場合。
10X, 12X, 13X, … 19Xのどれに含まれているかを、n = (k - 1) / pow9[digit]で特定する。
もしn = 1とわかった場合、11Xではなく12Xにあると考えること。
nが前の桁以下の数なら+1する。

これがK = 1になるまで計算を繰り返す。

具体的に考えて整理します。

0. 前計算します

/// 2桁
00~09: 9 = digits[1]
10~19: 9 = pow9[1]
...
90~99: 9

/// 3桁
000~099: 90 = digits[2]
100~199: 81 = pow9[2]
...
900~999: 81

/// 4桁
0000~0999: 819 = digits[3]
1000~1999: 729 = pow9[3]
...
9000~9999: 729

/// 5桁
00000~09999: 7381 = digits[4]
10000~19999: 6561 = pow9[4]
...
90000~99999: 6561


Q. 例えばK=300を考えます。

1. まず桁数を特定します。
digits[1] = 9 < 300 なので1桁より大きい
digits[2] = 90 < 300 なので2桁より大きい
digits[3] = 819 >= 300 なので3桁です。

2. 数を特定します。
まず3桁目が何かを考えます。

3桁目は0か?
000-099: digits[2] = 90 < 300なので0XXより大きい。300 - 90 = 210
3桁目は1か?
100~199: pow9[2] = 81 < 210 なので1XXより大きい。 210 - 81 = 129
3桁目は2か?
200-299: pow9[2] = 81 < 129 なので2XXより大きい。 129 - 81 = 48
3桁目は3か?
300-399: pow9[2] = 81 >= 48 なので3XXにあることが判明した。


2桁目が何かを考えます。K = 48
2桁目は0か?
300-309: pow9[1] = 9 < 48 なので30Xより大きい。 48 - 9 = 39
2桁目は1か?
310-319: pow9[1] = 9 < 39 なので31Xより大きい。 39 - 9 = 30
2桁目は2か?
320-329: pow9[1] = 9 < 30 なので32Xより大きい。 30 - 9 = 21
2桁目は3か?
330-339: 33かぶりなので0通り
2桁目は4か?
340-349: pow9[1] = 9 < 21 なので34Xより大きい。 21 - 9 = 12
2桁目は5か?
350-359: pow9[1] = 9 < 12 なので35Xより大きい。 12 - 9 = 3
2桁目は6か?
360-369: pow9[1] = 9 >= 3 なので36Xであることが判明した。

1桁目が何かを考えます。K = 3
3番目の1桁が答えになるので
360, 361, 362とわかる。

A. 362

もう少し一般化したい。2桁目を求める部分を眺める。
pow9[1]の引き算の繰り返しを、飛ばせそうな気がする。

K = 48から、pow9[1] = 9を5回引けることが分かる。
(48 - 1) / 9 = 5
※スキップ回数は、(K - 1) / 9で求める。 あまりを1-9で残す必要があるから。

まるまる5個スキップした、6個目の数にあることがわかる。
30X, 31X, 32X, 34X, 35X, 36X
36Xであることが判明する。

つまり(K - 1) / pow9[1] = 5スキップ
ここで、3桁目の数字が 3 <= 5 なので、もう1つスキップする必要があり、5 + 1 = 6が2桁目とわかる。

実装

int main()
{
  cincout();

  vector<ll> digits(19, 0);
  vector<ll> pow9(19, 0);
  pow9[0] = 1;
  digits[0] = 0;
  rep(i, 18)
  {
    pow9[i + 1] = pow9[i] * 9;
    digits[i + 1] = digits[i] + pow9[i + 1];
  }
  ll T;
  cin >> T;
  while (T--)
  {
    /*
    1. 桁を特定する
    2. 数字を特定する
    */
    ll K;
    cin >> K;
    string S;

    // 1. 桁を特定する
    rep(i, 19)
    {
      if (K <= digits[i])
      {
        S = string(i, '0');
        break;
      }
    }

    // 2. 数字を特定する。
    // 1XXはpow9[2] = 81通りある。pow9[digit]だけバリエーションがある
    for (ll digit = (ll)S.size() - 1; digit >= 0; --digit)
    {
      // 先頭だけ、0XXにはなりえないので注意。
      if (digit == (ll)S.size() - 1)
      {
        K -= digits[digit]; // 先頭0XXのパターンを除く
        ll n = (K - 1) / pow9[digit];
        K -= n * pow9[digit];
        // 先頭は1~9のどれかなので+1する
        ++n;
        S[digit] = n + '0';
      }
      else
      {
        ll n = (K - 1) / pow9[digit];
        K -= n * pow9[digit];

        // 1個前のけたがn以下の場合はnを1増やす
        // 3XYについて、Xは{0,1,2,4,5,...}と3が入りえない。
        // n=3の場合、33Yにはなりえない。34Yのくだりにあるはずなのでn+1する
        if (S[digit + 1] - '0' <= n)
          ++n;
        S[digit] = n + '0';
      }
    }
    reverse(all(S));
    cout << S << endl;
  }
}

https://atcoder.jp/contests/arc173/submissions/51139886