結果

問題 No.43 野球の試合
コンテスト
ユーザー nenuon
提出日時 2017-06-25 13:01:49
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 6 ms / 5,000 ms
コード長 1,275 bytes
コンパイル時間 1,028 ms
コンパイル使用メモリ 99,040 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-04 08:30:20
合計ジャッジ時間 1,441 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
typedef long long ll;
// 全探索
typedef pair<int, int> P;

int main(){
  int N;
  cin >> N;
  vector<string> vs;
  FOR(i,0,N){
    string s;
    cin >> s;
    vs.push_back(s);
  }
  vector<P> vp;
  int win[N];
  FOR(i,0,N) {
    win[i] = 0;
  }
  FOR(i,0,N){
    FOR(j,i,N){
      if(vs[i][j] == 'o') {
        win[i]++;
      }
      if(vs[i][j] == 'x') {
        win[j]++;
      }
      if(vs[i][j] == '-'){
        vp.push_back(P(i,j));
      }
    }
  }

  int ans = 10;
  int len = vp.size();
  FOR(i,0,1<<len){
    int winwin[N];
    FOR(j,0,N) {
      winwin[j] = win[j];
    }
    FOR(j,0,len){
      if((i>>j) & 1){
        winwin[vp[j].first]++;
      } else {
        winwin[vp[j].second]++;
      }
    }
    int tmp = 1;
    int now = winwin[0];
    sort(winwin, winwin + N);
    FOR(i,0,N){
      if(now<winwin[i]){
        tmp++;
        now = winwin[i];
      }
    }
    ans = min(ans, tmp);
  }
  cout << ans << endl;
  return 0;
}
0