はまやんはまやんはまやん

hamayanhamayan's blog

Kuroni and the Punishment [Ozon Tech Challenge 2020 (Div.1 + Div.2, Rated, T-shirts + prizes!) F]

https://codeforces.com/contest/1305/problem/F

前提知識

解説

https://codeforces.com/contest/1305/submission/72492279

手の付け所の1つとして最適方針を考えるというのがある。
この仮定で重要なものを得ることができる。
全部のgcdを取った結果を2にしたいと考えると、奇数の要素を+1すれば達成できるので、
答えがNを超えることはない。

ここから得られるものが何かというと、ある最適解が存在して、各要素に必要な操作回数が割り当たっているとする。
その要素のうち1つをランダムで選んだ時に、必要な操作回数が1以下である要素を選ぶ確率は少なくとも1/2である。
これを得られるかが最も重要。
一番意地悪な最適解は、「0 2 0 2 0 2 0 2 0 2... 」というやつで、これが1/2。

よって、乱択アルゴリズムを使う。
回数はお好みだが、googleで計算してみると10回でも99.9%成功と出ているので、10でも行けそうな雰囲気。
自分は20にしました。
必要な操作回数が1以下であろう要素を乱択で取り出してくる。
操作回数が1以下ということは、A[i]かA[i]-1かA[i]+1の3択になる。
全部に対して、計算してみて、操作回数が最小のものを選ぼう。

これからはA[i]のみで考える。(±1のやつは置き換えて読むだけ)
A[i]はもうこれ以上操作せず、ほかのやつを操作することで、gcdを2以上にしたい。
と考えると、gcdはA[i]の約数になることが分かる。
だが、1012だと約数は103個くらいあるものもある。ちょっと数が多い。
実際は約数ではなく、素因数だけを考えるだけでよい。
gcdを固定したときの必要な操作回数の総和は、それぞれの要素についてA[j] mod gcdが0となるようにA[j]を
操作する最小回数の総和となる。
具体的にはmin(A[j] % gcd, A[j] - (A[j] % gcd))
gcdに合成数abを使うとき、その因数aを使うときで、それぞれの要素での最小回数を考えると、
どのような場合でも因数aの方が同じか小さくなる。
雰囲気をいかに書いておく。

ab  |  x      |  
a   |  x |    |  
細かく割ってある方がmodで0の距離が近くなる!  

実装はそれほど難しくない。
解説を難しく感じたらコードを見たほうが簡潔かもしれない。

int N; ll A[201010];
//---------------------------------------------------------------------------------------------------
ll calc(ll gcd) {
    ll res = 0;
    rep(i, 0, N) {
        if (A[i] < gcd) res += gcd - A[i];
        else res += min(A[i] % gcd, gcd - (A[i] % gcd));
    }
    return res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];

    ll ans = infl;
    rep(_, 0, 20) {
        int target = getrand(0, N - 1);
        rep(d, -1, 2) if(2 <= A[target] + d) {
            auto vp = enumPrimeOnly(A[target] + d);
            fore(p, vp) chmin(ans, calc(p));
        }
    }
    cout << ans << endl;
}