yutasの競技プログラミング勉強帖

競技プログラミングの問題についての解説記事を主に書いています。

C - Even Digits / AtCoder Beginner Contest 336

ABC336 AtCoder C++ AtCoder Beginner Contest 300点 整数問題 競技プログラミング

問題

非負整数 n が次の条件を満たすとき、 n を良い整数と呼ぶ。

  • n を 10 進法で表したときに、偶数の数字 (0, 2, 4, 6, 8) のみが登場する。

このとき、 0, 68, 2024 が良い整数の一例である。

整数 n が与えられるので、良い整数のうち小さい方から n 番目の整数を求めよ。

入力

最初の1行目に、整数 n が与えられる。

条件

  • 実行時間制限: 2s
  • メモリ制限: 1024MB
  • 1 \leq n \leq {10}^{12}

出力

小さい方から n 番目の良い整数を1行で出力すること。

解法

5種類の数字のみが登場することから、5進数の利用を考えます。 5進数の非負整数を小さい順から並べると、 \begin{align} 0, \, 1, \, 2, \, 3, \, 4, \, 10, \, 11, \, 12, \, 13, \, 14, \, 20, \, 21, \, \cdots \end{align} という並び順になります。 これらの各桁の整数を2倍すると、 \begin{align} 0, \, 2, \, 4, \, 6, \, 8, \, 20, \, 22, \, 24, \, 26, \, 28, \, 40, \, 42, \, \cdots \end{align} となり、これは良い整数を小さい順に並べたものとなります。

従って、小さい方から n 番目の良い整数は、非負の5進数のうち、 n 番目に小さい値の各桁を2倍した数字ということになります。

ここで、非負の5進数のうち、 n 番目に小さい数字は、整数 n - 1 を5進数にした値ということになります。

以上から、与えられた n に対して、 n - 1 を5進数に変換し、その各桁を2倍することによって、答えが得られます。

ソースコード

main() 関数の中に、答えを出力する部分を直接実装しました。

int main() {
  // 値の入力
  ll n;
  cin >> n;
  n--; // n を 1 減らしておく

  ll ans = 0, digit = 1; // ans は答えとなる整数、 digit は現在どの位について考えているのかを表す整数

  // n が 1 以上である限り、以下の操作を繰り返す
  while (n > 0) {
    ans += (n % 5) * 2 * digit; // n を 5 で割ったときの余りに 2 を掛けた値がその桁となる
    n /= 5; // n を 5 で割って更新する
    digit *= 10; // 桁を1つ増やす
  }
  cout << ans << endl;

  return 0;
}