백준[23327] 리그전 오브 레전드 (Python3)

수학적 관찰이 필요한 문제
문제는 진짜 잘 만들었지만 증명하는 데 꽤 오래 걸렸다
코테에서 이렇게 나오면 시간 내에는 못 풀 거 같다.

완전 탐색

매 요청마다 리그전의 재미를 계산한다.
Q = 200,000, N = 100,1000, l = 1, r = 100,000 인 경우
200,000 * N!로 시간 초과가 발생한다

완전 탐색 최적화

각 후보 디비전을 계산할 때, 공통적으로 계산되는 부분이 있을 것이다
이를 알기 위해 1번 팀부터 N 번 팀까지 리그전을 진행할 때 생기는 재미에 대한 식을 나열해 본 결과 공통되는 식이 있단 것을 알 수 있다.

아래 표는 예제 1을 풀어쓴 결과다.

1 ~ 2팀이 치른 결과가 1 ~ 3팀에 포함된다.

표를 보면 1 ~ 3 팀까지 리그전을 할 경우 계산 결과에, 1 ~ 2팀끼리 리그전을 한 계산들이 포함된 것을 알 수 있다.
예시를 좀 더 확장해 보자.

1 ~ 4 팀도 마찬가지로, 1 ~ 3 팀이 치룬 리그전을 한 계산들이 포함된 것을 알 수 있다.

1 ~ 3팀이 치른 결과가 1 ~ 4팀에도 포함된다.

하지만, 재미도에 대한 누적합만으로는 쿼리에 대한 답을 구하는 것이 불가능하다.
새로운 기준에 대한 누적합을 통해 쿼리에 대한 답을 구해야 한다 생각했다.

누적 합

예제의 재미도 계산 표를 관찰한 결과, 새로 팀이 포함될 때, 계산식을 다르게 표현할 수 있단 것을 발견했다.
예를 들자면, 기존 1 ~ 2 팀의 리그전에, 3팀이 포함된다면 기존 식을 이렇게 표현할 수 있다.

마찬가지로, 4팀이 포함된다면 다음과 같이 식을 통합할 수 있다.

이왕 한 김에 마지막 팀까지 포함된 결과를 정리하면 다음과 같다.

 

각 팀의 인기에 대한 누적합에 따라 식이 정리되는 것을 확인했고
여기에 대한 누적합을 구한다면 문제를 해결할 수 있다 생각했다.

정리하면, 사용할 누적합은 2가지다.

• 리그전의 재미에 대한 누적합
• 팀의 인기에 대한 누적합

누적 합 계산

1팀부터 리그전을 치르면서 얻는 재미 계산은 구하기 쉽지만,
중간부터 시작하는 경우에 대해 재미 계산 구하기는 생각보다 까다로웠다.

4 5 팀끼리만 경기를 치르는 경우를 생각해 보자
1 ~ 3팀끼리 리그를 해서 얻는 재미와 1 ~ 3 팀이 4, 5팀과 경기를 해서 얻는 재미를 빼줘야 한다.

계산식은 다음과 같이 정했다.
(1 ~ 5 팀의 리그전 누적 합) - (1 ~ 3 팀의 리그전 누적 합) - (1, 2, 3 팀이 4팀과 경기한 재미 총합)

- (1, 2, 3 팀이 5팀과 경기한 재미 총합)

여기서 1, 2, 3팀 따로 4, 5 팀 따로 묶어서 수식을 다듬으면 다음과 같다.
(1 ~ 5 팀의 리그전 재미 누적 합) - (1 ~ 3 팀의 리그전 누적 합) -
(1 ~ 3팀의 인기 누적 합 * 4 ~5 팀의 인기 누적합)

코드로 표현하면, 전체 리그전 재미를 total, 해당 팀의 인기를 funny라고 할 때 치환하면 다음과 같다.
total[5] - total[3] - (funny[5] - funny[3]) * funny[3]

쿼리에 들어오는 값 l, r로 치환하면
ex) l = 4, r = 5일 때
total[r] - total[l - 1] - (funny[r] - funny[l - 1]) * funny[l - 1] 란 계산식이 나온다.

코드

import sys
input=sys.stdin.readline

N, Q = map(int, input().split())
popular = list(map(int, input().split()))
funny = [0] * N
total = [0] * N

for i in range(N):
    p = popular[i]
    if i == 0:
        funny[i] = p
    else:
        funny[i] = funny[i - 1] + p
        total[i] = total[i - 1] + p * funny[i - 1]
funny = [0] + funny
total = [0] + total
# print(funny)
# print(total)

def main():
    for _ in range(Q):
        s, e = map(int, input().split())
        ans = total[e]
        if s == 1:
            print(ans)
        else:
            temp = (funny[e] - funny[s - 1]) * funny[s - 1]
            # print(temp)
            # print(total[s - 1])
            print(ans - temp - total[s - 1])


if __name__ == "__main__":
    main()