結果

問題 No.43 野球の試合
コンテスト
ユーザー ゴリポン先生
提出日時 2025-03-31 19:48:26
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 58 ms / 5,000 ms
コード長 1,357 bytes
コンパイル時間 5,583 ms
コンパイル使用メモリ 166,796 KB
実行使用メモリ 7,324 KB
最終ジャッジ日時 2025-03-31 19:48:33
合計ジャッジ時間 6,342 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

module main;
// https://yamakasa3.hatenablog.com/entry/2018/06/20/014032 より
import std;

void main()
{
	// 入力
	auto N = readln.chomp.to!int;
	auto S = new char[][](N);
	foreach (ref line; S) {
		line = readln.chomp.dup;
	}
	// 答えの計算と出力
	auto n = S.join.count('-') / 2;	// まだ行われていない試合の数
	int rank = N;
	auto bit = new bool[](n);
	char[][] copy(char[][] s)
	{
		auto ret = new char[][](s.length);
		foreach (i, a; s)
			ret[i] = a.dup;
		return ret;
	}
	int solve()
	{
		auto a = copy(S);
		int cnt = 0;
		foreach (i; 0 .. N) {
			foreach (j; 0 .. i) {
				if (a[i][j] != '-') continue;
				if (!bit[cnt]) {
					a[i][j] = 'o';
					a[j][i] = 'x';
				} else {
					a[i][j] = 'x';
					a[j][i] = 'o';
				}
				cnt++;
			}
		}
		auto win = new int[](N);
		foreach (i; 0 .. N) {
			win[i] = a[i].count('o').to!int;
		}
		win.sort;
		int cnt2 = 1;
		auto list = [win[N - 1]];
		foreach_reverse (i; 1 .. N)
			if (win[i] > win[i - 1])
				list ~= win[i - 1];
		int cnt3 = a[0][1 .. $].count('o').to!int;
		foreach (i; list) {
			if (cnt3 >= i)
				return cnt2;
			else
				cnt2++;
		}
		return list.length.to!int;
	}
	void rec(int k)
	{
		if (k == n) {
			int t = solve();
			if (rank > t)
				rank = t;
			return;
		}
		rec(k + 1);
		bit[k] = true;
		rec(k + 1);
		bit[k] = false;
	}
	rec(0);
	writeln(rank);
}
0