SRM453 Div2 Hard(1000) TheSoccerDivTwo
チームをチーム0が順位で勝てないチーム、そのチームが負ければチーム0が勝てるチーム、そのチームが引き分ければチーム0が勝てるチーム、勝敗に関係無くチーム0が勝てるチームに分けて、g1, g2, g3, g4とする。なるべくg2が負けて、g3が引き分ける組み合わせを探す。g2はできる限りg1, g4, チーム0と対戦させる。残ったらg2同士で対戦。g3はなるべくg3同士で対戦。残ったらg1, g2, g4, チーム0の残ったチームと対戦。
#include <vector> using namespace std; class TheSoccerDivTwo { public: int find( vector<int> points ); }; int TheSoccerDivTwo::find( vector<int> points ) { int g1 = 0; // teams that team 0 can't beat int g2 = 0; // teams that team 0 can beat if the team loses int g3 = 0; // teams that team 0 can beat if the team draws int g4 = 0; // teams that team 0 can beat in any case for ( int i=1; i<(int)points.size(); i++ ) if ( false ); else if ( points[i]+0 > points[0]+3 ) g1++; else if ( points[i]+1 > points[0]+3 ) g2++; else if ( points[i]+3 > points[0]+3 ) g3++; else g4++; // remaining teams to beat/draw int r = g1 + g4 + 1; // match teams in g2 with teams in g1 and g4 if ( g2 < r ) r -= g2, g2 = 0; else g2 -= r, r = 0; // match teams in g2 with themselves r += g2 % 2; g2 -= g2 / 2; // match team in g3 with themselves g3 %= 2; // if other teams reamin // match team in g3 with them if ( r >= g3 ) g3 = 0; return 1 + g1 + g2 + g3; }