SRM453 Div2 Hard(1000) TheSoccerDivTwo

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