TopCoder SRM 601 Div1 Easy WinterAndPresents [1人競技プログラミング Advent Calendar 2016 2日目]

この記事は1人競技プログラミング Advent Calendar 2016 2日目の記事です。

問題概要：
TopCoder Statistics - Problem Statement

apple配列とorange配列(length 1<=len<=50 apple.size() == orange.size())にi番目の鞄に入っているりんごの数とオレンジの数が与えられる。
全ての鞄からX個の果物を取り出した際に作れるりんごとオレンジの組み合わせの種類の総数を答えよ。

解いた方法：
Xが違う場合において、必ず同じ組み合わせが発生しないので各Xについて独立に考えてよい。
例えば鞄が1つでそれぞれ十分にりんごとオレンジを含んでおり、Xが1の時に作れる組み合わせはりんご1とオレンジ0かりんご0とオレンジ1だが、
Xが2の時には必ず果物を2つ使うのでXが1の時に作れる組み合わせを作ることは出来ない。
鞄が増えても同様に倍の数を使用することになる。

各Xにおいて、作る事の出来るりんごとオレンジの組み合わせを全探索すると間に合わない。
各鞄からX個取り出す際に
・最もりんごを少なくとった場合のりんごの数
・最もりんごを多くとった場合のりんごの数
・最もオレンジを少なくとった場合のオレンジの数
・最もオレンジを多くとった場合のオレンジの数
を求め、上記の合計を求めておく。

Xが決まっている場合において、使用する果物の合計数は決め打つ事が出来る。
りんごかオレンジの数を決めるともう片方の果物を使用できる数を一意に求めることが出来る。
上記から、Xが決まっている場合の作る事の出来るは
min( 最大りんご数 - 最小りんご数, 最大オレンジ数 - 最小オレンジ数) + 1
で求めることが出来る。

Xが取り得る値は1 <= X <= 2,000,000なので、O(nX) なら十分に間に合う速度となる。

#include<bits/stdc++.h>

#define MP make_pair
#define PB push_back
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<(n);i++)
#define REP1(i,n) for(int i=1;i<(n);i++)
#define REP2(i,d,n) for(int i=(d);i<(n);i++)
#define RREP(i,n) for(int i=(n);i>=0;i--)
#define CLR(a)      memset((a),0,sizeof(a))
#define MCLR(a)     memset((a),-1,sizeof(a))
#define RANGE(x,y,maxX,maxY) (0 <= (x) && 0 <= (y) && (x) < (maxX) && (y) < (maxY))

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<LL> VLL;
typedef pair<int,int> PII;

const int INF = 0x3f3f3f3f;
const LL INFL = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-9;

const int DX[]={1,0,-1,0},DY[]={0,-1,0,1};

class WinterAndPresents {
    public:
    vector<int> apple;
    vector<int> orange;
    LL getNumber(vector<int> _apple, vector<int> _orange) {
        apple = _apple, orange = _orange;

        LL ans = 0;
        int lp = INF;
        REP(i, apple.size()){
            if(apple[i] + orange[i] == 0) return 0;
            lp = min(lp, apple[i] + orange[i]);
        }

        REP1(i, lp+1){
            int min_apple = 0, max_apple = 0;
            int min_orange = 0, max_orange = 0;

            REP(j, apple.size()){
                int tmp;
                tmp = i - orange[j];
                if(tmp > 0) min_apple += tmp;
                max_apple += min(i, apple[j]);
                tmp = i - apple[j];
                if(tmp > 0) min_orange += tmp;
                max_orange += min(i, orange[j]);
            }

            ans += min(max_apple - min_apple + 1, max_orange - min_orange + 1);
        }

        return ans;
    }
};