結果

問題 No.43 野球の試合
ユーザー work-furukawa
提出日時 2025-04-17 16:25:01
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 203 ms / 5,000 ms
コード長 1,275 bytes
コンパイル時間 675 ms
コンパイル使用メモリ 82,500 KB
実行使用メモリ 77,160 KB
最終ジャッジ日時 2025-04-17 16:25:03
合計ジャッジ時間 2,118 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

N = int(input())
S = [input() for _ in range(N)]
result = [[None for _ in range(N)]for _ in range(N)]
rest = set()
for i in range(N):
  for j in range(N):
    if i == j:
      result[i][j] = 0
      continue

    if S[i][j] == "o":
      result[i][j] = 1
      result[j][i] = -1
    elif S[i][j] == "x":
      result[i][j] = -1
      result[j][i] = 1
    else:
      rest.add((min(i, j), max(i, j)))

rest = list(rest)
def judge(games):
  win_cnt = [0] * N
  used = set()
  for i in range(N):
    for j in range(N):
      if i == j:
        continue
      if result[i][j] == -1:
        continue
      if result[i][j] == 1:
        win_cnt[i] += 1
        continue

      a, b = i, j
      if a > b:
        a, b = b, a
      if (a, b) in used:
        continue
      idx = rest.index((a, b))
      if games[idx] == 1:
        win_cnt[a] += 1
      elif games[idx] == 0:
        win_cnt[b] += 1

      used.add((a, b))

  val = win_cnt[0]
  sorted_win_cnt = sorted(set(win_cnt), reverse=True)
  return sorted_win_cnt.index(val) + 1

ans = N
def dfs(games):
  if len(games) >= len(rest):
    global ans
    # 未試合すべてに対する結果が揃ったら判定する
    ans = min(ans, judge(games))
    return

  dfs(games + [0])
  dfs(games + [1])

dfs([])
print(ans)
0