問題
10進法ですべての桁の数字が である整数をレピュニットと呼ぶ。（
がレピュニットになる。）
ちょうど3つのレピュニットの和として表せる整数のうち、 番目に小さいものを求めよ。
入力
整数 が1行に与えられる。
条件
- 実行時間制限: 2s
- メモリ制限: 1024MB
出力
答えを1行に出力すること。
解法
整数 （ただし、
）に対して、
桁のレピュニットは
（
桁）です。
従って、和に使われるすべてのレピュニットが 桁以下のとき、最大値は3つすべてが
桁のレピュニットのときの、
（
桁）です。
この値は
桁であるので、
桁のレピュニットよりも小さい値となります。
このことから、ある整数 に対して、
桁以下の3つのレピュニットの和として表せる整数の個数の合計が
を上回ったら、
桁以降のレピュニットについて考慮する必要はありません。
ここで、「 桁以下のレピュニットを3つ用いて得られる和の値」の個数について考えます。
3つのレピュニットの桁数をそれぞれ
とします。（ただし、
）
このとき、 については
であるので、
は相異なる3つの整数ということになります。
かつ
であることから、
の組み合わせの総数は
以上
以下の整数を3つ相異なるようにとる組み合わせの総数と等しいので、
\begin{align}
\frac{(i + 2) \{ (i + 2) - 1\} \{ (i + 2) - 2 \}}{3 !} = \frac{1}{6} i (i + 1) (i + 2)
\end{align}
が、和の値の個数となります。
ここで、 としてみると
\begin{align}
\frac{1}{6} \cdot 12 \cdot 13 \cdot 14 = 364
\end{align}
となります。
今回の問題では は最大でも
であるので、
桁以下のレピュニットの和について調べ上げれば、十分に問題の解答が得られるということが言えます。
以上から、 桁以下のすべてのレピュニットについて、 forループを3重で回して和を計算することで、
番目の値を求めることができます。
ここで、（
桁）であるので、
桁のレピュニットは
\begin{align}
\frac{1}{9} ({10}^{i} - 1)
\end{align}
と表すことができます。
コードを書く際はこれを利用します。
ソースコード
int n; vector<ll> ans; // ans は和として得られる値を保存する vector int main() { cin >> n; // 値の入力 // i <= j <= k となるように3重のforループを回し、和を列挙する for (int i = 1; i <= 12; i++) { ll num_i = (pow(10, i) - 1) / 9; // i 桁のレピュニットは (10 ^ i - 1) / 9 で与えられる for (int j = i; j <= 12; j++) { ll num_j = (pow(10, j) - 1) / 9; for (int k = j; k <= 12; k++) { ll num_k = (pow(10, k) - 1) / 9; ans.push_back(num_i + num_j + num_k); // 和を ans に入れる } } } sort(ans.begin(), ans.end()); // ans をソートする cout << ans[n - 1] << endl; // ans が 0-index になっていることに注意して出力する return 0; }
感想
場合の数についての説明を書く際に、「 のときの組み合わせの計算って、どのようにすればいいんだっけ…？」となりました。
