WARush

SRMの結果とか、解けた問題のコードを書いていきます

SRM573 Div2 Medium "TeamContestEasy"

3 * N人の生徒(0,1,2...3N-1)がプロコンに臨もうとしていて、
彼らのコーディング力が分かっている。

あなたのチームは生徒0,1,2であるが、
他のチームはどのメンバーが組んでいるのかまだ分かっていない。
チームとしての強さは、3人のコーディング力がX,Y,Zだとすると、
X + Y + Z - min(X, Y, Z)となる。

あなたは自分のチームのランクが最低でもどれぐらいなのかを知りたい。
ランクは、自分たちより強いチーム力を持つチームの数+1となる。

他のチームの組み合わせを想定して、最低のランクを返せ。

制約

3 <= 生徒の数 <= 48
1 <= 生徒のコーディング力 <= 10^6

考えた事

他のチームの1番強いやつをまず決める。
2番目は自チームを超えるような強さを持つやつらの中で
最低の強さを持つものを選び、ペアを組ませる。
これを繰り返す。

今思ったが、1番目と2番目で挟み込んでいくという間違えやすい実装するよりも、
選んだフラグ持って、一通りループさせて2番目を決めるような実装のほうがよかったな。

ソースコード
class TeamContestEasy {
public:
    int worstRank(vector <int> s){
        int my = s[0] + s[1] + s[2];
        my -= min( s[0], min( s[1], s[2] ) );

        sort( s.begin() + 3, s.end(), greater<int>() );
        int n = s.size();
        int m = n - 1 - (n - 3) / 3;
        int res = 0;
        for( int t = 3; t < m; t++ ){
            while( t < m && s[t] + s[m] <= my ){
                m--;
            }
            if( t < m ) res++;
            m--;
        }

        return res + 1;
    }
};