結果

問題 No.43 野球の試合
コンテスト
ユーザー work-furukawa
提出日時 2025-04-17 16:21:49
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,590 bytes
コンパイル時間 335 ms
コンパイル使用メモリ 82,168 KB
実行使用メモリ 75,904 KB
最終ジャッジ日時 2025-04-17 16:21:51
合計ジャッジ時間 1,751 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 6 WA * 1
権限があれば一括ダウンロードができます

ソースコード

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:
      if i == 0:
        # 0番目のチームの最高順位を知りたいので未対戦の場合は勝ちを設定しておく
        result[i][j] = 1
        result[j][i] = -1
      else:
        if result[min(i, j)][max(i, j)] is None:
          # 0番目との対戦以外のものを格納しておく
          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