Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2011-05-29SRM507 Div1

SRM507 Div1 500 CubePacking

| 14:02 | SRM507 Div1 500 CubePacking - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM507 Div1 500 CubePacking - SRM diary(Sigmar) SRM507 Div1 500 CubePacking - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

むずい・・・math的な雰囲気もするが、たぶん探索系だな

Lが最大10と小さいのを利用するのか?うーん・・・分からん・・・

底面のサイズとかで探索するんだろうか・・・でも探索の範囲が分からない・・・

探索の範囲についてはサンプル1はすごくいいヒントで、解が素数×素数×素数になる可能性があるのが分かる

つまり、解の最大は2,000,000,000くらいだが、そうすると1~20億くらいまでの素数を探索しなきゃならない

その組み合わせを底面サイズとして用いるとなると、さすがに計算量が明らかにオーバーする

うーん・・・探索の範囲を限定しようとすると、素因数分解みたいな話か・・?


あ、もう残り45分か

900が簡単だったらまた残念なことになるから、ここらで問題を読んでおこう

900はDPぽいが、ストレートにやると、計算量が2億超えるので難しいな・・

提出者も全然いない・・これはきっと難しいんだ

15分くらい費やしてまた500に戻る


さて、素因数分解とかって、答えが分かってたら計算できるけど、答えの範囲ってどうなるんだ?

そうか・・ここでLの最大10が生きてくるんだ

底面L*Lの長方形にすると、解が最大でもL*L*L*Nb+Ns+L*Lになるじゃないか

最小はL*L*L*Nb+Nsだから、たかだかL*L(=100)の範囲に解が必ずある!

ということで、解の値をイテレートして、解となりうるかどうかを調べれば良いのでは

解になるかどうかは、素因数分解まではする必要はないな。適当に約数を求めて、、サイズLの箱が全部収まるか調べればOK

書いた

サンプル合った

大きい入力で試す→だいたい300msくらい。問題ないかな・・・

提出


チャレンジフェーズ

サンプル弱いから、色々適当に書いて出しちゃってる人がいるに違いない

この人怪しい→突撃→失敗 読み間違えた・・

どんどん他の人が落ちていく・・ターゲットの人が落としまくっている。やばい

今度は明らかに間違ってる人発見→落とせる入力作成中に落とされる

だめだ・・・チャレンジ強い人がいるとやられたい放題だな・・


ソースコード

提出時はres変数を使用しておらず、ok関数がtrueのときreturn sumしている

以下は最悪時間の検証用に、途中で終了しないようにしたバージョン(これで300msくらい)

書きながら思ったけど、解の範囲が100とか分かっているのなら、適当に底面サイズの探索をするだけでも解けそうだな・・

class CubePacking {
public:
	bool ok(int Nb, int L, int a, int b, int c) {
		int aa=a/L, bb=b/L, cc=c/L;
		if(aa*bb*cc<Nb) return false;
		return true;
	}

	int getMinimumVolume(int Ns, int Nb, int L) {
		int res=2000400000;
		int sum=L*L*L*Nb+Ns;

		for(int t=0; t<100; t++) {
			for(ll i=1; i*i*i<=sum; i++) {
				if(sum%i>0) continue;
				int sum2=sum/i;
				for(ll j=i; j*j<=sum2; j++) {
					if(sum2%j>0) continue;
					if(ok(Nb, L, i, j, sum2/j)) res=min(res, sum);
				}
			}
			sum++;
		}

		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20110529