第三回アルゴリズム実技検定 C - 等比数列

お題箱より。

解法というよりは「こういう問題を解くための思考プロセスが知りたい」というリクエストだったので、その方向で書きます。

解法

この問題は結局、等比数列の性質を知識として知っている、または実験によって理解することが重要です。なので正直なところ、「知らない場合は色々な値で実験しよう（またはWeb検索しよう）」というのが解くための近道だと思います。

初項 $A$ が正の数であるとき、等比数列は公比 $R$ の値に応じて以下のような挙動になります。

$R$ の範囲	挙動
$R \gt 1$	項が進むにつれて値が急速に大きくなる。
$R = 1$	全ての項が $A$ である。
$-1 \lt R \lt 1$	項が進むにつれて値が急速に $0$ に近付く。
$R = -1$	$A, -A$ を交互に繰り返す。
$R \lt -1$	正の数と負の数を交互に繰り返しながら、その絶対値が急速に大きくなる。

このように $R$ の値によって挙動が大きく変わるので、まずここで場合分けをする、という思考をします。今回の問題では $R$ が正の整数なので、最初の2項目だけを考えれば良いです。

次にそれぞれの場合について考えます。

$R \gt 1$ のとき

このときは値が急速に大きくなるため、少ない項数で $10^{9}$ を超えてしまうことが予想されます。それ以降は値が大きくなり続けるので、一度 $10^{9}$ を超えてしまうと答えは large で確定します。そのため「普通に等比数列の計算を順にしていって、 $10^{9}$ を超えたら large を出力して途中終了し、途中終了せずに第 $N$ 項まで計算できたらそれを出力する」という解法が考えられます。

large になるまで最大でいくつの項があるかを見積もります。 $A, R$ は正整数なのでできるだけ小さい方が値が小さくなりやすい（長引きやすい）です。今は $R \gt 1$ の場合を考えているので、その中で最小ケースである $A = 1, R = 2$ に対して実際に計算をすると第 $31$ 項で $10^{9}$ を超えることが分かります。