Rating対象が1199までとなる最後の(?)ABCでした。次からは1999まで対象。ふるえてねむれ。
数字を1つ選んだら他の $N-1$ 個の数字は変更しないので、答えはその $N-1$ 個の最大公約数 $G$ より大きくはならない。
よって変更する数字も $G$（の倍数）にすればよいので、言い換えると「数字を1つ除いて最大公約数を最大化せよ」という問題である。
1つ1つ数字を除いてみて $N-1$ 個の最大公約数を求めていると間に合わない。
2つの配列を使って事前計算し、共通の計算を省略する。
A 12 24 18 27 36 --------------------- f 12 12 6 3 3 b 3 3 9 9 36
そうしたら、$A_i$ を除いた場合の最大公約数とは、$f[i-1]$ と $b[i+1]$ の最大公約数となる。
A3 = 18 を除いた場合の最大公約数 f 12 ⑫ 6 3 3 b 3 3 9 ⑨ 36 → 12 と 9 の最大公約数 = 3 A4 = 27 を除いた場合の最大公約数 f 12 12 ⑥ 3 3 b 3 3 9 9 ㊱ → 36 と 6 の最大公約数 = 6
一番端を除く場合だけ、ちょっと注意。
A1 = 12 を除いた場合の最大公約数 f 12 12 6 3 3 b 3 ③ 9 9 36 → 3
A5 = 36 を除いた場合の最大公約数 f 12 12 6 ③ 3 → 3 b 3 3 9 9 36
この中の最大値を求めればよい。
Pythonの標準ライブラリにある fractions.gcd(a,b) は、片方が0の場合、もう片方の数をそのまま返す。
よって、端の数字を除く場合の処理のため便宜的に0を仕込み、indexをずらしておくと、簡潔に記述できる。
f 0 12 12 6 3 b 3 9 9 36 0 --------------------- gcd 3 3 3 6 3
from fractions import gcd
n = int(input())
aaa = list(map(int, input().split()))
p = aaa[0]
f = [0, p]
for a in aaa[1:-1]:
p = gcd(p, a)
f.append(p)
aaa.reverse()
p = aaa[0]
b = [0, p]
for a in aaa[1:-1]:
p = gcd(p, a)
b.append(p)
b.reverse()
print(max(gcd(p, q) for p, q in zip(f, b)))
体感的にはCより簡単なような。直感的に操作の推移がイメージしやすいからか。
2つ並んだ負の数があれば、操作を行うことで両方正にできる。
3 -5 -7 9
↓
3 5 7 9
1つだけの負の数があれば、操作を行うことでその数は正になり、左隣か右隣が負になる（0という可能性もあるが）。 「負の符号の位置が移動した」と捉えると、移動先の数に対しても繰り返し操作を行うことで、好きなように移動させることができる。
3 -5 7 9
↓
3 5 -7 9
↓
3 5 7 -9
なので、負を全部、たとえば右端に追いやってしまって、2個隣り合ったら消すという操作方針にすると、
初期状態の負の数を数えて、偶数個なら絶対値を取って合計すればよい。奇数個なら、絶対値が最小の数のみを負にすればよい。
n = int(input())
aaa = list(map(int, input().split()))
bbb = list(map(abs, aaa))
if sum(1 for a in aaa if a < 0) % 2 == 0:
ans = sum(bbb)
else:
ans = sum(bbb) - min(bbb) * 2
print(ans)