Beta Round #66-A: The Elder Trolls IV: Oblivon

keyword

数学　C++

問題概要

3辺がX,Y,Z(<10^6)の豆腐にK回まで整数座標のところで包丁を入れられる。最大でいくつのブロックができるか求める問題。

解法

和が一定のときに積を最大にする問題。当然、バランスが取れているほど大きくなる。一辺をいくつに切るかで全探索して、残りは半分に近い大きさで切る、という方法で通った。
もっと賢い(分かりやすい)方法もある。X,Y,Z軸でいくつにわけるかをx,y,zと置いて1で初期化し、Kが残っていて、かつ上限を越えない限り順番にincしていく。

#include <iostream>
using namespace std;

typedef long long int64;
int64 X,Y,Z,K;

int64 solve(){
	int64 ans = 1;
	for(int64 a=1; a<=X && (a-1)<=K; a++){
		int64 tmp = a;
		int64 res = K-a+1;
		if((Y-1) + (Z-1) <= res){
			ans = max(ans, tmp * Y * Z);
		}
		if((Y-1) <= (res+1)/2){
			ans = max(ans, tmp * Y * min(Z, res - (Y - 1)));
		}
		if((Z-1) <= (res+1)/2){
			ans = max(ans, tmp * Z * min(Y, res - (Z - 1)));
		}
		ans = max(ans, tmp * min(Y,res/2+1) * min(Z,res - res/2 + 1));
		ans = max(ans, tmp);
	}
	return ans;
}

int main(){
	cin >> X >> Y >> Z >> K;
	int64 ans = 0;
	ans = max(ans, solve());
	swap(X,Y);
	ans = max(ans, solve());
	swap(Y,Z);
	ans = max(ans, solve());
	swap(Z,X);
	ans = max(ans,solve());
	swap(X,Y);
	ans = max(ans, solve());
	swap(Y,Z);
	ans = max(ans, solve());
	cout << ans << endl;
	return 0;
}