E - Even Digits Editorial
by
Nyaan
Editorial for printing
この問題はいくらかの言い換えにより見通しがよくなる問題なので、言い換える手順を説明します。
問題概要を簡潔に説明すると次の通りです。
\(0,2,4,6,8\) を並べて出来る整数のうち小さい方から \(N\) 番目の整数を求めてください。
ここで、登場する数字 \(0,2,4,6,8\) を全て \(2\) で割って \(0,1,2,3,4\) に置き換えると次のようになります。
\(0,1,2,3,4\) を並べて出来る整数のうち小さい方から \(N\) 番目の整数を求めてください。
この「\(0,1,2,3,4\) を並べて出来る整数」というのは \(5\) 進数 を利用すると上手く扱うことが出来ます。
条件を満たす整数は小さい方から順に
\[0, 1, 2, 3, 4, 10, 11, 12, 13, 14, 20, \dots\]
ですが、ここで上の数列を \(5\) 進数とみなした時の値を \(10\) 進数に直すと
\[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, \dots\]
になっています。つまり、「\(N\) 番目の整数を \(5\) 進数とみなして値を計算すると \(N-1\) になる」ということです。
よって、この問題は次のように言い換えることが出来ます。
\(N-1\) を \(5\) 進数に変換してください。
\(5\) 進数への変換は下の桁から決めていくことで変換することが出来ます。 (この部分については、ABC186 C などで既に出題されていて、Google 等で検索しても方法が見つかるので詳細は省略します。)
言い換え先の問題の解法を実装することで、この問題を解くことが出来ます。 (\(0,2,4,6,8\) を \(0,1,2,3,4\) に置き換えて問題を解いているので、最後に元の問題に戻すために \(0,1,2,3,4\) を \(0,2,4,6,8\) に置き換え直す必要があるのに注意してください。)
- 実装例(C++)
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int main() {
long long N;
cin >> N;
N--;
vector<int> a;
while (N) {
a.push_back(N % 5);
N /= 5;
}
if (a.empty()) a.push_back(0);
reverse(begin(a), end(a));
for (auto& x : a) cout << x * 2;
cout << endl;
}
posted:
last update:
