SRM601 div1 Easy WinterAndPresents

メモ

n個の袋から取り出したappleとorangeを合わせた時、appleとorangeの個数が(a,b)になる(a+b=nX)。 それぞれの袋にappleとorangeがそれぞれX個以上あるならそれぞれの袋からX個取り出すときは、 合わせると(nX,0),(nX-1,1),...,(0,nX)となるのでnX+1通りになる。

問題はappleとorangeがそれぞれX個以上無い時。 ある一つの袋のappleがX-c個しかなく、またある袋のorangeがX-d個しかないとき、 (nX-c,0),(nX-c-1,1),...,(0,nX-d)となってc+d少なくなる。

つまり足りない分だけ組み合わせの数が少なくなる。 全てのXについて足りない分を全ての袋分引けばOK。

コード

class WinterAndPresents{
  public:
  long long getNumber(vector <int> apple, vector <int> orange) {
    ll ret = 0;
    int maxx = 1e9;
    int n = apple.size();
    FOR(i,0,n) {
      maxx = min(maxx, apple[i] + orange[i]);
    }
    FOR(x,1,maxx+1) {
      ret += n * x + 1;
      FOR(i,0,n) {
        ret -= max(0, x - apple[i]);
        ret -= max(0, x - orange[i]);
      }
    }
    return ret;
  }
};