TopCoder SRM 846 : Div1 Easy Div2 Hard HockeyLeagueDraft

久々のSRM、レート増で終わってよかった。
https://community.topcoder.com/stat?c=problem_statement&pm=18015

問題

T個のチームとP人のプレイヤーがいる。
各プレイヤーは、攻撃力と守備力が与えられる。
また、各チーム攻撃力の総和と守備力の総和が与えられる。

各チームは、プレイヤーから1人選んでチームに加える。
その際、以下のように選ぶ。

• チームの強さは、攻撃力と守備力の二乗和である。
• プレイヤーをチームに加えるとき、攻撃力または守備力どちらかをチームの攻撃力・守備力に加算できる。
• 各チームは、チームの強さが最大になるよう、プレイヤーを選んでかつ攻撃力/守備力どちらを加算するか決める。

最後のチームが誰を選ぶか求めよ。

解法

まだ選ばれてない人のうち、攻撃力最大または守備力最大の人を選ぶことになるので、より強さが増えるほうを選ぼう。

class HockeyLeagueDraft {
	public:
	int draft(int P, int T, int seed, int MP, int MT) {
		ll state = seed;
		int i;
		vector<ll> A,D,TA,TD;
		set<pair<int,int>> SA,SD;
		FOR(i,P) {
			state = (state * 1103515245 + 12345)%(1LL<<31);
			A.push_back((state/10)%MP);
			state = (state * 1103515245 + 12345)%(1LL<<31);
			D.push_back((state/10)%MP);
			SA.insert({-A[i],i});
			SD.insert({-D[i],i});
		}
		
		int ret;
		FOR(i,T) {
			state = (state * 1103515245 + 12345)%(1LL<<31);
			TA.push_back((state/10)%MT);
			state = (state * 1103515245 + 12345)%(1LL<<31);
			TD.push_back((state/10)%MT);

			int x=SA.begin()->second;
			int y=SD.begin()->second;
			ll v=(TA[i]+A[x])*(TA[i]+A[x])+TD[i]*TD[i];
			ll w=(TD[i]+D[y])*(TD[i]+D[y])+TA[i]*TA[i];
			ret=min(x,y);
			if(v<w) ret=y;
			if(v>w) ret=x;
			SA.erase({-A[ret],ret});
			SD.erase({-D[ret],ret});
		}
		return ret;
	}
}

まとめ

雑にsetでやったけど普通に間に合った。