prefix sum만이 누적합이 아니다1 - value 누적합

1. 문제

 

28449번: 누가 이길까 (acmicpc.net)

28449번: 누가 이길까

 

2. 풀이

 

n명의 리스트 A를 오름차순 정렬, m명의 리스트 B를 오름차순 정렬하고 

 

A의 모든 원소 A[i]에 대하여, 리스트 B에서 lower bound와 upper bound를 찾아서 

 

lower bound 밑으로는 A[i]보다 작은 수들이니까 A의 승리이고, upper bound 위로는 A[i]보다 큰 수니까 B의 승리

 

lower bound와 upper bound 사이에는 A와 같은 값들이니 무승부

 

이렇게 하면 풀수있기는 한데, 예외처리를 해야돼서 실수하기 쉽다

 

lower bound가 upper bound보다 더 크다거나... lower bound가 없다거나... upper bound가 없다거나..

 

같은 값이 없어서 lower bound와 upper bound가 같다거나 등등

 

 

그런데 점수가 10만 이하라는 점에 주목한다면 A,B 각각을 순회해서 A,B팀이 10만 이내에 어떤 점수들을 가지고 있는지 counting 배열을 구한다

 

각각의 counting 배열의 크기는 10만 이내이며, 이렇게 만든 counting 배열을 다시 순회한다

 

왼쪽부터 오른쪽으로 1부터 10만까지 순회했을때 countingA[i]와 countingB[i]중에 0이 아닌 값이 있다면?

 

예를 들어 A = [1000,90,3,20000], B = [1,3,100000]

 

그러면 A = [0,0,0,1,....,1,......,1,.....,1,.....0]

 

B = [0,1,0,1,........,1]

 

 

 

1점부터 10만점까지 순회해서 i점에 A팀과 B팀중 존재하는지를 체크하는거임

 

먼저 i = 1에서 B[i] = 1이고 A[i] = 0이기 때문에 B가 1승을 한거임

 

 

 

그리고 다시 가면서... i = 3에서 A[i] = 1, B[i] = 1이니까 둘이 무승부긴한데..

 

 

 

여기서 B팀은 i = 1에서 1명 있기 때문에 A[3] = 1인 경우가 1승을 해야한다

 

이걸 어떻게 알아?

 

이 counting 배열을 prefix sum을 해? 그러면 A = 0 0 0 1 1 ... 2 ... 3 ... 3과 B = 0 1 1 2 2 2 ..... 3인데

 

i = 3에서 A[i] = 1, B[i] =2인데.. 이걸로는 A가 1승? B가 2승? 어떻게 할수가 없어

 

그래서 그냥 i = 1부터 10만까지 순회하면서 A팀의 value a = 0, B팀의 value b = 0으로 시작하고

 

점수 비교를 한 순간 value값들에 누적합 시켜주는것

 

여기서 value는 현재 i점보다 작은 A,B팀의 팀원 수가 된다.

 

 

 

여기서 현재 a = 0, b = 0이고 B[i] = 1, A[i] = 0이라 B는 1승했고, b += B[i]를 해준다

 

다시 i = 3까지 가면...

 

 

 

A[i] = 1, B[i] = 1인데 a = 0, b = 1이고 a,b는 i = 3보다 작은 점수들을 보유한 팀원 수이다.

 

그래서 먼저 A[i], B[i]를 비교해서 수가 같으니까 1번 무승부를 했고

 

A[i]와 b를 비교해서 A[i]*b만큼 A가 승리했고, B[i]와 a를 비교해서 B[i]*a만큼 B가 승리했다.

 

그리고 다시 a += A[i], b += B[i]해주고 다음 i로 넘어가는 식으로

 

n,m = map(int,input().split())

a = list(map(int,input().split()))
b = list(map(int,input().split()))

A = [0]*(100001)
B = [0]*(100001)

#A,B팀 각각이 10만 이내에 보유한 점수들을 counting
for i in range(n):
    
    A[a[i]] += 1

for i in range(m):
    
    B[b[i]] += 1

answer = [0,0,0] #A팀 승, B팀 승, 무승부

#A,B팀이 현재 i점보다 작은 점수를 가진 팀원 수 누적합
a = 0 
b = 0

for i in range(1,100001):
    
    #현재 i점에서 A[i]가 0이 아니고, B[i]가 0인 경우?
    if A[i] != 0 and B[i] == 0:
        
        answer[0] += b*A[i] #A팀은 i점보다 작은 모든 B팀에 대해 이긴다
        a += A[i]
    
    #현재 i점에서 B[i]가 0이 아니고, A[i]가 0인 경우?
    elif B[i] != 0 and A[i] == 0:
        
        answer[1] += a*B[i] #B팀은 i점보다 작은 모든 A팀에 대해 이긴다
        b += B[i]
    
    #A[i],B[i] 둘다 0이 아니라면?
    #현재 i점을 보유한 A,B팀은 A*B만큼 무승부가 나고
    #A는 i점보다 작은 b에 대해 이길 수 있고
    #B는 i점보다 작은 a에 대해 이길 수 있고
    elif A[i] != 0 and B[i] != 0:
        
        answer[0] += A[i]*b
        answer[1] += B[i]*a
        answer[2] += A[i]*B[i]

        a += A[i]
        b += B[i]

print(*answer)

 

 

누적합하면 prefix sum만 생각하지 말라 이거지