diverta 2019 Programming Contest に参加した【Python3】

今日は diverta 2019 Programming Contest に参加しました。

色々とトラブルがあったようで、結局 unrated となってレート更新がされないそうなのがつらいですが、一応 A ~ D までしっかり解くことができたので、そこまで記録を。

A – Consecutive Integers

すぬけ君は \(1,2,…,N\) の \(N\) 個の整数を持っています。 すぬけ君はこれらの整数から \(K\) 個の整数を選んで高橋君にあげようと考えています。連続する \(K\) 個の整数を選ぶ方法は何通りありますか？

https://atcoder.jp/contests/diverta2019/tasks/diverta2019_a

連続する \(K\) 個の整数であることに注意。 \(N – K + 1\) 個が答えになりますね。

N, K = map(int, input().split())
print(N - K + 1)

B – RGB Boxes

すぬけ君はボールが入った箱を売っている店に行きました。 売っている箱は以下の \(3\) 種類です。
・ \(R\) 個のボールが入った赤色の箱
・ \(G\) 個のボールが入った緑色の箱
・ \(B\) 個のボールが入った青色の箱
すぬけ君は赤色の箱を \(r\) 個、緑色の箱を \(g\) 個、青色の箱を \(b\) 個買うことで合計でちょうど \(N\) 個のボールが手に入るようにしたいです。 これを達成する非負整数の組 \((r,g,b)\) はいくつありますか？

https://atcoder.jp/contests/diverta2019/tasks/diverta2019_b

要するに、非負整数 \(x, y, z\) で R * x + G * y + B * z == N を満たすものの個数を求めればOKです。

\(x, y, z\) は非負ですから上限がそれぞれ \(N / R, N / G, N / B\) ですので、あとはぶん回して愚直に全探索です。

条件から \(1 \leq R, G, B, N \leq 3000\) だったので \(O(N ^ 2)\) でイケるとみて提出しましたが TLE 。PyPy に変更して再提出してみたら AC もらえました。

R, G, B, N = map(int, input().split())
ans = 0
for x in range(N // R + 1):
	for y in range(N // G + 1):
		if (N - R * x - G * y) % B == 0 and 0 <= (N - R * x - G * y) // B <= N // B:
			ans += 1
print(ans)

C – AB Substrings

すぬけ君は \(N\) 個の文字列を持っています。\(i\) 番目の文字列は \(s_i\) です。
これらの文字列を好きな順序で並べたあと、連結して \(1\) つの文字列を作ることを考えます。 作った文字列に AB という部分文字列が含まれる個数としてありうる値のうち、最大値を求めてください。

https://atcoder.jp/contests/diverta2019/tasks/diverta2019_c

個人的には D よりも面倒でした。

それぞれの文字列中の “AB” の個数は簡単に数えられますが、それぞれの端点の処理がちょっとめんどいです。

最初が “B” であること、最後が “A” であることが重要ですが、 BCA みたいな両方とも満たす場合は別個に考える必要があることに注意です。（これは具体例作ったら分かります）

N = int(input())
s = [0] * N
for i in range(N):
	s[i] = input()
ans = 0

for j in range(N):
	ans += s[j].count("AB")

x, y, z = 0, 0, 0  # xは~A、yはB~、zはB~Aの個数
for k in range(N):
	if s[k][0] == "B" and s[k][-1] =="A":
		z += 1
	elif s[k][0] == "B":
		y += 1
	elif s[k][-1] == "A":
		x += 1

if x >= 1 and y >= 1:
	ans += z + min(x, y)
elif x >= 1 or y >= 1:
	ans += z
else:
	ans += max(0, z - 1)

print(ans)

D – DivRem Number

すぬけ君は高橋君から正の整数 \(N\) をもらいました。 正の整数 \(m\) が以下の条件を満たすとき、 お気に入りの数 と呼ばれます。
\(N\) を \(m\) で割った商とあまりが等しい、すなわち \(⌊\frac{N}{m}⌋=N \bmod m\) が成立する
お気に入りの数を全て求め、その総和を出力してください。

https://atcoder.jp/contests/diverta2019/tasks/diverta2019_d

実験したり、数式化してごちゃごちゃいじったりしていると気づきますが、

\(N = k (m + 1)\) という式が得られるので、 \(m\) の候補は \(N\) の正の約数から \(1\) を引いたものになります。ということで、 \(N\) の正の約数を全列挙してあとは愚直に考えれば良さそうですね。

N = int(input())
ans = 0

div = []  # Nの約数を全列挙してdivとする
for i in range(1, int(N ** 0.5) + 1):
	if N % i == 0:
		div.append(i)
		if i != N // i:
			div.append(N // i)

for j in range(len(div)):
	if div[j] == 1:  # m=0はskip
		pass
	else:
		m = div[j] - 1
		if N // m == N % m:
			ans += m

print(ans)

E, F はまだレベルに達してないのでパスです。そのうち解けるようになりたい。まだ DP の理解も曖昧なので、まずは DP を習得しながら ABC – C の過去問を埋めていきたいです。

では。