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; } };