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

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

• 問題へのリンク

問題概要

個の正の整数 (総和を とする) が与えられたとき、

• 
• が最小値となる

を満たすような非負整数の組 を求めよ。複数通り考えられる場合は辞書順最小のものを求めよ。

制約

• 
• 
• 

解法

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

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

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

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

正しい解法

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

---

初期状態では はすべて 0 であるとする。スコアは初期状態では である。今から以下の操作をちょうど 回行う。

• を一つ選んで を 1 増やす

このとき、スコアは

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

---

たとえば、、 のときは、次のようになる。たとえば から へと増やすとき、スコアは だげ減少する。一方 から へと増やすとき、スコアは だげ減少する。

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

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

---

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

---

実装上は、ソートか 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;
}