ACM-ICPC World Finals 2016 A解法

A: Balanced Diet

問題

Dannyはm種類の菓子を一つづつ食べる。今までの菓子iを食べた個数をs_iとする。
各菓子iの個数は割合f_iに近い値にしたい。
正確には、今まで食べたお菓子の総数をnとすると、任意のお菓子iは
https://chart.googleapis.com/chart?cht=tx&chl=nf_i-1%3Cs_i%3Cnf_i%2b1
を満たす必要がある。

すでに、k個のお菓子を食べており、それらは度のタイミングでも条件を満たしている。
今後、最適な順番で菓子を食べることで、最大でいくつのお菓子を食べることができるか求めよ。
無限に食べることができるならばそれを指摘せよ。

制約

m <= 10^5
k <= 10^5
f_iは整数の比で与えられ、f_i := a_i / (sum a_i)
1 <= a_i
sum a_i <= 10^5

入力のk個の菓子を順番に食べる場合、上の条件を満たしている。

解法

まず、無限に食べることができる場合とはどのような状態か。
n f_i が整数のとき、その間の s_i が取りうる値は n f_i 丁度である必要がある。
そして、n が sum a_i の倍数のとき、全ての i について、s_i は一通り。
以降、同じ順番で s_i を増やしていけば無限に食べることができる。
よって、n がsum a_i の倍数に成るまで一つづつ増やしていき、到達したら無限ということで打ち切ればよい。

食べるべき菓子の条件を出す。

  • 右2項 s_i < n f_i + 1 より: nを増加していくとある時点で s_i + 1 < n' f_i + 1 になり、n' 以降でs_iを増やしても良い。
  • 左2項 n f_i - 1 < s_i より: nを増加していくとある時点で n' f_i - 1 > s_i になり、n' の前にs_iを増やす必要がある。

上の条件より、食べてもいいお菓子の集合が得られ、下の条件よりなるべく早く食べたいお菓子が得られる。
これらを2つの優先度付きキューで貪欲に取り、食べてもいい菓子がない場合・食べていい時間を過ぎてしまった菓子が出た場合そこで終わり。
sum a_iの倍数に成るまで食べたら無限。

コード

#include<queue>
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)
#define eprintf(s...)  fprintf(stderr, s)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }

int K, M;
int A[100111];
LL a_sum;
LL S[100111];

pair<int, int> f(int i) {
    LL l, h;
    if (M == 1) {
	l = K+1;
	h = K+1;
    } else {
	l = K + (S[i] * a_sum - (LL)K * A[i]) / A[i] + 1;
	h = K + (a_sum * (S[i] + 1) - (LL)K * A[i] - 1) / A[i] + 1;
	amax(l, (LL)K+1);
    }
    if (l > h) return make_pair(-1, -1);
    else return make_pair(l, h);
}

int main() {
    scanf("%d%d", &M, &K);
    REP (i, M) {
	scanf("%d", A+i);
	a_sum += A[i];
    }
    REP (i, K) {
	int x;
	scanf("%d", &x);
	x--;
	S[x]++;
    }

    int ans = 0;
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > Q, R;
    REP (i, M) {
	pair<int, int> p = f(i);
	if (p.first < 0) { goto END; }
	p.second = i;
	Q.push(p);
    }

    while (K % a_sum) {
	while (!Q.empty() && Q.top().first <= K + 1) {
	    pair<int, int> p = Q.top(); Q.pop();
	    int i = p.second;
	    p = f(i);
	    p = make_pair(p.second, i);
	    R.push(p);
	}

	if (R.empty() || R.top().first <= K) { ans--; goto END; }

	pair<int, int> p = R.top(); R.pop();
	int i = p.second;
	S[i]++;
	K++;
	ans++;
	p = f(i);
	if (p.first < 0) { goto END; }
	p.second = i;
	Q.push(p);
    }

    puts("forever");
    return 0;

END:;
    printf("%d\n", ans);
    return 0;
}