読者です 読者をやめる 読者になる 読者になる

srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

yukicoder No.43 野球の試合

yukicoder 全探索

問題

問題概要

野球の試合の対戦成績の表がもらえる. 表は埋まっていない部分があるので, そこを任意に決めた場合, 自チームは最高で何位になるか. また、同じ順位に複数のチームがあったとしても, 数字が抜けることはない.

解法

nが最大6でありとても小さい. 仮に対戦成績の表がすべて埋まっていない場合, 決まっていない箇所が30箇所であり, 半分は逆のことを示しているだけなので, 実質わからないのは最大でも15箇所ということになる. わからない場所すべてにおいて(例えばsij), i番目のチームが勝つか負けるのかの2通りしかないので, 全探索しても, 215ですむ. よって、2bit全探索を実装すればよいことになる.
実装方法はmaskを0から(1<<(わからない場所の数))-1 の間を回して, 位置pのbitが立っていれば, どちらかのチームが勝利したことにして、立っていなければもう一方のチームが勝利したことにして, 全試合の勝利数を数えればよい. それを2わからない場所の数だけ試して順位が最小のものを求めればよいことになる.

ミス

nが極端に小さいのが肝.

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;

string s[10];
int n;
int kati[10], make[10];

int main(void){
    cin >> n;
    rep(i, n) cin >> s[i];
    vector<pair<int, int> > nazo;
    rep(i, n)rep(j, n){
        if(s[i][j] == '-'){
            nazo.pb(mp(min(i, j), max(i, j)));
        }else if(s[i][j] == 'o'){
            kati[i]++;
        }
    }
    sort(all(nazo));
    nazo.erase(unique(all(nazo)), nazo.end());
    int size = nazo.size();
    int ans = INF;
    if(size != 0){
        for (int mask = 0; mask < (1 << (size)); ++mask){
            vector<int> win(10, 0);
            rep(i, n)win[i] = kati[i];
            for (int p = 0; p < size; ++p){
                if((mask & (1 << p)) != 0){//1が立ってたら、firstの勝ち 立ってなければsecondの負け
                    win[nazo[p].fi]++;
                }else{
                    win[nazo[p].se]++;
                }
            }
            int aim = win[0];
            sort(all(win));
            win.erase(unique(all(win)), win.end());
            reverse(all(win));
            int cnt = 0;
            while(win[cnt] != aim)cnt++;
            chmin(ans, cnt + 1);
        }
    }else{//すでに決まっている場合
        vector<int> win;
        rep(i, n) win.pb(kati[i]);
        sort(all(win));
        win.erase(unique(all(win)), win.end());
        reverse(all(win));
        int cnt = 0;
        while(win[cnt] != kati[0])cnt++;
        chmin(ans, cnt + 1);
    }
    printf("%d\n", ans);
    return 0;
}