結果

問題 No.43 野球の試合
コンテスト
ユーザー 0w1
提出日時 2016-11-26 15:32:38
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 11 ms / 5,000 ms
コード長 1,135 bytes
コンパイル時間 2,119 ms
コンパイル使用メモリ 174,924 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-27 11:34:40
合計ジャッジ時間 2,751 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 7
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

signed main(){
  int N; cin >> N;
  vector< string > G( N );
  for( int i = 0; i < N; ++i )
    cin >> G[ i ];
  int match_cnt = 0;
  for( int i = 0; i < N; ++i )
    for( int j = i + 1; j < N; ++j )
      match_cnt += G[ i ][ j ] == '-';
  int best = N;
  for( int i = 0; i < 1 << match_cnt; ++i ){
    vector< string > t = G;
    for( int j = 0, c = 0; j < N; ++j )
      for( int k = j + 1; k < N; ++k )
        if( t[ j ][ k ] == '-' ){
          if( i >> c & 1 )
            t[ j ][ k ] = 'o',
            t[ k ][ j ] = 'x';
          else
            t[ k ][ j ] = 'o',
            t[ j ][ k ] = 'x';
          ++c;
        }
    vector< int > win( N );
    for( int j = 0; j < N; ++j )
      for( int k = 0; k < N; ++k )
        win[ j ] += t[ j ][ k ] == 'o';
    int zwin = win[ 0 ];
    sort( win.begin(), win.end(), greater< int >() );
    for( int j = 0, c = 0; j < N; ++j ){
      if( j - 1 >= 0 and win[ j ] != win[ j - 1 ] )
        ++c;
      if( win[ j ] == zwin ){
        best = min( best, c + 1 );
        break;
      }
    }
  }
  cout << best << endl;
  return 0;
}
0