SRM552 Div1

問題が面白い回でした。

Easy(Failed System Test/250)
解法自体は難しくないのですが、誤差やオーバーフローに注意しないと間違えます。

すべての色で必要な球の個数がN*(N+1)/6個(ただし、小数点以下切り捨て)であると考えて、作れるだけ作ったあと、不足している分を調整して、答えから引いていく解法で解きました。

他に二分探索で答えを求める解法もあります。

typedef long long ll;

class FoxPaintingBalls{
public:
	ll theMax(ll R, ll G, ll B, int N) {
		if(N==1)return R+G+B;
		ll a = (ll)N*(N+1)/6;
		ll ans = min(min(R,G),B)/a;
		if(N%3!=1){
			return ans;
		}
		R-=ans*a;
		G-=ans*a;
		B-=ans*a;
		ll rest=ans;
		rest-=R+G+B;
		if(rest>0){
			//ans-=ceil((double)rest/(3.0*a+1.0));にすると、doubleの精度の問題でWAする。
			ans-=rest/(a*3+1);
			if(rest%(a*3+1))ans--;
		}
		return ans;
 	}
};

Medium(-/500)
正方形を2つ作って、最大値を求める。
O(n^4)でやろうとして、解法が思いつかなくて解けませんでしたが、n<=30なので、O(n^5)やO(n^6)とかでも解けたみたいです。
(0,0)から(x,y)までの和を求めておくと、(a,b)から(c,d)までの和をO(1)で求められるようになって、そこからどうにかして解くのだと思いますが、難しかったです。

Score 50
Rating 1241 -> 1347