kmjp's blog

競技プログラミング参加記です

Google Code Jam 2021 Round 1A : B. Prime Time

初手ミスってタイムロス。
https://codingcompetitions.withgoogle.com/codejam/round/000000000043585d/00000000007543d8

問題

500未満の素数の多重集合が与えられる。
要素数は10^15以下である。
これらの多重集合を2つに分け、片方の和と、もう片方の積を一致させることができるとき、その最大値を求めよ。

解法

要素数が小さい場合はDFSで積の方に割り当てる要素を選んでいっても間に合う。
最大ケースではこれでは間に合わない。

元の多重集合の和をSとする。
いくつかの要素を積を取る集合に持って行ったとして、その積は10^18以上にはならないはず。
とすると、前者の集合から取り除く要素の和は、499^7>10^18なので3500もいかないはずである。
そこで、[S-3500,S]の範囲を全探索し、多重集合内の部分集合に素因数分解できるか試してみるとよい。

int M;
int P[555];
ll N[555];

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>M;
	ll S=0;
	FOR(i,M) {
		cin>>P[i]>>N[i];
		S+=P[i]*N[i];
	}
	ll ret=0;
	
	for(ll a=S;a>=max(1LL,S-500*8);a--) {
		ll sum=S;
		ll X=a;
		FOR(i,M) {
			ll num=N[i];
			while(num&&X%P[i]==0) num--, sum-=P[i], X/=P[i];
		}
		if(X==1&&a==sum) {
			ret=a;
			break;
		}
	}
	
	_P("Case #%d: %lld\n",_loop,ret);
}

まとめ

最初DFSやってしまったが、一応手元で最大ケース試して考え直した。
SmallとLargeでおそらく?良い感じに想定解法が異なるGCJ向けの問題。