Google Code Jam 2020 Round 1C : Oversized Pancake Choppers

方針は単純だけど、実装はちょっと手間取る。
https://codingcompetitions.withgoogle.com/codejam/round/000000000019fef4/00000000003172d1

問題

N要素の整数列Aが与えられる。
A中の要素を2つに分解する(合計が元の要素と一致する2つの非負実数値に分ける)、という処理を何度か行い、同じ値がD個以上あるようにしたい。
分解処理を何度行えばよいか。

解法

Dが小さいことに着目する。
1つの要素を(D-1)回処理してD分割すれば条件を満たすので、最悪でも(D-1)回が解になる。

c回均等分割して等しい要素がc個とあと違う大きさの要素が残るよりは、残った1つも同じ大きさになって(c+1)個の要素に分かれると、分割回数が減ってお得である。
そうすると、D個生成する値の候補はA[i]/c (cは1～D)の形しかありえない。
そこで、A[i]/cの値を総当たりしよう。

なお、事前に二分探索で(分割回数はともかく)D個同じ値を切り出せる最大の値mを求めておこう。
A[i]/c＞mとなような値は対象外とする。

ここで着目すべきは、A[i]/cの整数倍(それも高々D倍)の値だけである。
残りは分割した残りからA[i]/cが得られて、分割回数を節約できておいしい、ということがない。
そこでそれらだけ小さい順に見ていけばよい。

なお、この問題はA[i]が大きいので、下手に小数を使うと誤差の問題で誤りやすい。
事前にc倍した値を使うなど、有理数や整数を使おう。
以下の解答はO(N*D^2)かかるので、定数倍の高速化が必要。

int N,D;
ll A[10101];

unordered_map<ll,int> M[51];
vector<pair<ll,ll>> V;

bool comp(pair<ll,ll> A,pair<ll,ll> B) {
	// A.first/A.second<=B.first/B.second
	return A.first*B.second<B.first*A.second;
	
}

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	FOR(i,51) M[i].clear();
	V.clear();
	
	
	cin>>N>>D;
	FOR(i,N) {
		cin>>A[i];
		for(j=1;j<=50;j++) {
			M[j][A[i]*j]++;
			V.push_back({A[i],j});
		}
	}
	sort(A,A+N);
	sort(ALL(V),comp);
	
	int mi=D-1;
	x=0;
	for(i=20;i>=0;i--) if(x+(1<<i)<V.size()) {
		ll a=V[x+(1<<i)].first;
		ll b=V[x+(1<<i)].second;
		ll num=0;
		FOR(j,N) num+=A[j]*b/a;
		if(num>=D) x+=1<<i;
	}
	
	y=x;
	FOR(i,y+1) if(i==0 || V[i].first*V[i-1].second!=V[i-1].first*V[i].second) {
		ll a=V[i].first;
		int j=V[i].second;
		int cut=0;
		int lef=D;
		for(x=1;x<=lef;x++) if(M[j].count(a*x)) {
			int num=M[j][a*x];
			if(lef<=num*x) {
				cut+=lef/x*(x-1)+lef%x;
				lef=0;
			}
			else {
				lef-=num*x;
				cut+=num*(x-1);
			}
		}
		mi=min(mi,cut+lef);
	}
	
	_P("Case #%d: %d\n",_loop,mi);
}

まとめ

毎度いい問題作るよね。