結果

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

ソースコード

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

        idx = rest.index((i, j))
        if games[idx] == 1:
          win_cnt[i] += 1
        elif games[idx] == 0:
          win_cnt[j] += 1

  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