CPSCO2019 Session3 : G - Grand Election

ちょっと手間取った。
https://atcoder.jp/contests/cpsco2019-s3/tasks/cpsco2019_s3_g

問題

N要素の正整数列A[i]が与えられる。
Xをx[1]+x[2]+...+x[N]=XとなるようN個の非負整数列xに分解するとき、

が最小となるxを求めよ。
値が同じになるxが複数ある場合、辞書順最小値を求めよ。

解法

x[i]を1ずつインクリメントしていくと、最初は総和が1/A[i]ずつ減少し、X/Aに到達する前後で少し変わった変化をして、その後は1/A[i]ずつ増加する、と最大3通りの変化をする。
なので、(減少量, インデックス, 個数)のtupleをソートし、減少量が大きくインデックスが小さいものから順に計X個選ぶようにすればよい。

減少量のソートには、有理数か精度の高い小数型が必要なので注意。

int N;
ll X,S;
ll A[1010101];
ll R[1010101];

bool cmp(vector<ll> L,vector<ll> R) {
	__int128_t A=__int128_t(L[0])*R[1];
	__int128_t B=__int128_t(L[1])*R[0];
	
	if(A>B) return 1;
	if(A<B) return 0;
	return L[2]>R[2];
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>X;
	FOR(i,N) cin>>A[i], S+=A[i];
	
	
	vector<vector<ll>> V;
	FOR(i,N) {
		ll num=X*A[i]/S;
		V.push_back({1,A[i],i,num});
		V.push_back({abs(num*S-X*A[i])-abs((num+1)*S-X*A[i]),A[i]*S,i,1});
		V.push_back({-1,A[i],i,1LL<<30});
	}
	sort(ALL(V),cmp);
	
	FORR(v,V) {
		ll num=min(X,v[3]);
		//cout<<v[2]<<" "<<num<<" "<<v[0]<<"/"<<v[1]<<endl;
		X-=num;
		R[v[2]]+=num;
	}
	
	FOR(i,N) cout<<R[i]<<endl;
}

まとめ

有理数とかmodintとかのクラス、真面目に作っておこうかなぁ。