AtCoder Beginner Contest 125 C,D 問題メモ

AtCoder Beginner Contest 125

AtCoder Beginner Contest 125 解説配信 - YouTube

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)