TopCoder SRM 601 Div1 Easy WinterAndPresents

問題

n個のかばんがあって、i番目のかばんにはりんごがapple[i]個とみかんがorange[i]個入っている。
ここから次のようにしてりんごとみかんを取り出す。取り出し方は何通りあるか。

自然数Xを選ぶ。
それぞれのかばんから、りんごとみかんの合計がX個になるようにりんごとみかんを取り出す。
これを全てのかばんについて行い、りんごとみかんの個数のそれぞれの合計をa, bとする。

a, bの組が異なるとき、二つの取り出し方は異なると数える。

制約条件

n≦50
apple[i], orange[i]≦100万

方針

Xを固定。
すると、りんごとみかんの合計はnX個と決まる。
このうちいくつをりんごにできるか考える。

i番目の袋でりんごがa個とb個（a < b）に出来るとすると、
その袋ではa≦j≦bなるjなら、どのjでもりんごをj個にすることができる。

なので、それぞれの袋についてりんごの数の上限と下限を求め、
それを全て足してやれば全体のりんごの数の上限と下限が求まり、
間の数も全て作れることがわかる。

これを全てのXについて試せばいい。

ソースコード

class WinterAndPresents {
	public:
	long long getNumber(vector <int> apple, vector <int> orange) {
		
		int n = apple.size();
		ll ans = 0;
		
		for(int x = 1; x <= 2000000; x++){
			int lo = 0, hi = 0;
			
			rep(i, n){
				if(apple[i] + orange[i] < x) goto FAIL;
				hi += min(apple[i], x);
				lo += max(0, x - orange[i]);
			}
			ans += hi - lo + 1;
			FAIL:;
		}
		return ans;
	}
};