AtCoder ABC182
2020-11-08(日)に行われたAtCoderBeginnerContest182の問題をA問題から順に考察も踏まえてまとめたものとなります．
問題は引用して記載していますが，詳しくはコンテストページの方で確認してください．
コンテストページはこちら
公式解説
A問題 twiblr
問題文
あなたは twiblr という SNS をしています。
twiblr では、フォロー数が$2×($フォロワー数$)+100$を超えない範囲でフォロー数を増やすことができます。
あなたの現在のフォロワー数は$A$で、フォロー数は$B$です。
フォロー数はあといくつ増やせますか?
a, b = map(int, input().split())
print(2*a+100-b)
B問題 Almost GCD
問題文
数列$A(A_1,A_2,A_3,…,A_N)$が与えられます。
正の整数$k$の GCD 度を、$A_1,A_2,A_3,…,A_N$のうち$k$で割り切れるものの数と定義します。
$2$以上の整数のうち GCD 度が最大になるものを一つ求めてください。 GCD 度が最大のものが複数ある場合どれを出力しても構いません。
$p$の GCD 度 $\geq p×k$ の GCD 度 ($p$は素数，$k$は自然数)
となることから，素数だけ調べればと思って実装しましたが，$N$が小さいので不要でしたね．
他にも，ループを抜ける条件などいろいろ書いていますが，早く解くコンテストにおいてこのあたりも不要でした．
n = int(input())
a_list = list(map(int, input().split()))
sosuu_list = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]
max_a = max(a_list)
max_count = 0
ans = 0
for i in sosuu_list:
if max_a < i:
break
count = 0
for a in a_list:
if a % i == 0:
count += 1
if count > max_count:
max_count = count
ans = i
if max_count == len(a_list):
break
print(ans)
C問題 To 3
問題文
各桁に$0$が出現しないような正の整数$N$が与えられます。
$N$の桁数を$k$とします。$N$の桁を$0$個以上$k$個未満消して、残った桁をそのままの順序で結合することで$3$の倍数を作りたいです。
$3$の倍数を作ることができるか判定し、作ることができるなら作るのに必要な最少の消す桁数を求めてください。
あまりいいコードではないけど，提出したものそのまま．
丁寧に場合分け．
n = input()
n_list = []
for i in range(len(n)):
k = int(n[i])
k = k % 3
if k == 2:
n_list.append(-1)
else:
n_list.append(k)
if sum(n_list) % 3 == 0:
print(0)
else:
t = sum(n_list) % 3
if t == 2:
p_one = n_list.count(1)
n_one = n_list.count(-1)
if n_one > 0 and len(n_list) - 1 > 0:
print(1)
elif p_one > 1 and len(n_list) - 2 > 0:
print(2)
else:
print(-1)
else:
p_one = n_list.count(1)
n_one = n_list.count(-1)
if p_one > 0 and len(n_list) - 1 > 0:
print(1)
elif n_one > 1 and len(n_list) - 2 > 0:
print(2)
else:
print(-1)
D問題 Wandering
問題文
数列$A_1,A_2,A_3,…,A_N$が与えられます。 この数列は負の要素を含むかもしれません。
数直線上の座標$0$に置かれているロボットが、以下の動作を順に行います。
・正の向きに$A_1$進む。
・正の向きに$A_1$進み、正の向きに$A_2$進む。
・正の向きに$A_1$進み、正の向きに$A_2$進み、正の向きに$A_3$進む。
⋮
・正の向きに$A_1$進み、正の向きに$A_2$進み、正の向きに$A_3$進み、… 、正の向きに$A_N$進む。
動作開始時から終了時までのロボットの座標の最大値を求めてください。
わりかしうまく解けた気がする．
各ステップで，一番正の向きに行けるときを一回の計算で求めることができるようにすることで，TLEを回避しました．
n = int(input())
a_list = list(map(int, input().split()))
b_list = [0] * n
b_list[0] = a_list[0]
c_list = [0] * (n + 1)
c_list[1] = b_list[0]
for i in range(1, n):
b_list[i] = b_list[i - 1] + a_list[i]
c_list[i + 1] = c_list[i] + b_list[i]
max_x = 0
max_b = b_list[0]
x = 0
for i in range(n):
x = c_list[i]
if max_b < b_list[i]:
max_b = b_list[i]
x += max_b
if x > max_x:
max_x = x
print(max_x)
今回もD問題までいいペースで解けたのですが，E問題で詰まってしまいました．
そろそろ，5完できるように過去の問題も時間作って解いていけたらと思っております．
最後まで読んでいただきありがとうございました．