資源配分問題とも言われるタイプの問題。均等配分からの摂動で良さそう (嘘解法) だと騙すことを狙った！
問題概要
個の正の整数 
(総和を 
とする) が与えられたとき、
が最小値となる
を満たすような非負整数の組 
を求めよ。複数通り考えられる場合は辞書順最小のものを求めよ。
制約
解法
まず問題の見た目から、次のような嘘解法が多発することを狙った！
を満たす範囲でギリギリまで 
を高めた状態をまず作る
- この段階では
の総和は 
以下になるはず
- そこから少しずつ を高めていく
- それによる増分が最小になるような部分を 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;
}
,
とする
は
からの距離が
であるような
上の点を経由して
だけ離れた地点に位置する
