結果

問題 No.43 野球の試合
ユーザー data9824data9824
提出日時 2015-05-19 00:28:23
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 10 ms / 5,000 ms
コード長 1,074 bytes
コンパイル時間 563 ms
コンパイル使用メモリ 76,976 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-20 10:00:20
合計ジャッジ時間 1,310 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 7 ms
4,376 KB
testcase_07 AC 10 ms
4,380 KB
testcase_08 AC 6 ms
4,376 KB
testcase_09 AC 9 ms
4,380 KB
testcase_10 AC 5 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <functional>
#include <limits>
#include <cstdlib>

using namespace std;

int main() {
	int n;
	cin >> n;
	vector<string> s(n), t(n);
	for (int i = 0; i < n; ++i) {
		cin >> s[i];
		t[i] = s[i];
	}
	int games = n * (n - 1) / 2;
	int patterns = 1 << games;
	int minOrder = numeric_limits<int>::max();
	for (int bits = 0x0; bits < patterns; ++bits) {
		int mask = 0x1;
		for (int y = 1; y < n; ++y) {
			for (int x = 0; x < y; ++x) {
				if (s[x][y] == '-') {
					bool win = (bits & mask);
					t[x][y] = win ? 'o' : 'x';
					t[y][x] = win ? 'x' : 'o';
				}
				mask <<= 1;
			}
		}
		set<int, greater<int> > scores;
		for (int i = 1; i < n; ++i) {
			scores.insert(count(t[i].begin(), t[i].end(), 'o'));
		}
		int score0 = count(t[0].begin(), t[0].end(), 'o');
		int order = 1;
		for (set<int>::const_iterator it = scores.begin();
			it != scores.end() && score0 < *it;
			++it, ++order) {
		}
		minOrder = min(minOrder, order);
	}
	cout << minOrder << endl;
	return 0;
}
0