AtCoder Beginner Contest 125 C,D 問題メモ

AtCoder Beginner Contest 125

Rating対象が1199までとなる最後の(?)ABCでした。次からは1999まで対象。ふるえてねむれ。

C - GCD on Blackboard

問題

  • 黒板に $N$ 個の整数 $A_1,A_2,\ldots,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,\ldots,A_N$ が並ぶ
  • この整数列に対して次の操作を好きなだけ行える
    • 隣り合う2数を選び、-1 を乗算する
  • 操作終了後の整数列を $B_1,B_2,\ldots,B_N$ とする
  • 上手く操作を行ったときの、$B_1+B_2+\ldots+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)

programming_algorithm/contest_history/atcoder/2019/0427_abc125.txt · 最終更新: 2019/04/27 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0