初手ミスってタイムロス。
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向けの問題。