Google Code Jam 2017 Round 1A : B. Ratatouille

問題文わかりにくすぎる…。
https://code.google.com/codejam/contest/5304486/dashboard#s=p1&a=2

問題

料理を1皿作る際、N種の具材がありそれぞれの想定必要量はR[i]である。
ただし、厳密にこれを満たす必要はなく、R[i]の[90%,110%]の範囲でブレがあってもよいが。

料理を作るために各具材を発送したい。
各具材iについて、それぞれP種類のパッケージjがあり、そのパッケージにはQ[i][j]の量の具材が入る。

各具材についてパッケージを1種ずつ取り出して料理キットとして発送する。
その際料理が具材を余らせることなく作れるようにしたい。
作れる皿数は正の整数皿以上なら構わない)
各パッケージは1回ずつしか使えない。

最大いくつのキットを作ることができるか。

解法

貪欲で解く。

各パッケージついて、料理を何皿作れるかのRangeを求めよう。
整数皿分を作れないパッケージはこの時点で除いてしまおう。
そうすると、各具材についてRangeが共通部分を持つようなパッケージ群を選ぶ問題になる。

各具材、未使用のパッケージのうち最小量のものを選んでみる。
皿数のRangeが共通部分を持たない場合、Rangeの最大値が小さすぎるものを取り除く、ということを貪欲に行うと、いずれ各具材のRangeが共通部分を持つようになる(か、もしくはそれ以上キットを作れない)、

int N,P;
int R[100];
vector<int> Q[100];
int ID[100];
int LL[100][100];
int RR[100][100];

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>N>>P;
	FOR(i,N) {
		cin>>R[i];
		R[i]*=10;
	}
	FOR(y,N) {
		Q[y].clear();
		FOR(x,P) {
			cin>>j;
			j*=10;
			int LLL=(j+(R[y]*11/10)-1)/(R[y]*11/10);
			int RRR=j/(R[y]*9/10);
			if(LLL<=RRR) Q[y].push_back(j);
		}
		sort(ALL(Q[y]));
		
		FOR(x,Q[y].size()) {
			LL[y][x]=max(1,(Q[y][x]+(R[y]*11/10)-1)/(R[y]*11/10));
			RR[y][x]=(Q[y][x])/(R[y]*9/10);
		}
		ID[y]=0;
	}
	int ret=0;
	while(1) {
		int mal=0;
		FOR(y,N) {
			if(ID[y]>=Q[y].size()) goto out;
			mal=max(mal,LL[y][ID[y]]);
		}
		int up=1;
		while(up) {
			up=0;
			FOR(y,N) {
				while(ID[y]<Q[y].size() && RR[y][ID[y]]<mal) {
					ID[y]++;
					if(ID[y]>=Q[y].size()) goto out;
					up=1;
					mal=max(mal,LL[y][ID[y]]);
				}
				if(ID[y]>=Q[y].size()) break;
			}
			if(y<N) break;
		}
		
		
		ret++;
		FOR(y,N) ID[y]++;
	}
	out:
	_P("Case #%d: %d\n",_loop,ret);
}

まとめ

GCJは問題文が無駄に長い点はしんどいんだよなぁ。