TopCoder SRM 691 Div1 Medium Moneymanager

TLE回避が難しい。
https://community.topcoder.com/stat?c=problem_statement&pm=14284

問題

偶数であるN個の課題があり、それぞれパラメータa[i],b[i]が設定されている。
これらの課題を順番を並べ替え１回ずつ処理したい。
そのさい、課題を処理すると自身の経験値がa[i]増える。また、合計経験値のb[i]倍だけお金をもらえる。
また、N個のうち半分を処理すると経験値がE増える。

最適な順番で課題を解く時、最大でもらえる金額を答えよ。

解法

隣接する２つの課題i,jがあるとき、間に経験値がE増加する中間地点を経由しないとすると、両者の経験値の差を求めるとどちらを先にすべきかわかる。
具体的には、a[j]*b[i]＜a[i]*b[j]なら、i番を先にすべきである。
まずはこの判断基準をもとに間に経験値E増加を含まない範囲で、課題を処理する最適な順を求めよう。

あとは各課題をE経験値が増える前後どちらに行うかを考える。
b[i]が同じならばa[i]が大きい順に処理するのが良い。
あとはb[i]ごとに、先頭何個を前半処理するかをDFS等で総当たりし、合計N/2個選ぶようにしよう。

あとは元のソート順のうちどれがE経験値を得る前に処理し、どれが得た後に処理されたかわかるので、全体の処理順も定まる。
後は題意の通り金額を計算しよう。

割とTLEが厳しいので、ちょこちょこ定数倍の高速化を頑張っておいた方が無難。

int N;
vector<pair<int,int>> VP;
vector<int> V[15];

bool cmp(pair<int,int> A, pair<int,int> B) {
	return B.first*A.second<A.first*B.second;
}

class Moneymanager {
	public:
	int X;
	ll getget(vector<int> x) {
		int i,j;
		ll mask=0;
		FOR(i,11) FOR(j,x[i]) mask |= 1LL<<V[i][j];
		int tot=0;
		int se=0;
		FOR(i,N) if(mask & (1LL<<i)) se+=VP[i].first, tot+=se*VP[i].second;
		se+=X;
		FOR(i,N) if((mask & (1LL<<i))==0) se+=VP[i].first, tot+=se*VP[i].second;
		return tot;
	}
	
	ll dfs(int cur,int left1,int left2,vector<int>& x) {
		if(left1==0) return getget(x);
		if(left2==0) return 0;
		if(left1>left2) return 0;
		ll ma=0;
		if(x[cur]<V[cur].size()) {
			x[cur]++;
			ma=dfs(cur,left1-1,left2-1,x);
			x[cur]--;
		}
		return max(ma,dfs(cur+1,left1,left2-(V[cur].size()-x[cur]),x));
		
	}
	
	int getbest(vector <int> a, vector <int> b, int X) {
		N=a.size();
		this->X=X;
		int i;
		VP.clear();
		FOR(i,N) VP.push_back({a[i],b[i]});
		sort(VP.begin(),VP.end(),cmp);
		FOR(i,11) V[i].clear();
		FOR(i,N) V[VP[i].second].push_back(i);
		
		vector<int> x(11,0);
		return dfs(1,N/2,N,x);
		
	}
}

まとめ

本番解けたと思ったけどTLEだった…。