結果
問題 |
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 |
ソースコード
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); }