【경쟁 프로 전형적인 90문】010의 해설(python)

개요

경쟁 프로 전형 90문 의 해설 기사입니다.
해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다.

※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다.
※★5이상의 문제는 난이도적으로 후회하고 있기 때문에, 투고 시기가 늦어질 가능성이 있습니다. (대신 정중하게 해설 해 주시는 분이라면 꼭 부탁드립니다)

이슈010-Score Sum Queries

문제 개요

N명의 학생이 2개의 쌍으로 나누어져 있을 때, 각 클래스의 학적 번호 L~R번의 합계점을 구한다.
이것을 Q개의 쿼리로 실시한다.

해결 방법

우선, 어리석게 Q개의 쿼리 1개 1개에 대해서, L~R번까지의 합계를 매번 구하는 방법이 생각됩니다만,
이 생각에서는, L~R번까지의 합계를 구하는 처리로, 최대 N회,
이것을 최대 Q회 실시하면 $O(QN)$ 가 되어, TLE가 되어 버립니다.

그래서 이번에는 누적 합을 사용합니다.
※누적합에 대해 알고 싶은 분은 여기 를 확인해 주십시오.

그러면
1. 각 세트의 누적 합 S를 구한다(N회)

2. Q개의 쿼리에 대해 $S[R]-S[L-1]$를 구한다. ($O(1)$를 Q회)

이것은 $O(N+Q)$의 계산량으로 충분히 고속으로 요구됩니다.



인용 소스 : 경쟁 프로 전형 90문 Github

구현

answer.py

N = int(input())

# 1組、2組で分けて得点を格納する
c1 = [0]*N
c2 = [0]*N

for i in range(N):
  c, p = map(int, input().split())
  if c == 1:
    c1[i] = p
  else:
    c2[i] = p

# 各組で累積和 s1, s2を求める
s1 = [0]*(N+1)
s2 = [0]*(N+1)

for i in range(N):
  s1[i+1] = s1[i] + c1[i]
  s2[i+1] = s2[i] + c2[i]

# Q個のクエリに対し、L~R番までの合計を求める
# L番は和に含めるため、L-1番までの合計をマイナスする
Q = int(input())

for _ in range(Q):
  l, r = map(int, input().split())
  sum1 = s1[r] - s1[l-1]
  sum2 = s2[r] - s2[l-1]
  print(sum1, sum2)

마지막으로

문제의 해설을 읽어도 다른 사람의 코드를 봐도 확실히 모르는 분
힘에 조금이라도 될 수 있으면 다행입니다.
코드의 개선점이나 그 외, 의견등 있으면, 부담없이 코멘트해 주세요.
또, 이 기사를 읽고 이해할 수 있었던 분은 꼭 LGTM를 눌러 주실 수 있으면 기쁩니다.
(기사 투고의 모티베가 됩니다.)

여기까지 읽어 주셔서 감사합니다.