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; } };