ABC136 E MaxGCD

https://atcoder.jp/contests/abc136/submissions/6726558

所感

時間があればできた……？(怪しい)

問題概要

長さNの数列Aがある。以下の操作をK回以下行って得られるN個の数のGCDを最大化せよ。

i != j のA_i, A_j について、A_iに1を足し、A_jに-1を足す。  

取った方針

GCDをmに固定して考える。(典型)
mod m を取った数列Bを考えると、(典型)この総和が0(mod m)になることが必要。
上記の条件を満たし、移動する数(操作の回数)がK以下であることが必要。
これはmod m を取った値の総和から一番大きいものを引いたもの。(大嘘)
↑でWAしたあと、増やしてmの倍数になるパターンと減らしてmの倍数になるパターンの存在に気づき、コスト(増減する数)が小さい方を取ればよい(大嘘)と思い時間切れで死亡
そもそも解の候補を全探索していたが、本当は解の範囲は1<=x<=10⁶ でなく 1<=x<=500*10⁶なので間に合う解法ではない

正しい方針

GCD をmに固定して考える。(OK)
mod m をとると、増やしてmの倍数になるパターンと減らしてmの倍数になるパターンが存在する。(OK)
増やす量と減らす量が等しい必要があり、これはソートして累積和をあらかじめ計算しておくことで全探索ができる。(NG)(デバッグで気づけたはず)
ここまででNlogNで判定ができる。
解の候補を全探索するとmax(A)NlogNで間に合わないが、解の候補はAの和の約数(GCDがmの時、Aはcmで表せるはずなので)であり、これはsqrt(Nmax(A))なので間に合う。(NG)(時間があっても怪しいと思う)

得られた知見

・数a, b, c...のGCDの候補はa+b+c...の約数(約数の定義から自明)(a, b, c...のGCDがmである -> a, b, cはmを約数に持つ なので)
・公約数 -> mod を取ると余りだけを考えられて見通しがよくなる

解くのに必要な要素

・GCD の候補は総和の約数とすることで探索範囲をsqrt(N)にできる

周辺調査によって得られた知見

特になし