AtCoder Beginner Contest 180をPythonで解く-Shinoryo's Weblog

こんにちは, Shinoryoです.

今回はAtCoder Beginner Contest 180を, Pythonで解いてみた結果を書き連ねていこうと思います.

A - box

出力すべき解答は$N-A+B$なので, それを出力します.

次の2つの配列を用意しておくと便利です.

sorted()で並べ替えた配列の最後の値(＝最大値)を表示するには[-1]とします.

すなわち, $N$の公約数を羅列するという問題です. $i$が$1$から$N$までループさせて, $N$が$i$で割り切れるかどうかを調べます. しかし, これだとTLEです.

$N$が$i$で割り切れるならば, $N$は$N/i$でも割り切れることを利用すると, $1$から$\sqrt{N}$までのループで済みます.

(例えば, $6$は$2$で割り切れるが, $6/2 = 3$でも割り切れる. )

出力は昇順で並べ替える必要があるので, 公約数のリストを一度配列に格納して, sorted()でソートします.

強さが$Y$以上にならないように, 最も経験値を得る(すなわち最も多く特訓をする)には, 以下のようにします.

強さ$X$があまり大きくないときは, 強さが$B$増えるよりも強さが$A$倍になった方が, 強さの増加を抑えられる. ゆえに, 強さを$A$倍にする操作を行う(カコモンジムに通う).
強さ$X$が十分大きいときは, 強さが$A$倍になるよりも強さが$B$増えた方が, 強さの増加を抑えられる. ゆえに, 強さを$B$増やす操作を行う(AtCoderジムに通う).

「強さ$X$があまり大きくない」の確認は, $X \times A < X + B$(強さが$B$増えるよりも強さが$A$倍になった方が, 強さの増加を抑えられる)かつ$X \times A < Y$($A$倍しても強さが$Y$に届かない)で行います.

強さ$X$を$A$倍する操作が終了したら, あとは何回$B$を加えられるかを考えるだけです.

E以降は私の能力不足故に省略いたします.