サンプルを見れば上限が分かる系の問題！

問題へのリンク

問題概要

各桁の値が 1 である数をレプユニット数という。

レプユニット数 3 個の和として考えられる数のうち、 $N$ 番目に小さい数を求めよ。

制約

$1 \le N \le 333$

考えたこと

まず、問題文の条件を満たす数をトリレプユニット数と呼ぶことにしよう。

この手の問題は「全探索」と相場は決まっている。その際に重要なことは、「何桁のレプユニット数まで考える必要があるか」を $N \le 333$ という制約から見積もることだ。

結論から言えば、サンプル 3 が「333 番目のトリレプユニット数は 112222222233 であること」を示しているので、12 桁まで考えればよいことがわかる。

ここでは、もう少し真面目に考察してみよう。

$N$ 桁以下のトリレプユニット数の個数

トリレプユニット数は、

1112223333

というように「1 → 2 → 3 と変化していく数」なのだ。もちろん、113 のように 2 がなかったり、3333 のように 3 のみだったりもする。

これを踏まえて、 $N$ 桁以下のトリレプユニット数の個数を見積もってみよう。まず、左側に 0-padding して、

00011122233333

というように、 $N$ 個の数であって「0 → 1 → 2 → 3 と変化していく数」と捉え直すことにする。

よって、 $N$ 桁以下のトリレプユニット数の個数は、 $N$ 桁の数の隙間と両端を合わせた $N+1$ 個所から、重複を許して $3$ 個を選ぶ方法の数 (重複組合せ) から 1 を引いたもの（0 を除外する）なので、

${}_{N+1}\mathrm{H}_{3} - 1 = {}_{N + 3}\mathrm{C}_{3} - 1$ 個

と求められる。 $N = 12$ とすると、

${}_{N + 3}\mathrm{C}_{3} - 1 = {}_{15}\mathrm{C}_{3} - 1 = 454$ ( $\ge 333$ ) 個

となる。よって、 $N \le 333$ という制約から、12 桁以下のトリレプユニット数まで考えれば良いことがわかった。

まとめ

全体として解法は

12 桁以下のトリレプユニット数を列挙する
それらの 3 つの和で表される数を重複なしで列挙する
そのうちの $N$ 番目の数を求める

と、すればよい。

コード

ここでは安全のために 15 桁以下のトリレプユニット数を列挙した。

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

int main() {
    vector<long long> base({1});
    for (int i = 0; i < 15; i++) {
        base.push_back(base.back() * 10 + 1);
    }

    vector<long long> all;
    for (auto x : base) for (auto y : base) for (auto z : base) {
        all.push_back(x + y + z);
    }
    sort(all.begin(), all.end());
    all.erase(unique(all.begin(), all.end()), all.end());
    
    int N;
    cin >> N, N--;
    cout << all[N] << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCode ABC 333 C - Repunit Trio (4Q, 灰色, 300 点)

問題概要

制約

考えたこと

$N$ 桁以下のトリレプユニット数の個数

まとめ

コード