SRM 573 Div2 Medium TeamContestEasy

問題

SRM 573 - TopCoder Wiki

プログラミングコンテストが開催され,各参加者の強さはstrengthで表される. コンテストは3人一組となり,チームの強さは,上位2名のstrengthの和で表される. 今あなたがstrength[0], strength[1], strength[2]のチームにいる時. 自分のチームの上位となるチームの数の最大を答える問題.

解答

  • 最下位はスコアに反映されないので下位1/3は無視して良い.
  • できるだけ大きいスコアを作りたいので一人目をstrengthから大きい順に選択して,二人目を小さい方から順に選択して自分のチームのスコアを超えるように選択する.
  • このようにグリーディーに選択していけば自分のチームのスコアを超える,最大のチーム数を求めることが出来る.

公式のソースコードわかりやすかった.

using namespace std;

class TeamContestEasy
{
public:
  int worstRank(vector <int> strength)
    {
      int i, j;
      int mystrength = strength[0] + strength[1] + strength[2] - min(strength[0], min(strength[1], strength[2]));
      strength.erase(strength.begin());
      strength.erase(strength.begin());
      strength.erase(strength.begin());
      int n = strength.size();
      int res = 1;
      vector<bool> used = vector<bool>(n, false);
      sort(strength.rbegin(), strength.rend());
      for(i = 0; i < n; i++) {
        if (used[i]) continue;
        for (j = n-n/3; j > i; j--) {
        if (used[j]) continue;
          if ((strength[i] + strength[j]) > mystrength) {
            res++;
            used[j] = true;
            used[i] = true;
            break;
          }
        }
      }
      return res;
    }
};