【AtCoder】ABC 336 C - Even Digits | 茶コーダーが解くAtCoder

atcoder.jp

実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 343

問題概要

非負整数 $n$ が以下の条件を満たすとき、 $n$ は「良い整数」であるとする。いい整数のうち小さい方から $N$ 番目の整数を求めよ。

条件 : $n$ の各桁は $0, 2, 4, 6, 8$ のみである。

制約

$N$ は整数。
$1 \leq N \leq 10^12$

考察

$N$ は最大で $10^{12}$ になるため、単純にループを用いて各桁を確認していくのでは間に合わない。

一度冷静になって、いい整数を1番目から列挙していこう (サンプルケース1を参照) 。

使える整数は5種類なので、2桁目は5番目ごとに変わっていく。

この仕組みにピンとこないだろうか。もっとわかりやすくするために、各々を2で割ってみよう。この操作によって、使える整数は $0, 1, 2, 3, 4$ になった。

そう、実はいい整数の列というのは、5進数を列挙していったものなのである。

ここまで分かってしまえばあとはやるだけ。 $N-1$ を5進数に変換したものを文字列化し、各桁を2倍して元に戻す。基数変換のライブラリは以前実装したものを利用している。

yuulis.hatenablog.com

コード

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

using ll = long long;

// ======================================== //

std::string radix_conversion(const std::string x, const int from, const int to)
{
    // Conversion table.
    // To be changed as appropriate.
    const std::string table = "0123456789abcdef";
    assert((2 <= from && from <= 16) && (2 <= to && to <= 16));

    unsigned long sum = 0;
    for (char c : x)
    {
        sum = sum * from + table.find(c);
    }

    std::string res = "";
    do
    {
        int mod = sum % to;
        res = table[mod] + res;
        sum /= to;
    } while (sum);

    return res;
}

int main()
{
    ll N;
    cin >> N;

    string ans = radix_conversion(to_string(N - 1), 10, 5);
    for (auto &c : ans)
    {
        if (c == '0')
            cout << 0;
        else if (c == '1')
            cout << 2;
        else if (c == '2')
            cout << 4;
        else if (c == '3')
            cout << 6;
        else if (c == '4')
            cout << 8;
    }
    cout << endl;
}