TopCoder SRM 601 Div1 Easy WinterAndPresents

SRM601に参加。Easyはそこそこの速度で解けたが、MediumはSample正解のコードはすぐかけたものの、計算量を落としきれず最大ケースでTLEするのが確定的なのでsubmit出来ず。
ChallengeではTLEすると思われたコードがTLEせず、25pt失った。
おかげで微妙な順位だったが、若干レートが上がったようだ。
http://community.topcoder.com/stat?c=problem_statement&pm=12860

問題

i番目の袋には、リンゴA[i]個とオレンジO[i]個が入ってるとする。
各袋から任意の正の整数K個ずつの果物を取ることができ、かつその時取れる合計のリンゴとオレンジの数の組み合わせ数を答えよ。

解法

まず、Kはの範囲の値を取ることができる。
後は各Kに応じてその時のリンゴの数の範囲を数えればよい。
リンゴの最大数Mはであり、最小数Lはである。
最大数は明らかで、リンゴがK個以上入っていればK個とり、K個未満ならあるだけ使えばよい。
最小数は、同様にできるだけオレンジを取るようにし、オレンジが不足する分だけリンゴを取った場合の数である。
取りうる組み合わせ数はM-L+1であり、これを各Kにおいて加算すればよい。

class WinterAndPresents {
	public:
	int N;
	long long getNumber(vector <int> apple, vector <int> orange) {
		int ma=1<<30,i,j;
		ll ret=0;
		N=apple.size();
		FOR(i,N) ma=min(ma,apple[i]+orange[i]);
		for(i=1;i<=ma;i++) {
			ll mio=0,mao=0;
			FOR(j,N) {
				mao+=min(orange[j],i);
				mio+=max(0,i-apple[j]);
			}
			ret += mao-mio+1;
		}
		return ret;
	}

};

まとめ

特にひっかけもないし素直な問題。