TopCoder SRM 844 : Div1 Medium Presents2023

これ本番に自信をもってsubmitするの怖いな…。
https://community.topcoder.com/stat?c=problem_statement&pm=17946

問題

面積Pの紙がある。
これを使って、できるだけ多くの体積の直方体をラッピングしたい。

この手順は、以下のように行う。
ラッピング候補の直方体のサイズを、A≦B≦Cとなる正整数A,B,Cで表す。
この時、以下の直方体を選ぶ。

• あり得る中で、体積(A*B*C)が最大。
• 体積が等しい組み合わせが複数あれば、タプルとして最小のものを選ぶ。

紙が残っている限り、複数個の直方体をラッピングしてもよい。
ラッピングする直方体の体積の総和の最大値を求めよ。

解法

A,B,Cを総当たりして体積が最大なものを求めるのが基本方針。
後は以下のように枝刈りする。

• 体積の最大化を考えると、立方体に近い組み合わせが良い。面積の条件から、3辺は√(P/6)程度であるのが良い。そこでAは√(P/6)から±10000あたりだけ探す。
• A,Bを決めると、面積の条件からCの上限が決まるので、Cは総当たりしなくてよい。

class Presents2023 {
	public:
	long long pack(long long paperArea) {
		ll P=paperArea/2;
		ll V=0;
		while(P>=3) {
			ll ma=0,mv=0;
			ll B=sqrt(P/3);
			for(ll a=max(B-10000,1LL);a<=B+10000;a++) {
				for(ll b=a;a*b+b*b+b*a<=P;b++) {
					ll c=(P-a*b)/(a+b);
					ll na=a*b+b*c+c*a;
					if(a*b*c>mv) {
						mv=a*b*c;
						ma=na;
					}
				}
			}
			V+=mv;
			P-=ma;
		}
		
		return V;
	}
}

まとめ

シンプルな問題設定ながら罠が多くてしんどい。