問題概要

黒板に整数値 $x = 1$ が書かれています。次のいずれかの操作を最小回数繰り返すことによって、整数値 $x$ の値を $x = N$ にしたいとします。

$x$ を $a$ 倍して $ax$ にする
$x$ を十進法表記したときに、末尾の値を先頭に持ってくる

最小回数を求めてください。不可能である場合は -1 を出力してください。

制約

$2 \le a, N \le 10^{6}$

解法

この手の「最小回数」を求める問題は、原理的には BFS で解けます！
ただし、探索領域があまりにも広大であると、TLE となってしまいます。

今回の問題では、 $N \le 10^{6}$ なので、整数値 $x$ が $10^{7}$ 未満である場合のみ考えればよいです。なぜなら、今回の操作によって、整数値の桁数が減少することはないからです (値が減少すること自体はありえます)。

一般には、 $10N$ 未満の整数値のみ考えれば良いと言えるでしょう。

よって、 $1$ 以上 $10N$ 未満の整数値に対応する頂点を用意して、操作によって変化する 2 値間に辺を張ったグラフを考えて、 $1$ から $N$ までの最短路を求めます。

シフト演算には $O(\log N)$ の計算量を要することから、全体の計算量は $O(N \log N)$ と評価できます。

コード

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

int main() {
    long long a, N;
    cin >> a >> N;
    
    queue<long long> que;
    vector<long long> dp(N * 10, -1);
    
    auto push = [&](long long v, long long p) -> void {
        if (v >= N * 10) return;
        if (dp[v] == -1) {
            que.push(v);
            dp[v] = dp[p] + 1;
        }
    };
    que.push(1);
    dp[1] = 0;
    while (!que.empty()) {
        long long x = que.front();
        que.pop();
        
        // a 倍する
        push(x * a, x);
        
        // シフト操作する
        if (x % 10 != 0) {
            string sx = to_string(x);
            sx = sx.back() + sx.substr(0, sx.size()-1);
            istringstream si(sx);
            long long x2;
            si >> x2;
            push(x2, x);
        }
    }
    cout << dp[N] << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 235 D - Multiply and Rotate (緑色, 400 点)

問題概要

制約

解法

コード