AtCoder Beginner Contest 136 E - 今日から始める競プロ日記
はじめに
AtCoder Beginner Contest ( ABC ) 136 に参加。
今日はA～Dまで解いた。
Eが解けなかったので解説動画を見ながら解き方をまとめてみる。
（説明が下手くそなので参考程度に）
参考
公式の解説動画を参考にしました。 いつもありがとうございます。
ABC136の結果
- パフォーマンス：1109
- レート：706→755（+49）
E - Max GCD
長さNの整数列A1, A2, ......, ANが与えられる。
この整数列に対して、Ai に1を足し、Aj から1を引く、という操作を最大でK回行える。
操作後の整数列において、すべての要素を割り切ることができる正の整数の最大値を求める。
例（サンプル1）
与えられた整数列：8 20
// 8から1引き、20に1を足す 8 - 1 = 7 20 + 1 = 21 // 7の倍数になっていることが分かる 7 % 7 = 0 21 % 7 = 0
よって答えは 7 。
解き方
制約が
1 <= N <= 500 1 <= A <= 10^6 1 <= K <= 10^9
となっているので、可能性のあるすべての値を試そうとしてもTLEになる。
そこで、どうやったら計算量を減らせるかを工夫する必要があり、 まず以下の（1）,（2）について考える。
（1）数列全体の和は変化しない
まず、「 Ai に1を足し、Aj から1を引く」という操作を何回行っても、数列全体の和は変化しない。
8 + 20 = 28 //操作を一回行う 8 - 1 = 7 20 + 1 = 21 7 + 21 = 28 //もう一回操作を行ってみる 7 - 1 = 6 21 + 1 = 22 6 + 22 = 28
何回操作を行っても和は28。
よって、数列全体の和はどうやっても変化しない。
（2） 数列のすべての要素の最大公約数は、数列全体の和の約数でもある
数列のすべての要素の最大公約数（公約数）を求めてみると、 その値が数列全体の和の約数でもあることが分かる。
例として次の数列を考える。
14 21 35
この数列の要素はすべて7の倍数。
14 = 7 * 2 21 = 7 * 3 35 = 7 * 5
和を求めてみる。
14 + 21 + 35 = 70
当たり前だが、ここで求められた和である70は7の倍数。
70 = 7 * 10
この足し算はつまりこういうこと。
14 + 21 + 35 = (7 * 2) + (7 * 3) + (7 * 5) = 7 * 10 = 70
よって、数列のすべての要素の最大公約数（公約数）は、数列全体の和の約数でもある。
（1）,（2）より、数列全体の和の約数が答えになる
(1), (2)から、数列全体の和の約数の中に、 操作後の数列のすべての要素の最大公約数が存在することが分かった。
つまり、和の約数をすべて求めて、それぞれが条件を満たすか確認すればいいだけになった。
条件は二つ。
- 操作を行って整数列の最大公約数が、数列全体の和の約数になるかどうか
- 操作回数がK以下で済むかどうか
整数列の各要素をマイナス側とプラス側に分ける
条件を満たすか調べる。
例として次の整数列について考える。
1 1 2 2 3 5
和を求める。
1 + 1 + 2 + 2 + 3 + 5 = 14
和の約数を求める。
14の約数：1, 2, 7, 14
よって、答えは1 2 7 14のどれかである。
次に、整数列の要素をプラス側とマイナス側に分ける。
つまり、操作において+1する側と-1する側に分けるということ。
先ほどの整数列をもう一度見る（ちなみにソート済みであることが重要）。
1 1 2 2 3 5
ここで、この整数列の最大公約数を14にしたいとする。
つまり、各整数を14の倍数にしたい。14 × 0 = 0より0にしてもよい。
例えば左半分の1 1 2を0にして、右半分2 3 5を14にしようとする。
1 1 2 | 2 3 5
境界は真ん中
左半分 0 - 1 = -1 0 - 1 = -1 0 - 2 = -2 合計A = -4 右半分 14 - 2 = 12 14 - 3 = 11 14 - 5 = 9 合計B = 32
一度の操作では+1と-1を一回ずつ行うので、T回操作を行うと、合計でA=-T、B=Tであり、-A = Bとなるはずである。
つまり、-A != Bの場合はその操作は間違いである。
次に、左側と右側の境目を一つ右にずらしてみる。
1 1 2 2 | 3 5
左側 0 - 1 = -1 0 - 1 = -1 0 - 2 = -2 0 - 2 = -2 合計A = -6 右側 14 - 3 = 11 14 - 5 = 9 合計B = 20
これでも-A != Bであるため、これも間違いである。
さらに、境目を一つ右にずらしてみる。
1 1 2 2 3 | 5
左側 0 - 1 = -1 0 - 1 = -1 0 - 2 = -2 0 - 2 = -2 0 - 3 = -3 合計A = -9 右側 14 - 5 = 9 合計B = 9
このとき-A = Bであり、この操作は実行可能である。
また、このときの操作回数はB回となる。
このようにして、 ある最大公約数にするために操作が何回必要が求めることができる。
あとはこの解き方を実装すればよい（難しい......）。
set
解説でsetが使われていたのでちょっと調べてみた。
以下の記事を参考。
コード
解説動画で実装していたsnukeさんのコードを参考。
おわりに
考え方はなんとなくわかったけど、 実装はできる気がしない。
