SRM 573 Div1 Easy TeamContest

問題

3*Nの要素を持つ配列strengthが与えられる。この要素を3つずつN個のグループに分ける。最初の3つの要素をまとめたものがあなたの所属するグループである。グループの強さはグループのstrengthがx,y,zだとすると max(x,y,z) + min(x,y,z) で決まる。残りの3*N-3をうまくN-1のグループに分けた時、あなたのグループは強さ順で最悪の場合何位になることがあるか。あるグループがあなたのグループより強いとは、そのチームの強さがあなたのチームの強さより大きい時であるとする。

やりかた

貪欲。
残り3*N-3の要素はまずソートしておく。グループは以下を繰り返して分けていく。
最大要素：ソートしたなかで一番大きい要素（ソース中のiのループ）
最小要素：ソートしたなかで上の最大要素と足しあわせてあなたのチームより強くなる条件を満たすもののうち最小の要素（ソース中のkのループ）
真ん中の要素：最小要素の次の要素（ソース中のjのループ）

こうするとこのグループはあなたのグループよりスレスレで強くなる。ここで選んだ3つは取り除いておく。これが何回繰り返せるか調べればいい。

以下ソース。O(N^4)程度で余裕。

class TeamContest {
public:
  int worstRank(vector <int> strength) {
    int result = 0;
    int my = max(strength[0], max(strength[1], strength[2])) +
      min(strength[0], min(strength[1], strength[2]));//あなたのチームの強さ
    sort(strength.begin() + 3, strength.end());

    bool change = true;
    int N = strength.size();
    while(change){
      N = strength.size();
      change = false;
      for(int i = N - 1; i >= 3; i--){//最大要素
	for(int k = 3; k < i; k++){//最小要素
	  for(int j = k + 1; j < i; j++){//真ん中の要素
	    if(my < strength[i] + strength[k]){
	      result++;
	      strength.erase(strength.begin() + i);
	      strength.erase(strength.begin() + j);
	      strength.erase(strength.begin() + k);
	      change = true;
	      goto L1;
	    }
	  }
	}
      }
    L1:;
    }
    return result + 1;
  }
};

普通に考えるとjのループ必要ないね。。。