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

こんにちは, Shinoryoです.

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

A - box

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

	n, a, b = [int(i) for i in input().split()]
	print(n-a+b)

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

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

	n = int(input())
	absx = sorted([abs(int(i)) for i in input().split()])
	squaredx = [i**2 for i in absx]

	print(sum(absx))
	print(sum(squaredx)**(1/2))
	print(absx[-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$ を加えられるかを考えるだけです.

	x, y, a, b = [int(i) for i in input().split()]
	exp = 0

	# bを足すよりもaをかけた方が経験値が稼げるパターンまで, xを増やし続ける
	# (ある段階でbを足した方が経験値が稼げるようになると, それ以降はbを足した方が経験値が稼げる)
	while True:
	if xa >= y or xa >= x+b :
	break
	exp += 1
	x *= a

	# 残り分はbを足す
	exp += (y - x) // b

	# 上の計算だとbを足し続けた結果yになる可能性もあるので, それを確認する
	if (y-x) % b == 0:
	exp -= 1

	print(exp)

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