ABC367 C-Enumerate Sequences (C++)

C - Enumerate Sequences

検討

コンテスト中は再帰で書こうとしましたがぐちゃぐちゃになり2完で終わりました。再帰の模範解答は公式解説に譲るとして、コンテスト後に自力で解いた解法は6進数に変換して数列を列挙する方法です。

回答

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

// 10→6進数変換
string t_to_s (int n) {
    string n_s = "";
    while (n > 0) {
        n_s += to_string(n % 6);
        n /= 6;    
    }
    reverse(n_s.begin(), n_s.end());

    return n_s;
}

// 6→10進数変換
int s_to_t (int n) {
    int n_t = 0;
    int tmp = 1;
    while (n > 0) {
        n_t += n % 10 * tmp;
        n /= 10;
        tmp *= 6;
    }

    return n_t;
}

int main() {
    int N, K; cin >> N >> K;
    vector<int> R(N);
    for (int i = 0; i < N; i++) cin >> R[i];

    int start = 0, end = 0;
    for (int i = 0; i < N; i++) {
        start*= 10; end *= 10;
        start++; end += 5;
    }
    

    for (int i = s_to_t(start); i <= s_to_t(end); i++) {
        int tmp = i;
        string tmp_s = t_to_s(tmp);

        bool jdg = true;
        int num_sum = 0;
        for (int j = 0; j < N; j++) {
            if (tmp_s[j] == '0' || tmp_s[j] - '0' > R[j]) {
                jdg = false;
                break;
            }
            num_sum += tmp_s[j] - '0';
        }

        if(jdg && num_sum % K == 0) {
            for (int j = 0; j < N; j++) {
                cout << tmp_s[j] << " ";
            }
            cout << endl;
        }
    }
}

実行時間282msでACでした。
備忘録としてn->10進数、10->n進数変換するコードを置いておきます。

// n進数はstringで扱っている

// 10->n進数変換
string ten_to_n (int num, int n) {
    string n_conv = "";
    while (num > 0) {
        n_conv += to_string(num % n);
        num /= n;    
    }
    reverse(n_conv.begin(), n_conv.end());

    return n_conv;
}

// n->10進数変換
int n_to_ten (string num_string, int n) {
    int num = stoi(num_string);
    int num_conv = 0;
    int tmp = 1;
    while (num > 0) {
        num_conv += num % 10 * tmp;
        num /= 10;
        tmp *= n;
    }

    return num_conv;
}