けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

CPSCO2019 Session3 G - Grand Election (800 点設定)

資源配分問題とも言われるタイプの問題。均等配分からの摂動で良さそう (嘘解法) だと騙すことを狙った!

問題概要

 N 個の正の整数  a_{1}, \dots, a_{N} (総和を  A とする) が与えられたとき、

  •  x_{1} + \dots + x_{N} = X
  •  |\frac{x_{1}}{a_{1}} - \frac{X}{A}| + \dots + |\frac{x_{1}}{a_{1}} - \frac{X}{A}| が最小値となる

を満たすような非負整数の組  (x_{1}, \dots, x_{N}) を求めよ。複数通り考えられる場合は辞書順最小のものを求めよ。

制約

  •  1 \le N \le 10^{5}
  •  1 \le X \le 10^{9}
  •  1 \le a_{i} \le 100

解法

まず問題の見た目から、次のような嘘解法が多発することを狙った!

  •  \frac{x_{i}}{a_{i}} \le \frac{X}{A} を満たす範囲でギリギリまで  x_{i} を高めた状態をまず作る
    • この段階では  x の総和は  X 以下になるはず
  • そこから少しずつ  x を高めていく
    • それによる増分が最小になるような部分を Greedy に選んでいく

しかしコーナーケースとして、次のようなケースがある!

f:id:drken1215:20201027140800p:plain

f:id:drken1215:20201027140828p:plain

これらのコーナーケースを作るのに、とても苦労した!!実際テキトーにケースを作ると、上記の嘘解法が大体正しいのだ。

 

正しい解法

この問題を次のような問題と読み替えよう!


初期状態では  x_{1}, \dots, x{N} はすべて 0 であるとする。スコアは初期状態では  N|\frac{X}{A}| である。今から以下の操作をちょうど  K 回行う。

  •  i を一つ選んで  x_{i} を 1 増やす

このとき、スコアは

 |\frac{x_{i}}{a_{i}} - \frac{X}{A}| - |\frac{x_{i} + 1}{a_{i}} - \frac{X}{A}|

だけ減少する。スコアの最小値を求めよ。


たとえば、 a = (2, 3, 5) X = 13 のときは、次のようになる。たとえば  x_{1} = 0 から  x_{1} = 1 へと増やすとき、スコアは  \frac{1}{2} だげ減少する。一方  x_{1} = 2 から  x_{1} = 3 へと増やすとき、スコアは  \frac{1}{10} だげ減少する。

f:id:drken1215:20201027141717p:plain

そして、問題は、上のように各  i について、 x_{i} を 1 増やしたときのスコアの減少分を並べて行ったときに、これらの値から  X 個を左詰めで選ぶ方法のうち、総和が最大のものを求める問題ということになる。

ここで注目したいことは、どの  i に対しても、「 x_{i} を 1 増やしたときのスコアの減少分」は広義単調減少だということだ。このことから、次にことがいえる


 i についての系列を、全部まとめたものをソートして、大きい順に  X 個とればよい


実装上は、ソートか priority_queue を使えば OK。

 

コード

精度の問題から、有理数型か、long double 型が必要となることに注意。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

long long calc_gcd(long long a, long long b) {return b ? calc_gcd(b, a % b) : a;}
struct frac {
    long long first, second;

