AtCoder精選良問「D - Multiply and Rotate」Diff 862

この記事はAtCoderの精選良問集マガジンの中の記事です。
私が良問だと思った問題を解説付きでまとめています。

AtCoder 精選良問集 Diff 茶後半～水前半｜Qlitre｜note

問題リンク

D - Multiply and Rotate

問題概要

はじめ、黒板に１の数字が書かれている。
整数 a と N が与えられる。その中で以下の操作のどちらかを行うことができる。

1. 黒板の数字を消して、a 倍した数字を書きこむ。

2. 黒板の数字の末尾の数字を先頭に持ってくる

ただし、２番の操作に関しては、黒板の数字が10未満、もしくは10で割り切れるとき（末尾が０になるため）は行えない。

以上のような設定で最少何回で黒板の数字をNにできるか、ということを出力する。

考え方

まず制約に注目をしてみる。
a N ともに10**6 つまり1,000,000と大きいように見える。
なんとなく全探索が厳しいかなーという感想を一見したところ持ってしまう。

しかし、良く良く考えてみると、例えば黒板に書かれた数字は１番の操作では倍々で増えていく。１番の操作をしている限りはすぐにNを超えてしまうんじゃないか、という感じがある。
試しに a の一番小さい入力である２で調べてみよう。

function main() {
    const maxNum = 10 ** 6
    let num = 1
    let cnt = 0
    const a = 2
    for (let i = 0; i < 100; i++) {
        num *= a
        cnt++
        if (num > maxNum) break
    }
    log(cnt)
}

20

簡単なfor文で何回２をかければ1,000,000を超えるか調べみた。出力は20だったので、操作１を行っている限り20回程度行うとNを超えてしまうことがほとんどであることが分かる。

次に操作２の方に注目をする。末尾の数字を先頭に持ってくる内容のため、多くて数字の桁数マイナス１の回数を調べればいいことがわかる。

たとえば123という数字で考えてみる。
１回操作をすると312になる。
２回操作をすると231になる。
３回操作をすると123と元に戻る。
そのため、これ以上の操作をする必要がない。
制約が10**6なので、大きい数字でも６回程度で調べ上げられる。

実際の探索の実装については幅優先探索を用いるとよいだろう。

a=2で例えば123 という数字をいまみているとする。
2倍した246と、末尾を先頭に持ってきた312をキューに加える。
そして次に246 を見て…というように探索を行っていく。
このようにして最初に見つかった回数が、答えとなる最小の回数だ。

次に終了条件を考えてみる。
操作１と操作２に注目をすると、桁数が減るということはありえない。

例えば Nが123でいまみている数字が1234だった場合、どちらの操作を行っても、桁数が3以下になることはありえない、ということである。

そのため、今みている数字の桁数がNの桁数を超えた場合は、それ以上に追加するべき数字はないので、キューへ新たな数字は追加しない。

これをNに当たるまでひたすら続けていく。

実装

幅優先探索は両端キューを使って行うのがセオリー。しかし前提条件からそこまでキューの大きさが増えないので、素朴なarray.shift()メソッドで先頭の数字を取り出しても充分に間に合う。

import { createInterface } from "readline";
import * as fs from "fs";
import { log } from "console";


function main() {
    const [a, n] = nextNums(2)
    // 最大の桁数
    const maxDigitLen = String(n).length
    // キュー　今見ている数字と、操作を行った回数を保持させていく
    const que: number[][] = []
    // 既にみた数字を格納する集合
    const vis: Set<number> = new Set()
    que.push([1, 0])
    vis.add(1)
    let ans = -1
    while (que.length > 0) {
        // 今見ている数字と回数を取り出す
        const [nowNum, cnt] = que.shift()!
        // nにあたったらそれが答え
        if (nowNum == n) {
            ans = cnt
            break
        }
        // 今見ている数字の桁数
        const nowDigitLen = String(nowNum).length
        // 超えている場合は操作しない
        if (nowDigitLen > maxDigitLen) continue
        // 操作１で得られる数字
        const op1Num = nowNum * a

        if (!vis.has(op1Num)) {
            // キューに次の数字を加える
            que.push([op1Num, cnt + 1])
            vis.add(op1Num)
        }
        // 10より大きい且つ10で割り切れない場合操作２
        if (nowNum > 10 && nowNum % 10 != 0) {
            // 末尾の数字
            // 123 => 3
            const lastDigit = nowNum % 10
            // 末尾の数字以外の数字
            // 123 => 12
            const remain = Math.floor(nowNum / 10)
            // 3 * (10**2)=> 300 + 12 = 312
            const op2Num = lastDigit * (10 ** (nowDigitLen - 1)) + remain
            if (!vis.has(op2Num)) {
                // キューに入れる
                que.push([op2Num, cnt + 1])
                vis.add(op2Num)
            }
        }
    }
    // 答えの出力 見つかっていなかったら-1が出力される。
    log(ans)
}

let inputs = "";
let inputArray: string[];
let currentIndex = 0;

function next() {
    return inputArray[currentIndex++];
}
function nextNum() {
    return +next();
}
function nextBigInt() {
    return BigInt(next());
}
function nexts(length: number) {
    const arr = [];
    for (let i = 0; i < length; ++i) arr[i] = next();
    return arr;
}
function nextNums(length: number) {
    const arr = [];
    for (let i = 0; i < length; ++i) arr[i] = nextNum();
    return arr;
}
function nextBigInts(length: number) {
    const arr = [];
    for (let i = 0; i < length; ++i) arr[i] = nextBigInt();
    return arr;
}


// デバッグ環境がWindowsであれば条件分岐する
if (process.env.OS == "Windows_NT") {
    const stream = createInterface({
        input: process.stdin,
        output: process.stdout,
    });
    stream.on("line", (line) => {
        inputs += line;
        inputs += "\n";
    });
    stream.on("close", () => {
        inputArray = inputs.split(/\s/);
        main();
    });
} else {
    inputs = fs.readFileSync("/dev/stdin", "utf8");
    inputArray = inputs.split(/\s/);
    main();
}