結果

問題 No.43 野球の試合
コンテスト
ユーザー FromBooska
提出日時 2023-03-18 07:30:27
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 136 ms / 5,000 ms
コード長 1,441 bytes
コンパイル時間 196 ms
コンパイル使用メモリ 81,852 KB
実行使用メモリ 76,284 KB
最終ジャッジ日時 2024-09-18 13:05:35
合計ジャッジ時間 1,485 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

# N<=6なのでありうる試合数はマックス15
# 残りの試合に番号を付けてビット全探索できるだろう
# 実装が面倒だと思う

N = int(input())
S = []
dic = {}
num = 0
for i in range(N):
    temp = list(input())
    S.append(temp)
    for j in range(N):
        if j > i and temp[j] == '-':
            dic[num] = (i, j)
            num += 1
    
#print(S)
#print(dic)

ans = N

for bit in range(1<<num):
    temp_table = [['?']*N for _ in range(N)]
    shift = 0
    for i in range(N):
        for j in range(N):
            if S[i][j] != '-':
                temp_table[i][j] = S[i][j]
            else:
                if j > i:
                    if bit>>shift & 1 == 1:
                        temp_table[i][j] = 'o'
                    else:
                        temp_table[i][j] = 'x'
                    shift += 1
                if j < i:
                    if temp_table[j][i] == 'o':
                        temp_table[i][j] = 'x'
                    elif temp_table[j][i] == 'x':
                        temp_table[i][j] = 'o'
    #print('bit', bit)
    #print(temp_table)
    
    win_count = [0]*N
    for i in range(N):
        win = temp_table[i].count('o')
        win_count[i] = win
    #print(win_count)
    
    zero_rank = 1
    for i in range(N-1, win_count[0], -1):
        if i in win_count[1:]:
            zero_rank += 1
    ans = min(ans, zero_rank)  
    
print(ans)
0