SRM453 Div1 Medium(500) TheTournamentDivOne

TheTournamentDivOne

勝ち点 w と引き分け点 d を合計が points になるように各チームに振り分けると考える。ただし、d は異なる２チームに同時に与えなければならない。各チームの引き分け数は、合計が偶数であり、引き分け数最大のチームの引き分け数が他のチームの合計以下であればよい。この問題は次のように定式化できる。

　最小化：
　条件：
　　
　　
　　

ここで , はそれぞれチーム の勝ち数と引き分け数である。また目的関数は のときは の最小化、 のときは の最大化となる。

w<2d（w>2d）の場合、各チームに x と y を x が最小（最大）となるように設定する。割り当てることができなければ有効な点数ではない。条件を満たすまで w を増やして（減らして）いく。この際、３番目の条件が満たされるようにするため、y が最大（最小）のチームを選択する。

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

class TheTournamentDivOne
{
    bool    update( int *x, int *y, int point, int w, int d, int f );
    bool    check( vector<int> y );
public:
    int     find( vector<int> points, int w, int d );
};

int TheTournamentDivOne::find( vector<int> points, int w, int d )
{
    int n = (int)points.size();

    vector<int> x( n );         //  number of wins
    vector<int> y( n );         //  number of draws
    vector<bool> c( n, true );  //  x[i] can be increased/decreased

    int f = w<2*d ? 1 : -1; //  1:minimize x  -1:maximize x

    //  initialize
    for ( int i=0; i<n; i++ )
    {
        x[i] = f>0 ? -1 : points[i]/w+1;

        if ( ! update( &x[i], &y[i], points[i], w, d, f ) )
            goto fail;
    }

    //  increase/decrease x to satisfy the conditions
    while ( ! check( y ) )
    {
        int t = -1;
        for ( int i=0; i<n; i++ )
        if ( c[i] )
        {
            if ( t == -1  ||
                 f > 0  &&  y[i] > y[t]  ||
                 f < 0  &&  y[i] < y[t] )
                t = i;
        }
        if ( t == -1 )
            goto fail;

        if ( ! update( &x[t], &y[t], points[t], w, d, f ) )
            c[t] = false;
    }

    return accumulate( x.begin(), x.end(), 0 )
           + accumulate( y.begin(), y.end(), 0 ) / 2;

fail:
    return -1;
}

//  update x and y to satisfy that w*x+d*y = point
//  dir=1: x++  dir=-1: x--
bool TheTournamentDivOne::update( int *x, int *y,
                                  int point, int w, int d, int f )
{
    int tx = *x;

    while ( true )
    {
        tx += f;

        if ( w * tx < 0  ||  w * tx > point )
            return false;

        if ( ( point - w * tx ) % d == 0 )
        {
            *x = tx;
            *y = ( point - w * tx ) / d;
            return true;
        }
    }
}

//  check that
//  1) sum of y is even
//  2) y[i] <= Sum[t!=i] y[t]  for any i
bool TheTournamentDivOne::check( vector<int> y )
{
    int sum = accumulate( y.begin(), y.end(), 0 );

    if ( sum % 2 != 0 )
        return false;

    for ( int i=0; i<(int)y.size(); i++ )
        if ( 2 * y[i] > sum )
            return false;

    return true;
}

はてなに記法があるのはありがたいが、あまり美しくない……。