ABC 401-500/ABC406B - Product Calculator - 競技プログラミング用 知識集積所

---

問題

ABC406B
C++で解くのは、B問題としては難問。

必要知識

A問題レベルのものは省略

• long long型

考え方

数字が小さい場合は、ほぼ問題文どおりにやればできる。
やや込み入っている点は、k+1桁以上の数の判定方法。
以下のいずれかでやることになる。

1つ目は、基準値を用意すること。
1に対してforループで10をk回かけてあげれば、k+1桁の中で最小の数ができる。
それ以上かどうかを判定すればよい。

2つ目は、to_string()して.size()で桁数を取得する方法。
取得した数がk+1以上であるかを判定すればよい。

これで、forループで1回分ずつ電卓の表示を求めてやれば、入力が小さければACできる。

問題は、入力が大きくなった場合。
まず、Aの値が最大で10^kまでありうる。
int型からは当然のようにあふれる。
そして、long long型ですら、電卓の今の表示にAを掛けるとあっさりあふれる。
なので、実際にかけてみて桁数を調べる方法が使えない。
これがこの問題をC++で解く場合の最大の難所。

別の判定方法を考える。
例えばkが3で次に掛ける数が321の場合、3*321=963はセーフで、4*321=1284はアウト。
これは、1000/321=3で元の電卓の数の上限を求めることができそうに見える。
しかし、kが3で次に掛ける数が100の場合、電卓の数の上限は9だが、1000/100=10になって合わない。
そこで、1000ではなく999/321=3や999/100=9、となる。
1000の前後になりそうな111（9倍で999)や143（7倍で1001）も、999/111=9、999/143=6、と上限が正しく出る。

よって、k+1桁以上の数の判定方法には1つ目の方法を改良した方法を用いる。
k+1桁の中で最小の数から1を引いておき、それを次の入力数割った商を元の電卓の数の上限とし、それより大きい数が入っていたらリセットとする。
これで無事にオーバーフローせずにACすることができる。

解答例

解答例

注意点

別解

double型での判定を併用する

k+1桁以上であるかの判定にdouble型を使えば、10^308くらいまで対応しているのでオーバーフローの心配はいらなくなる。
しかし今度は精密性が犠牲になってしまう。
そこで、両者を併用し、

• まず、double型を用いてオーバーフローするほど大きくなるかを判定する
• オーバーフローしないなら、真面目に掛け算してk+1桁以上かどうかを確認する

とすることでも解ける。
解答例

Pythonで解く

Pythonならそもそもこんな苦労をしなくてもいい……。