AtCoder精選良問「D - Multiply and Rotate」Diff 862
この記事はAtCoderの精選良問集マガジンの中の記事です。
私が良問だと思った問題を解説付きでまとめています。
問題リンク
問題概要
はじめ、黒板に１の数字が書かれている。
整数 a と N が与えられる。その中で以下の操作のどちらかを行うことができる。
黒板の数字を消して、a 倍した数字を書きこむ。
黒板の数字の末尾の数字を先頭に持ってくる
ただし、２番の操作に関しては、黒板の数字が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();
}