TopCoder SRM 605 Div1 Easy AlienAndHamburgers [1人競技プログラミング Advent Calendar 2016 7日目]

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

問題概要：
TopCoder Statistics - Problem Statement
i番目のハンバーガーの種類を表すtype配列とi番目の味のスコアを表すtaste配列が与えられる。 何個かのハンバーガーを食べて合計スコアを最大化したい。
スコアは 食べたハンバーガーの種類 * 食べたハンバーガーの味のスコアの合計で求められる。

解いた方法：
まず自明にtaste[i]が正の値の場合は重複している種類のハンバーガーでも必ず食べた方が最終スコアがお得になる。
負の値の場合は今までに食べたことがあるtypeのハンバーガーだと自明にスコアが下がるだけなので食べない。
また、食べたときに今までの合計スコアより結果が悪くなるなら食べない方がお得である。

taste[i]でソートしてtasteが大きい順番に食べていき食べたらスコアが下がるまで食べ続ければよい。

#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 AlienAndHamburgers {
    public:
    vector<int> type;
    vector<int> taste;
    int getNumber(vector<int> _type, vector<int> _taste) {
        type = _type, taste = _taste;
        vector<PII> hamburgers;
        REP(i, type.size()){
            hamburgers.PB(MP(taste[i], type[i]));
        }
        sort(ALL(hamburgers), greater<PII>());

        set<int> use_types;
        int all_taste = 0;
        REP(i, hamburgers.size()){
            if(hamburgers[i].first >= 0){
                all_taste += hamburgers[i].first;
                use_types.insert(hamburgers[i].second);
            }else if(use_types.count( hamburgers[i].second ) == 0){
                int now_score = use_types.size() * all_taste;
                if(now_score < (int)(use_types.size()+1) * (all_taste + hamburgers[i].first)){
                    all_taste += hamburgers[i].first;
                    use_types.insert(hamburgers[i].second);
                }
            }
        }
        return use_types.size() * all_taste;
    }
};