글 읽기 - 18891번 문제 내부 표현 관련 문의

eric9709 4년 전 6

18891 문제에서 1단계 부분의 수식을 보면 "r₀:지역구 무소속 당선인수" 라고 명시되어 있습니다.

제가 문제를 풀던 중 헷갈려 관련 자료를 찾아보던 중 하단 링크에서는 r₀에 해당하는 내용이 "비례대표 의석을 배분받지 못하는 정당들의 의석수 합산" 이라고 되어 있습니다.

문제에 명시된 대로 풀어야 할지 아니면 실제 선거법에 나온 대로 풀어야 할지를 모르겠어서 수정 문의드립니다.

첨부한 코드는 제가 하단 링크를 기준으로 작성한 Python 코드입니다. 예제와 이번 총선 결과를 넣었을 때에는 잘 작동하지만, '틀렸습니다' 결과가 나왔습니다.

감사합니다.

http://www.peoplepower21.org/Politics/1681824?_ga=2.177566822.2116936509.1587094894-1719454289.1587094894

import sys

def main():
    p, v = map(int, sys.stdin.readline().split())
    partyDict = {}
    seatSum = 0
    validVoteSum = 0

    # parsing area
    for _ in range(p):
        name, seat, vote = map(str, sys.stdin.readline().split())
        seat = int(seat)
        vote = int(vote)
        partyDict[name] = [_ + 1, seat, vote]
        seatSum += seat
        validVoteSum += vote
    
    # check other values
    noPartySeat = 253 - seatSum
    
    # check valid party
    validParty = []
    ratioValidVoteSum = 0
    invalidPartyCnt = noPartySeat
    for i in partyDict:
        ratio = partyDict[i][2] / validVoteSum
        validFlag = False
        if ratio >= 0.03 or seat >= 5:
            validFlag = True
            validParty.append(i)
            ratioValidVoteSum += partyDict[i][2]
        else:
            invalidPartyCnt += partyDict[i][1]
        partyDict[i] += [ratio, validFlag]
    
    # update valid party ratio
    ratioSeatDict = {}
    for i in validParty:
        ratioSeatDict[i] = [partyDict[i][2] / ratioValidVoteSum]
    
    # calculate ratio seat
    validSeatSum = 0
    for i in ratioSeatDict:
        temp = ((300 - invalidPartyCnt) * ratioSeatDict[i][0] - partyDict[i][1]) / 2
        seat = 0
        if temp < 1:
            seat = 0
        else:
            seat = int(temp)
            if temp - int(temp) >= 0.5:
                seat += 1
        ratioSeatDict[i].append(seat)
        validSeatSum += seat
    
    # update ratio seat to 30
    if validSeatSum > 30:
        underPriority = []
        newSeatSum = 0
        for i in ratioSeatDict:
            newSeat = 30 * ratioSeatDict[i][1] / validSeatSum
            underPriority.append([-(newSeat - int(newSeat)), partyDict[i][0], i])
            ratioSeatDict[i][1] = int(newSeat)
            newSeatSum += int(newSeat)
        underPriority.sort()
        for i in range(30 - newSeatSum):
            ratioSeatDict[underPriority[i][2]][1] += 1
    
    elif validSeatSum < 30:
        underPriority = []
        newSeatSum = 0
        for i in ratioSeatDict:
            newSeat = ratioSeatDict[i][1] + (30 - validSeatSum) * ratioSeatDict[i][0]
            underPriority.append([-(newSeat - int(newSeat)), partyDict[i][0], i])
            ratioSeatDict[i][1] = int(newSeat)
            newSeatSum += int(newSeat)
        underPriority.sort()
        for i in range(30 - newSeatSum):
            ratioSeatDict[underPriority[i][2]][1] += 1
    
    # calculate left 17 seats
    underPriority = []
    leftSeatSum = 0
    for i in ratioSeatDict:
        leftSeat = 17 * ratioSeatDict[i][0]
        leftSeatSum += int(leftSeat)
        ratioSeatDict[i][1] += int(leftSeat)
        underPriority.append([-(leftSeat - int(leftSeat)), partyDict[i][0], i])
    underPriority.sort()
    for i in range(17 - leftSeatSum):
        ratioSeatDict[underPriority[i][2]][1] += 1

    # final seat calculate
    finalSeatList = []
    for i in partyDict:
        seat = partyDict[i][1]
        if partyDict[i][4]:
            seat += ratioSeatDict[i][1]
        finalSeatList.append([-seat, i])
    finalSeatList.sort()
    for i in finalSeatList:
        print(i[1], -i[0])
    return

if __name__ == "__main__":
    main()

eric9709 4년 전 0

방금 문제는 해결했습니다.

문제에 명시된 대로 "r₀:지역구 무소속 당선인수" 로 계산해야 풀리네요.

일단 28열에 seat 변수를 넣은 것이 잘못되어 partyDict[i][1] 로 바꾼 뒤 제출했으나 틀렸다는 결과를 얻었습니다.

이후 32열과 33열을 주석처리하고 44열의 invalidPartyCnt를 noPartySeat(무소속 정당 의석 수)으로 바꾸니 accept 되었습니다.

shiftpsh 4년 전 1

죄송합니다. 제가 법 해석을 일부 잘못했습니다. 수정하도록 하겠습니다.

shiftpsh 4년 전 1

데이터를 교체했습니다. 재채점을 요청했습니다.

eric9709 4년 전 0

빠른 피드백 감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

18891번 문제 내부 표현 관련 문의

eric9709 4년 전 6

eric9709 4년 전 0

shiftpsh 4년 전 1

shiftpsh 4년 전 1

eric9709 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말