結果

問題 No.43 野球の試合
ユーザー FromBooskaFromBooska
提出日時 2023-03-18 07:30:27
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 135 ms / 5,000 ms
コード長 1,441 bytes
コンパイル時間 512 ms
コンパイル使用メモリ 81,820 KB
実行使用メモリ 76,152 KB
最終ジャッジ日時 2023-10-18 17:05:52
合計ジャッジ時間 1,701 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 36 ms
53,556 KB
testcase_01 AC 37 ms
53,556 KB
testcase_02 AC 37 ms
53,556 KB
testcase_03 AC 37 ms
53,556 KB
testcase_04 AC 38 ms
53,556 KB
testcase_05 AC 38 ms
53,556 KB
testcase_06 AC 59 ms
66,564 KB
testcase_07 AC 135 ms
76,152 KB
testcase_08 AC 38 ms
53,556 KB
testcase_09 AC 37 ms
53,556 KB
testcase_10 AC 38 ms
53,556 KB
権限があれば一括ダウンロードができます

ソースコード

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