yukicoder No.375 立方体のN等分 (1)

問題はこちら
No.375 立方体のN等分 (1) - yukicoder

1回切るとブロックの数は1以上増えるので、N-1回切ればN個以上になる。実際、同じ方向に切り続ければN-1回でN個にすることができるので、最大値はN-1。
最小値を考える。
縦・横・高さ方向に各a,b,c回切ったとすると、できるブロックは(a+1)*(b+1)*(c+1)個
よって求めるべきはmin{a+b+c|(a+1)(b+1)(c+1)=N}
変数を1つずらしてmin{a+b+c-3|abc=N}として考える。a,b,cはNの約数しかとれない。
a≦b≦cと仮定して良い。このときとなる。
あとは全探索すれば良い

int main(){
	long n,s,t;
	int i,j;
	scanf("%ld",&n);
	s=n;
	//自明な上界
	for(i=cbrt(n)+1;i>0;i--){
		if(n%i!=0)continue;
		for(j=sqrt(n/i)+1;j>0;j--){
			if(n/i%j!=0)continue;
			t=i+j+n/i/j-3;
			if(t<s)s=t;
		}
	}
	printf("%ld %ld",s,n-1);
	return 0;
}

ぎゅっと縮めて

long n,s,t,i=5e3;
main(j){
	scanf("%ld",&n);
	for(s=n;--i;)for(j=4e5;n%i<1&&--j;s=n/i%j|(t=i+j+n/i/j-3)>s?s:t);
	s=!printf("%ld %ld",s,n-1);
}

134B

ループ圧縮して

long n,s,t,i=5e3;
main(j){
	scanf("%ld",&n);
	for(s=n;s=n%i|!--j?j=4e5,--i?s:!printf("%ld %ld",s,n-1):n/i%j|(t=i+j+n/i/j-3)>s?s:t;);
}

128B
とするとRE。ぐぬぬ。仕方が無いのでprintfは外に出して

long n,s,t,i=5e3;
main(j){
	scanf("%ld",&n);
	for(s=n;n%i|!--j?j=4e5,--i:n/i%j|(t=i+j+n/i/j-3)>s?:(s=t););
	s=!printf("%ld %ld",s,n-1);
}

129B
とするとTLE。TLEナンデ！？
n%iを毎回計算してるせいかなあ……
元のコードの丁度2倍くらいの時間がかかってるから5.2sくらいでギリギリアウトになってるみたいだ。

16/07/18追記

long n,s,i=5e3;
main(j){
	scanf("%ld",&n);
	for(s=n;n%i|!--j?j=4e5,--i:n/i%j?:(s=fmin(s,i+j+n/i/j-3)););
	s=!printf("%ld %ld",s,n-1);
}

127B

4996msでぎりぎり通った。n/i/jの計算回数が減ったおかげ？