Pythagorean Expectation ( ACM-ICPC 교내 예선 )

여전히 ACM-ICPC 교내대회 예선 문제다. 그리고 길다. 누가 대신 타이핑 해줬으면 좋겠다ㅜㅜ

개인적으로 프로야구를 챙겨보진 않는데 야구 분석 기법들 (수학의 영역) 은 관심이 많다. 직접 야구를 하는 입장에서 보면 달리기도 하고 던지고 치기도 하는 등 동적인 운동인데 반해, 분석하는 입장에서는 굉장히 정적인 운동이다. 투수로부터 시작해서 다시 투수에게 돌아가기 전까지 발생하는 이벤트들만 시간 순으로 정리하면 경기 전체 (보크까지 포함해서) 를 완벽히 복기할 수 있다. 지금 푸는 문제는 점수 득실만을 가지고 해당 팀의 승률을 추측해볼 수 있는 통계적 기법을 다룬다. 이러한 여러 기법에 관심있는 사람들은 세이버매트릭스 ( Sabermetrics ) ( 나무위키 Link )를 찾아보면 될 것이다.

---

[문제]
유명한 피타고라스의 정리와 유사한 형태의 피타고라스 기대값 (Pythagorean Expectation)이 야구와 같은 스포츠 경기에 자주 사용된다. 피타고라스 기대값은 빌 제임스 (Bill James)에 의해 정의되었으며, 이 값은 특정 야구팀이 한 시즌 동안 얼마나 잘 했는지를 평가하는 지표 중 하나로 사용된다. 한 야구팀의 피타고라스 기대값 W는 아래 식과 같이 정의된다.

여기서 S는 해당 팀의 총 득점 수를, A는 해당 팀의 총 실점 수를 나타낸다.

이 기대값을 실제 승률과 비교하여, 해당 팀이 한 시즌을 얼마나 잘 보냈는지 평가할 수 있다. 예를 들어, 한화 이글스는 2014 시즌에 619 득점과 889 실점을 했다. 즉, S=619, A=889이 되어, 한화 팀의 피타고라스 기대값은 W= 619^2/ (619^2 + 889^2) = 0.326이 된다. KBO 규정에 따르면, 한 시즌당 한 팀은 128번 경기를 해야 하므로, 한화는 0.326 * 128 = 41.728 경기에서는 승리했어야 한다. 실제 한화는 49 경기에서 승리했기 때문에, 2014 시즌을 그리 나쁘지 않게 보냈음을 알 수 있다. 반면에 롯데 자이언츠는 S=715이고 A=719이 되어, W=0.497이 된다. 따라서 0.497 * 128 = 63.616 경기 이사이을 이길 것으로 기대되었지만, 실제론 58경기만 승리했다. 결국, 롯데에게 2014년은 기대에 많이 못 미친 시즌이었음을 알 수 있다.

n 개의 팀에 대한 기록이 주어지면, 이 기록으로부터 팀 별 피타고라스 기대값을 계산한 후, 그 중 최대 기대값과 최소 기대값을 출력하는 프로그램을 작성하시오.

[입력]
입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫 줄에는 두 양의 정수 n (2<=n<=1000)과 m (2<=m<=1000)이 주어진다. 여기서 n은 팀 개수이며, m은 전체 경기 수이다. 다음의 m개 줄에는 각 경기에 대한 정보가 주어진다. 하나의 경기는 네 개의 정수 a,b,p,q로 주어지는 데, 팀 a와 팀 b가 경기를 했고 팀 a는 p득점을 팀 b는 q득점을 했다는 의미이다. 여기서 1<= a≠b<=n이며, p와 q는 모두 음이 아닌 20이하의 정수이다. 하나의 테스트 데이터에서 팀 당 경기수가 반드시 같을 필요는 없다. 만약 어떤 팀의 총 득점과 총 실점이 모두 0이라면, 그 팀의 기대값은 0으로 정의한다.

[출력]
출력은 표준출력을 사용한다. 각 테스트 데이터에 대해, 두 정수 값을 한 줄에 하나씩 출력해야 한다. 첫 번째 출제는 최대 피타고라스 기대값에 1,000을 곲한 값의 정수부분을 출력하고, 두 번째 줄에는 최소 피타고라스 기대값에 1,000을 곱한 값의 정수부분을 출력한다.

[예시]

입력 예제	출력예제
2 3 5 1 2 3 5 1 3 10 1 1 2 0 7 2 3 9 3 3 2 4 5 4 6 1 2 0 11 1 3 17 13 1 4 17 1 2 3 7 12 2 4 19 17 3 4 17 0	871 100 753 103

# input T = number of test cases
T = input()
 
for _ in xrange( T ):
    # input n = number of teams & m = number of games
    n,m = map(int, raw_input().split()) 
    
    # store team scores into the team list
    team = list()
    for i in xrange( n+1 ): 
        # In order to make the index equals the team number,
        # the length of team list should be n+1 
        team.append( [0,0] )
 
    for i in xrange( m ):
        # input a,b = team numbers & p,q = scores
        a,b,p,q = map(int, raw_input().split())
 
        # update the total team scores in team list
        team[a] = [ team[a][0] + p, team[a][1] + q ]
        team[b] = [ team[b][0] + q, team[b][1] + p ]
 
    # store Pythagorean Expectation data into the pytha list
    pytha = list()
    for i in xrange( 1,n+1 ):
        S = float( team[i][0] ) # S:number of runs the team scored
        A = float( team[i][1] ) # A:number of runs the team allowed
 
        # calculation of Pythagorean Expectation
        if S == 0 :
            pytha.append( 0.0 )
        else :
            pytha.append( S**2 / ( S**2 + A**2 ) )
 
    pytha.sort()
    print int( pytha[-1]*1000 )  # best team
    print int( pytha[0]*1000 )   # worst team

코드 리뷰를 할 것 없이 그냥 코드에 주석으로 설명을 했다. 주로 문장이 되게끔 적어서 오해없이 이해할 수 있을 것이다. list와 tuple의 packing/unpacking이 익숙하다면 큰 문제 없을 것이다. 다만 map이란 함수가 낯설 수도 있을 것 같아서 이 내용만 추가하겠다. 현재 위에 쓴 map은 첫 인자 ( argument ) 로 함수를 받고 두 번째 인자로 list를 받는다. list의 원소들을 대상으로 첫 인자로 받은 함수 결과값들로 대체하는 식이다. 내가 만약에 구현한다면 다음과 같이 짤 것이다.

def my_map( func, sequence ):
    result = list()
    for item in sequence:
        result.append( func( item ) )
    return result

참고용으로 아래에 map의 help 메세지를 덧붙인다. 위에서 구현한 my_map보단 더 많은 기능이 있긴 하다.

Help on built-in function map in module __builtin__:
 
map(...)
    map(function, sequence[, sequence, ...]) -> list
    
    Return a list of the results of applying the function to the items of
    the argument sequence(s).  If more than one sequence is given, the
    function is called with an argument list consisting of the corresponding
    item of each sequence, substituting None for missing values when not all
    sequences have the same length.  If the function is None, return a list of
    the items of the sequence (or a list of tuples if more than one sequence).