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

こんにちは, Shinoryoです.

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

A - twiblr

求める値は $2 A + 100 - B$ となるので, それを出力します.

	a, b = [int(x) for x in input().split()]
	print(2*a+100-b)

$k$ を $2$ から $A$ の最大値(もちろん $1000$ まででも問題ありません)までループさせて, 各 $k$ に対してGCD度を求めます. そして, 最もGCD度が大きかったときの $k$ を出力します.

	n = int(input())
	a = sorted([int(x) for x in input().split()], reverse=True)
	gcdmax, ans = 0, 0

	for k in range(2, a[0]+1):
	gcdtemp = sum(a[i] % k == 0 for i in range(n))
	if gcdmax < gcdtemp:
	gcdmax, ans = gcdtemp, k

	print(ans)

Pythonで組み合わせのリストを作成するには, itertools.combinations(リスト)を利用します.

$N$ の桁のうち $0$ 個を消した場合, $1$ 個を消した場合, ……と順に試していき, $3$ で割り切れた場合に消した桁数を出力します. $3$ で割り切れるかどうかの判定は, 各桁の数字の合計が $3$ で割り切れるかどうかで行います.

	import itertools

	n = [int(x) for x in list(input())]
	k = len(n)

	for i in range(k+1, 0, -1):
	for c in itertools.combinations(n, i):
	if sum(c) % 3 == 0:
	print(k-i)
	exit()

	print(-1)

愚直に行うと $O (N^{2})$ かかるため, TLE. そのようなコードを参考までに以下に示しておきます.

	n = int(input())
	a = [int(x) for x in input().split()]
	resultmax, result = 0, 0

	for i in range(n):
	for j in range(i+1):
	result += a[j]
	resultmax = max(resultmax, result)

	print(resultmax)

そこで, 「正の向きに $A_{1}$ 進み, 正の向きに $A_{2}$ 進み, 正の向きに $A_{3}$ 進み, …, 正の向きに $A_{i}$ 進む」という一連の動作を動作 $i$ とします.

ある変数 $p$ に対して, $A_{i}$ を順に足していくことで「動作 $i$ の合計の座標の変化」が分かります.
また, $p$ が最大だったときの値を(変数 $q$ に)保存し続けることで, 「動作 $i$ を座標 $0$ で始めた場合の, 開始から終了までの座標の最大値」が分かります.
さらに, $p$ を順に足し続けてきたある変数 $x$ に対して, $q$ を足すことで「動作 $i$ が行われている間の座標の最大値」が分かります.
つまり, $x$ が最大だったときの値を(変数 $r$ に)保存し続けることで, 求める最大値を得ることができます.

この方法なら $O (N)$ ですみます.

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