    using D = long double;
    inline frac normalize() {
        if (second < 0) {first = -first; second = -second;}
        long long d = calc_gcd(abs(first), abs(second));
        if (d == 0) {first = 0; second = 1;}
        else {first /= d; second /= d;}
        return *this;
    }
    frac(long long f = 0, long long s = 1) : first(f), second(s) { normalize(); }
    inline D to_d() const { return D(first) / second; }
    inline frac operator - () { (*this).first *= -1; return (*this); }
    inline const frac& operator = (long long a) { *this = frac(a, 1); return *this; }
    inline const frac& operator += (const frac& a);
    inline const frac& operator += (long long a);
    inline const frac& operator -= (const frac& a);
    inline const frac& operator -= (long long a);
    inline const frac& operator *= (const frac& a);
    inline const frac& operator *= (long long a);
    inline const frac& operator /= (const frac& a);
    inline const frac& operator /= (long long a);
    inline friend ostream& operator << (ostream& s, const frac& f) { 
        s << f.first; if (f.second != 1) s << "/" << f.second; return s;
    }
};
inline bool operator == (const frac &a, const frac&b) {
    return a.first * b.second == a.second * b.first;
}
inline bool operator != (const frac &a, const frac &b) { return !(a == b); }
inline bool operator < (const frac& a, const frac& b) {
    return a.first * b.second < a.second * b.first;
}
inline bool operator > (const frac& a, const frac& b) { return b < a; }
inline bool operator <= (const frac& a, const frac& b) {
    return a.first * b.second <= a.second * b.first;
}
inline bool operator >= (const frac& a, const frac& b) { return b <= a; }
inline frac operator + (const frac& a, const frac& b) {
    frac res;
    res.first = a.first * b.second + a.second * b.first;
    res.second = a.second * b.second;
    res.normalize();
    return res;
}
inline frac operator - (const frac& a, const frac& b) {
    frac res;
    res.first = a.first * b.second - a.second * b.first;
    res.second = a.second * b.second;
    res.normalize();
    return res;
}
inline frac operator * (const frac& a, const frac& b) {
    frac res;
    res.first = a.first * b.first;
    res.second = a.second * b.second;
    res.normalize();
    return res;
}
inline frac operator / (const frac& a, const frac& b) {
    frac res;
    res.first = a.first * b.second;
    res.second = a.second * b.first;
    res.normalize();
    return res;
}
inline frac abs(const frac& a) {
    frac res; res = a; res.normalize(); 
    if (res.first < 0) res.first = res.first * (-1);
    return res;
}
inline const frac& frac::operator += (const frac& x) {*this = *this + x; return *this;}
inline const frac& frac::operator += (long long x) {*this = *this + x; return *this;}
inline const frac& frac::operator -= (const frac& x) {*this = *this - x; return *this;}
inline const frac& frac::operator -= (long long x) {*this = *this + x; return *this;}
inline const frac& frac::operator *= (const frac& x) {*this = *this * x; return *this;}
inline const frac& frac::operator *= (long long x) {*this = *this * x; return *this;}
inline const frac& frac::operator /= (const frac& x) {*this = *this / x; return *this;}
inline const frac& frac::operator /= (long long x) {*this = *this / x; return *this;}



int N;
long long X, A;
vector<long long> a;


frac eval(long long x, int i) {
    return abs(frac(x, a[i]) - frac(X, A));
}

int main() {
    cin >> N >> X;
    a.resize(N);
    A = 0;
    for (int i = 0; i < N; ++i) cin >> a[i], A += a[i];

    for (int i = 0; i < N; ++i) {
        long long lim = X * a[i] / A;
    }

    vector<long long> res(N, 0);
    priority_queue<pair<frac,int> > que;
    for (int i = 0; i < N; ++i) que.push({eval(0, i) - eval(1, i), i});
    long long X2 = X;
    while (X2 > 0) {
        auto p = que.top(); que.pop();
        int i = p.second;
        long long x = res[i];

        frac diff = eval(x, i) - eval(x+1, i);
        frac diff2 = eval(x+1, i) - eval(x+2, i);
        
        if (diff != diff2) {
            res[i] += 1;
            --X2;
            que.push({diff2, i});
        }
        else if (x == 0) {
            long long lim = X * a[i] / A;
            if (X2 >= lim) {
                X2 -= lim;
                res[i] += lim;
                frac diff3 = eval(lim, i) - eval(lim+1, i);
                que.push({diff3, i});
            }
            else {
                res[i] += X2;
                X2 = 0;
            }
        }
        else {
            res[i] += X2;
            X2 = 0;
        }
    }

    for (int i = 0; i < N; ++i) cout << res[i] << endl;
}