SRM453 Div1 Easy(250) TheBasketballDivOne

チーム数 n≦5 なので試合結果 3^n(n-1)/2 は最大59049通り。全パターン試す。

#include <iostream>
#include <set>
#include <vector>

using namespace std;

class TheBasketballDivOne
{
public:
    int find( int n, int m );
};

int TheBasketballDivOne::find( int n, int m )
{
    int lim = 1;
    for ( int i=0; i<n*(n-1)/2; i++ )
        lim *= 3;

    set<vector<int> > log;

    for ( int i=0; i<lim; i++ )
    {
        vector<vector<int> > table( n, vector<int>( n, 0 ) );

        int t = i;

        for ( int j=0; j<n; j++ )
        for ( int k=j+1; k<n; k++ )
        {
            table[j][k] = t%3;
            table[k][j] = 2 - t%3;
            t /= 3;
        }

        vector<int> W( n );
        for ( int j=0; j<n; j++ )
            for ( int k=0; k<n; k++ )
                W[j] += table[j][k];

        bool ok = W[0] == m;
        
        if ( ok )
        {
            for ( int j=0; j<n-1; j++ )
                if ( W[j] < W[j+1] )
                    ok = false;
        }

        if ( ok )
            log.insert( W );
    }

    return (int)log.size();
}

これだと時間オーバーしそうなので、

int main()
{
    TheBasketballDivOne t;

    for ( int n=0; n<=5; n++ )
    {
        for ( int m=0; m<=9; m++ )
            if ( n >= 2 && m >= 1 )
                cout << " " << t.find(n,m);
            else
                cout << " " << 0;

        cout << endl;
    }
}

と事前に計算して、答えを埋め込む。

class TheBasketballDivOne
{
public:
    int find( int n, int m );
};

int TheBasketballDivOne::find( int n, int m )
{
    int t[6][10] = {
        {  0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
        {  0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
        {  0, 1, 1, 0, 0, 0, 0, 0, 0, 0 },
        {  0, 0, 1, 2, 2, 0, 0, 0, 0, 0 },
        {  0, 0, 0, 1, 4, 6, 5, 0, 0, 0 },
        {  0, 0, 0, 0, 1, 6,16,20,16, 0 },
    };

    return t[n][m];
}

開始早々サーバーが落ちてたけど、レーティングは計算されるのだろうか。