台北市104 學年度資訊學科能力競賽 pC. Underdog ( 田忌賽馬 )

暴力判斷就可以了。
顯然把最強的K + 1個依序跟對手最弱的K + 1個比，一定最優。

#include <bits/stdc++.h>
using namespace std;

typedef vector< int > vi;
typedef vector< vi > vvi;
typedef pair< int, int > pii;
typedef vector< pii > vp;

int K, N;
vi S; // team id to rank
vi rS; // rank to team id
vvi P, U, L;

void init(){
    cin >> K >> N;
    S = rS = vi( N );
    P = U = L = vvi( N, vi( 2 * K + 1 ) );
    for( int i = 0; i < N; ++i ){
        cin >> S[ i ],
        --S[ i ],
        rS[ S[ i ] ] = i;
        for( int j = 0; j < 2 * K + 1; ++j )
            cin >> P[ i ][ j ];
        for( int j = 0; j < 2 * K + 1; ++j )
            cin >> U[ i ][ j ];
        for( int j = 0; j < 2 * K + 1; ++j )
            cin >> L[ i ][ j ];
    }
}

int win( vi a, vi b, int rank_a, int rank_b ){
    for( int i = 0; i < a.size() / 2; ++i )
        a.insert( a.begin(), a.back() ),
        a.pop_back();
    int win_cnt = 0;
    for( int i = 0; i < a.size(); ++i )
        if( a[ i ] > b[ i ] or ( a[ i ] == b[ i ] and rank_a < rank_b ) )
            ++win_cnt;
    return win_cnt >= K + 1;
}

void solve(){
    for( int i = N - 1; i >= 0; --i ){
        int win_all = 1;
        for( int j = 0; j < N; ++j )
            if( rS[ i ] != j )
                if( not win( P[ rS[ i ] ], P[ j ], i, S[ j ] ) ){
                    win_all = 0;
                    break;
                }
        if( win_all ){
            cout << rS[ i ] + 1 << " ";
            break;
        }
    }
    for( int i = N - 1; i >= 0; --i ){
        int win_all = 1;
        for( int j = 0; j < N; ++j )
            if( rS[ i ] != j )
                if( not win( U[ rS[ i ] ], L[ j ], i, S[ j ] ) ){
                    win_all = 0;
                    break;
                }
        if( win_all ){
            cout << rS[ i ] + 1 << endl;
            break;
        }
    }
}

signed main(){
    ios::sync_with_stdio( false );
    init();
    solve();
    return 0;
}