AtCoder Beginner Contest 125 に参加した【Python3】

3度目のコンテストです。前回の天下一プログラマコンテストでもD問題が解けなかったので、今回こそは……!という意気込みで臨みました。

相変わらず仕事から帰ったあと、日をまたいでから明け方までの時間を毎日費やしてきて、おかげで過去問はABCのA問題が全て、B問題が半分終わりました。

A問題

ビスケット生産装置を起動すると、起動してから \displaystyle A 秒後、 \displaystyle 2A 秒後、 \displaystyle 3A 秒後、… ( \displaystyle A の倍数秒後) に \displaystyle B 枚ずつビスケットを生産します。ビスケット生産装置を起動してから \displaystyle T + 0.5 秒後までに生産されるビスケットの合計枚数を求めてください。

\displaystyle A 秒ごとに \displaystyle B 枚生産されるので、 \displaystyle T // A 回生産されると考えることができて、これに \displaystyle B を掛ければOKです。

0.5秒ってのは「TがAの倍数だったらそのタイミングで生産されるのか?」的な話を明確化するために付けたものだと考えられるので、この考え方であれば無視でもOKですね。

Python3
A, B, T = map(int, input().split())
print(T // A * B)

B問題

\displaystyle N 個の宝石があり、 \displaystyle i 番目の宝石の価値は \displaystyle V_i です。
あなたはこれらの宝石の中からいくつかを選んで手に入れます。このとき、 \displaystyle 1 つも選ばなくとも、全て選んでも構いません。
ただし、 \displaystyle i 番目の宝石を手に入れる場合コスト \displaystyle C_i を支払わなければいけません。手に入れた宝石の価値の合計を \displaystyle X 、支払ったコストの合計を \displaystyle Y とします。 \displaystyle X - Y の最大値を求めてください。

要するに、一番得をするように宝石を買えば良いわけですね。利益 \displaystyle V_i - C_i が正になるものを購入すれば自然と最大になります。

Python3
N = int(input())
V = list(map(int, input().split()))
C = list(map(int, input().split()))
ans = 0
for i in range(N):
	if V[i] > C[i]:
		ans += V[i] - C[i]
print(ans)

C問題

\displaystyle N 個の整数 \displaystyle A_1, A_2 , ..., A_N が黒板に書かれています。あなたはこの中から整数を \displaystyle 1 つ選んで、 \displaystyle 1 以上 \displaystyle 10^9 以下の好きな整数に書き換えます。
元の整数と同じ整数に書き換えても構いません。
書き換えた後の \displaystyle N 個の整数の最大公約数の最大値を求めてください。

N – 1 個のgcdがあるとき、残り1つが何になろうともともとの gcd 以上に大きくなることは無いので、方針自体はメチャクチャ簡単で「 \displaystyle N - 1 個の gcd の最大をもとめる」でOKなわけです。

gcd を求めるプロセスは以前まとめましたね。

Python 3 でN個の数の最小公倍数・最大公約数を求めたいとき

しかし、普通にやるとオーダーが多分 \displaystyle N^2 になって計算が爆発して死ぬと。死んだコードがこちら。

Python3
import fractions
import copy
N = int(input())
A = list(map(int, input().split()))
ans = 0
for i in range(N):
    B = copy.copy(A)
    del B[i]
    tmp = B[0]
    for j in range(1, N - 1):
    	tmp = fractions.gcd(tmp, B[j])
    ans = max(ans, tmp)
print(ans)

これで TLE で死んだので高速化の方針は \displaystyle 2 つあって。

  • 書き換える(取り除く)数字を決めるプロセスを高速化する方針
  • gcd を求めるプロセスを高速化する方針

自分は後者が分からないので前者でなんとかできないか試行錯誤しましたが、まぁできずに終了。(↓のやつは合ってるかわからないまま書いてみたらそれっぽかったので提出してみると1ケースだけ WA だったやつ)

Python3
import fractions
N = int(input())
A = list(map(int, input().split()))
# まずはA[0]以外のgcdをansとしておく
ans = A[1]
for i in range(2, N):
	ans = fractions.gcd(ans, A[i])
# つぎにA[0]と他の要素の2数のgcdをリストアップし、それが一番小さくなるindexをkとする
G = [A[0]]
for j in range(1, N):
	G.append(fractions.gcd(A[0], A[j]))
k = G.index(min(G))
# A[k]以外のgcdをtmpとしておく
if k == N - 1:
	B = A[: N - 1]
elif k == 0:
	B = A[1:]
else:
	B = A[: k] + A[k + 1:]
tmp = B[0]
for l in range(1, N - 1):
	tmp = fractions.gcd(tmp, B[l])
# ansとtmpの大きい方を出力
print(max(ans, tmp))

↑がなんで WA なのか教えてください。なんで合ってるのかはわからないけどなんで間違ってるのか反例が思いつかないです。

gcdを求めるプロセスを工夫する

twitter を眺めてみた感じ、 累積GCD とかいう方法を使うといけるっぽい。つまり高速化のアプローチをすべきは後者の gcd を求めるプロセスの方でした。

結局 累積GCD が何なのかはわかりませんが、東大の先輩に教えてもらった感じこういう方針で計算量を削減できます。

  • gcd を左から、右からそれぞれメモ化する(たぶんこれが累積GCD?)
  • 書き換えるやつの右と左までの累積GCDのGCDが、取り除いた \displaystyle N - 1 個のGCDになるので、これを i = 0 ~ N – 1 でまわせば終了
  • 端点だけ注意

なるほど〜〜〜!!!
区切って左から右からの gcd を累積的に求めれば良いのか!天才の発想ですね

これをふまえてコード書いたらこうなりました。

Python3
from fractions import gcd
N = int(input())
A = list(map(int, input().split()))
Asort = sorted(A)[:: -1]
L = [0] * N  # 左からi番目までのgcdをメモった配列
R = [0] * N  # 右からi番目までのgcdをメモった配列
L[0] = A[0]
R[0] = A[N - 1]
for i in range(1, N):
	L[i] = gcd(L[i - 1], A[i])
	R[i] = gcd(R[i - 1], A[N - 1 - i])
ans = max(L[N - 2], R[N - 2])
for j in range(1, N - 1):
	ans = max(ans, gcd(L[j - 1], R[N - j - 2]))
print(ans)

2 数取り出して約数全列挙の方針もある、これは天才ですね、そもそも gcd とか考えなくていいっぽい(疲れたのでコードは書きません)

D問題

\displaystyle N 個の整数が並んでおり、順に \displaystyle A_1, A_2, ..., A_N です。あなたはこの整数列に対して次の操作を好きなだけ行うことができます。
操作: \displaystyle 1 \leq i \leq N - 1 を満たす整数 \displaystyle i を選ぶ。 \displaystyle A_i\displaystyle A_{i + 1}\displaystyle -1 を乗算する。
操作終了後の整数列を \displaystyle B_1, B_2, ..., B_N とします。
\displaystyle B_1 + B_2 + ... + B_N の最大値を求めてください。

実験していくと感覚的に分かってくるのですが、 A の要素は、負の数が偶数個ある場合はすべて正の数に変換できるし、
奇数個ある場合は 1 つを除いて正の数に変換でき、かつ負の数のままになる 1 つの数は自由に選べる事がわかります。

てなわけで絶対値をとってあげて、絶対値が一番小さいのを負の数にしてあげればOK。

Dにしてはかなりカンタン? D はまともに過去問解いてないのでなんとも言えないのですが、かなりカンタンめな印象を受けました。

Python3
N = int(input())
A = list(map(int, input().split()))
B = []
count = 0  # Aの中の負の要素の個数
for i in range(N):
	if A[i] != abs(A[i]):
		count += 1
	B.append(abs(A[i]))
if count % 2 == 0:
	print(sum(B))
else:
	print(sum(B) - min(B) * 2)

サトゥー

やっと色が付きました。茶色です。早く水色になりたいです。

次こそ全完を目指したいです。

コメントを残す

メールアドレスが公開されることはありません。

日本語が含まれない投稿は無視されますのでご注意ください。(スパム対策)