Codeforces Round #432 Div.2 D / Div.1 B - Arpa and a list of numbers

http://codeforces.com/contest/850/problem/B

問題概要

N要素の数列Aが与えられる。以下の操作を好きなだけ繰り返して、数列の全要素のGCDが1でなくなるようにしたい。目的を達成する最小のコストを求めよ。

  • 操作1. コストxで数列から任意の1要素を取り除く
  • 操作2. コストyで数列の任意の1要素に1を足す

1 <= n <= 5×105

1 <= x, y <= 109

1 <= a <= 106

解法

最終的なGCDを固定して考える(この数をgとする)。gの倍数ごとに区間を分けて、その区間ごとに数えるとうまいこといく。

具体的には(kg, (k+1)g]のような区間に含まれる数がgを約数に持つためには、(k+1)gのところまでインクリメントされるしかない。何回目のインクリメントまでがxより得かはxをyで割れば出る。つまり上の区間のうち決まった境界より左の数はxで処理し、右の数はy×距離で処理することになる。境界を仮にmとすると、前者はkg~mの区間に現れる数を累積和すれば求まる。後者は距離に応じてxの係数がインクリメントするので単純な累積和だとだめで、区間内にその数がn回現れるならn回カウントされるような累積和を使いたい。これはxで使った累積和に対してさらに累積和を取ると得られるのでそれを使う(伝われ)、あとそれだけだと区間左外の分もカウントしてしまってるのでそれは良い感じに引く。

頑張ったんですが説明無理だったので要点だけ言うと①GCDを固定します②固定したGCDの倍数ごとに区間を区切ります③区間ごとに累積和を良い感じにやってO(1)で計算します という感じです。①はO(max(A)), ②はならしでO(log(max(A)))のあわせてO(max(A)log(max(A))).

感想

そもそも解法がむずい上に境界まわりの処理が鬼すぎる、あと解法を書くのもむずすぎる

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;
 
 
void main() {
    auto s = readln.split.map!(to!long);
    auto N = s[0].to!int;
    auto X = s[1];
    auto Y = s[2];
    auto A = readln.split.map!(to!int).array;
    A.sort();
    
    const int MAX = 10^^6 + 1;
    const int border = ((X - 1) / Y).to!int;


    auto cnt = new long[](MAX * 2); 
    auto cntsum = new long[](MAX * 2);
    
    foreach (i; 0..N)
        cnt[A[i]] += 1;
    foreach (i; 0..MAX*2-1)
        cnt[i + 1] += cnt[i];
    foreach (i; 0..MAX*2-1)
        cntsum[i + 1] += cntsum[i] + cnt[i + 1];


    long ans = 1L << 59;
    
    foreach (g; 2..MAX) {
        long tmp = 0;
        for (int l = 1; l < MAX; l += g) {
            int r = l + g - 1;
            int m = max(l, r - border);
            long y = Y * (cntsum[r - 1] - cntsum[m - 1] - cnt[m - 1] * (r - m));
            long x = X * (cnt[m - 1] - cnt[l - 1]);
            tmp += x + y;
        }
        ans = min(ans, tmp);
    }

    debug {
        cnt[0..20].writeln;
        cntsum[0..20].writeln;
    }
    
    ans.writeln;
}