プログラマランキング

順位
問題の説明
ボクシングの試合にはn人のボクサーが参加し、それぞれ1番からn番まで参加した.ボクシングの試合は1対1で行われ、A選手の実力がB選手より優れていれば、A選手はいつもB選手に勝つ.審判は与えられた試合の結果に基づいて選手をランキングしたいと思っている.しかし、いくつかの試合結果を失ったため、正確な順位はつけられなかった.
アスリートの数n,試合結果の2次元配列結果をパラメータとして与える場合は,正確に並べ替えられるアスリートの数を返すために解関数を記述してください.
せいげんじょうけん

選手の数は1名以上100名以下.

試合の結果は1試合以上4500試合以下であった.

その結果、各行[A,B]を並べてA選手がB選手に勝ったことを示す.

すべての試合の結果に矛盾はなかった.

I/O例
nresultsreturn5[[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]]2
I/O例説明
2番選手は[1,3,4]選手に敗れ、5番選手が勝利したので4位だった.
5番は4位の2番に負けて5位だった
concept

Google霊箱.これはまったく思いもよらなかった.

で一番勝ったのは一番すごいものではない...!勝っても相手に負ける可能性があるから...

だからグーグルの霊箱...

Code

def solution(n, results):
    answer = 0
    #정확하게...?
    #가장 많이 이긴 놈이 제일 쎈게 아니다...
    #이긴수가 비슷하더라도.. 상대 녀석에게 졌을 수 있기 때문..!
    #그렇담 제일 많이 진 녀석으로 생각해도..?
    graph = [ [0]*(n+1) for _ in range(n+1)]
    for win, los in results:
        graph[win][los] = -1
        graph[los][win] = 1
    
    #floyd warshall
    for k in range(1,n+1):
        for i in range(1,n+1):
            for j in range(1,n+1):
                #자기 자신을 제외하고 승패 여부를 알 수 없는 경우
                if(i!=j and graph[i][j] == 0):
                    if (graph[i][k] == 1 and graph[k][j] == 1):
                        #삼단논법 마냥 가능하다면
                        graph[i][j] = 1
                    elif(graph[i][k] == -1 and graph[k][j] == -1):
                        graph[i][j] = -1
    #승패를 확연하게 알 수 있는 것이 왜 이기고 지기고 모두 명확해야하는지 아직 이해하지 못함
    for i in range(1,n+1):
        if graph[i][1:].count(0) == 1:
            answer+=1
    return answer

リファレンス

パス

に移動

すべてのパスの最低コスト.

...