AtCoder Beginner Contest 125 C,D 問題メモ
Rating対象が1199までとなる最後の(?)ABCでした。次からは1999まで対象。ふるえてねむれ。
C - GCD on Blackboard
問題
- 黒板に $N$ 個の整数 $A_1,A_2,...,A_N$
- 1つだけ好きな数字に書き換えられる
- 書き換える数字を上手く選んだとき、書き換えた後の $N$ 個の整数の最大公約数の最大値を求めよ
- $2 \le N \le 10^5$
- $1 \le A_i \le 10^9$
解法
数字を1つ選んだら他の $N-1$ 個の数字は変更しないので、答えはその $N-1$ 個の最大公約数 $G$ より大きくはならない。
よって変更する数字も $G$（の倍数）にすればよいので、言い換えると「数字を1つ除いて最大公約数を最大化せよ」という問題である。
1つ1つ数字を除いてみて $N-1$ 個の最大公約数を求めていると間に合わない。
2つの配列を使って事前計算し、共通の計算を省略する。
- $f[i]=A_1～A_i$（先頭 $i$ 個）の整数の最大公約数
- $b[i]=A_i～A_N$（末尾 $N-i+1$ 個）の整数の最大公約数
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)))
D - Flipping Signs
問題
- $N$ 個の整数 $A_1,A_2,...,A_N$ が並ぶ
- この整数列に対して次の操作を好きなだけ行える
- 隣り合う2数を選び、-1 を乗算する
- 操作終了後の整数列を $B_1,B_2,...,B_N$ とする
- 上手く操作を行ったときの、$B_1+B_2+...+B_N$ の最大値を求めよ
解法
体感的にはCより簡単なような。直感的に操作の推移がイメージしやすいからか。
- 正の数字をなるべく多くしたい
- 同じ数字に対し2回操作を行ったら元に戻るので、2回以上同じ2数で操作を行う意味は無い
2つ並んだ負の数があれば、操作を行うことで両方正にできる。
3 -5 -7 9
↓
3 5 7 9
1つだけの負の数があれば、操作を行うことでその数は正になり、左隣か右隣が負になる（0という可能性もあるが）。 「負の符号の位置が移動した」と捉えると、移動先の数に対しても繰り返し操作を行うことで、好きなように移動させることができる。
3 -5 7 9
↓
3 5 -7 9
↓
3 5 7 -9
なので、負を全部、たとえば右端に追いやってしまって、2個隣り合ったら消すという操作方針にすると、
- 初期状態で負の数が偶数個なら、全部正にできる
- 初期状態で負の数が奇数個なら、1個を除き正にできる。負の1個は好きな数字に移動できる
初期状態の負の数を数えて、偶数個なら絶対値を取って合計すればよい。奇数個なら、絶対値が最小の数のみを負にすればよい。
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)
