TopCoder SRM 601, Division 1, Level 1 : WinterAndPresents

概要

　いくつかのバッグがあり、i 番のバッグの中には apple[ i ] 個のりんごと orange[ i ] 個の蜜柑が入っている。
　次のような手順で、クリスマスプレゼントを用意したい。

1. 正整数 X であって、どのバッグにも X 個以上の果物が入っているような X を一つ選ぶ
2. それぞれのバッグから X 個の果物を取り出す
3. 取り出した果物をまとめてプレゼントとする

　このとき、作ることができるプレゼントの種類を求めよ。なお、プレゼントが異なるとは、それぞれに含まれているりんごまたは蜜柑の数が異なることを言う。

解法

　まず、異なる X で作られたプレゼント同士は互いに背反なので独立に考えることができます。X の最大値は 2,000,000 なので、一つの X で何種類のプレゼントを作れるかをある程度高速に求められれば問題を解くことができます。
　では、X が決まったとき、何種類のプレゼントを作ることができるでしょうか？　まず、可能な限りりんごを多くするように作るとすると、このときの作り方は確定します。その状態から、いくつかのりんごを蜜柑に差し替えれば違うプレゼント作ることができます。このときの差し替え可能な個数が作ることができる（りんごを最大に取った場合とは）異なるプレゼントの数です。各バッグについて、りんごを最大数取る場合は a = min( X, apple[ i ] ) 個のりんごを取ることができます。残っている蜜柑の数は o = orange[ i ] - ( X - a ) です。この状態から差し替えることができるりんごの数は、min( a, o ) となります。各バッグについてこれを計算して総和をとれば、差し替え可能なりんごの数が求まります。この計算は O( N ) でできるので、時間的にも問題ありません。
　あとは、有効な X 全てについて作ることができる種類を計算して総和をとれば全体の答えが求まります。

コード

typedef long long LL;
typedef vector<int> VI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

const int INF = INT_MAX / 2;

class WinterAndPresents
{
public:
	long long getNumber( vector <int> apple, vector <int> orange )
	{
		const int N = apple.size();

		int maxX = INF;
		REP( i, 0, N )
		{
			maxX = min( maxX, apple[i] + orange[i] );
		}

		LL res = 0;
		REP( x, 1, maxX + 1 )
		{
			res += solve( apple, orange, x );
		}
		return res;
	}

	LL solve( const VI &apple, const VI &orange, const int x )
	{
		LL res = 1;
		REP( i, 0, apple.size() )
		{
			const LL a = min( apple[i], x );
			const LL rest = x - a;
			res += min<LL>( a, orange[i] - rest );
		}		
		return res;
	}
};