Saiko~ No Contesuto #02 すごろくチキンレース

2015/11/01 (Sun) Hackerrank 二分探索 累積和

問題

問題文

方針

条件を満たすにはサイコロの目が全て等しく，さらにそれが $N$ の約数でないといけないです． 各約数に対して，全ての目をその値にするのに必要な魔法の数は累積和と二分探索で求まります．

事前に $a$ をソートし，前からの累積和 $s[i] = a[0]+a[1]+ \cdots + a[i-1]$ を計算しておきます． $k$ を $a[i]$ が $x$ 以上になる最大の $i$ とします． すると，インデックスが $k$ 未満の部分は $(x - a[0]) + \cdots + (x - a[k-1]) = xk - s[k]$ 回， $k$ 以上の部分は $(a[k] - s) + \cdots + (a[m-1] - s) = s[m] - s[k] - x(m-k)$ 回の魔法が必要となります．

$d(n)$ を $n$ の約数の数とすると全体で $O(m + d(n)\log{m})$ です．

実装

ll n,m;
ll a[300010], s[300010];

ll query(ll x){
    int k = lower_bound(a, a+m, x) - a;
    ll res = 0;
    res += x*k - s[k];
    res += s[m] - s[k] - x*(m-k);
    return res;
}

ll solve(){
    sort(a, a+m);
    s[0] = 0;
    rep(i,m) s[i+1] = a[i] + s[i];
    ll ans = query(1);
    for(ll i = 1; i*i <= n; i++){
        if(n%i == 0){
            if(i <= n) ans = min(ans, query(i));
            if(n/i <= n) ans = min(ans, query(n/i));
        }
    }
    return ans;
}

int main(){
    scanf("%lld%lld", &n, &m);
    rep(i,m) scanf("%lld", a+i);
    cout << solve() << endl;
}