TopCoder SRM 573 Div1 Easy TeamContest、Div2 Medium TeamContestEasy

SRM573には参加。
Easyは正解したけど、Mediumは考え方は良かったもののツメが甘くてミス。
レートは微増なので良いけどね…。

ではDiv1 Easy・Div2 Mediumから。
http://community.topcoder.com/stat?c=problem_statement&pm=12470
http://community.topcoder.com/stat?c=problem_statement&pm=12471

問題

各人の能力が数値で表されている。３人組を作る場合、その組の能力は以下の様になる。

• Div1 Easy : ３人の能力値のうち最大値と最小値と和
• Div2 Medium : ３人の能力値のうち上位２人の能力値の和

ここで、3N人の能力値が与えられている。
最初の３人が既に組を組んでおり、残りの3(N-1)人の組は未定である。
このとき、最初の３人組の最悪の順位を求める。

解法

まず、最初の３人組の能力値は定義に則って計算すればよい。
あとは、この３人組の最悪の順位を探すため、この３人組の能力値を上回る組をできるだけ多く作る。

• Div1 Easy : まだ組を組んでない人のうち、最大値の人を選ぶ。次に、最小値の人から順に、和が最初の３人組の能力値を超える人を選ぶ。この２人の時点でこの組の能力値は確定しているので、あと１人は選んだ２人の間の能力値で、できるだけ能力値の低い組未作成の人を選んで３人組を作る。
• Div2 Medium : まだ組を組んでない人のうち、最大値の人を選ぶ。次に、最小値の人から順に、和が最初の３人組の能力値を超える人を選ぶ。この２人の時点でこの組の能力値は確定しているので、あと１人はできるだけ能力値の低い組未作成の人を選んで３人組を作る。（Div1 Easyと違い、３人目は２人目に選んだ人より能力値が高くても低くても良い）

Div 1 Easyはこんな感じ。

class TeamContest {
	int N;
	vector<int> S;
	public:
	int worstRank(vector <int> strength) {
		S.clear();
		N=strength.size();
		int i,ms;
		
		ms=max(max(strength[0],strength[2]),strength[1]) + min(min(strength[0],strength[2]),strength[1]);
		int rank=1;
		for(i=3;i<N;i++) S.push_back(strength[i]);
		sort(S.begin(),S.end());
		reverse(S.begin(),S.end());
		int vis[50];
		ZERO(vis);
		
		N-=3;
		int j,m;
		FOR(i,N-1) {
			if(vis[i]) continue;
			for(j=N-1;j>i;j--) {
				if(vis[j]) continue;
				if(S[i]+S[j]<=ms) continue;
				int k;
				for(k=j-1;k>i;k--) {
					if(vis[k]==0) {
						vis[i]=vis[j]=vis[k]=1;
						rank++;
						goto nex;
					}
				}
			}
			nex:
			;
		}
		return rank;
	}

};

次にDiv2 Medium。
先のDiv1 Easyに比べると最初の３人組の能力値計算方法と、３人目を選ぶ範囲が異なるだけ。

class TeamContestEasy {
	int N;
	vector<int> S;
	public:
	int worstRank(vector <int> strength) {
		S.clear();
		N=strength.size();
		int i,ms;
		
		ms=strength[0]+strength[1]+strength[2] - min(min(strength[0],strength[2]),strength[1]);
		int rank=1;
		for(i=3;i<N;i++) S.push_back(strength[i]);
		sort(S.begin(),S.end());
		reverse(S.begin(),S.end());
		int vis[50];
		ZERO(vis);
		
		N-=3;
		int j,m;
		FOR(i,N-1) {
			if(vis[i]) continue;
			for(j=N-1;j>i;j--) {
				if(vis[j]) continue;
				if(S[i]+S[j]<=ms) continue;
				vis[i]=vis[j]=1;
				int k;
				for(k=N-1;k>i;k--) {
					if(vis[k]==0) {
						vis[k]=1;
						rank++;
						goto nex;
					}
				}
			}
			nex:
			;
		}
		return rank;
	}
};

まとめ

Div1とDiv2でこういう微妙な内容の違いを付けるのは珍しいな。
大して難易度の変化にも貢献してないし。