Rating Updates

현재 레이팅을 $R$이라 하자. 각 퍼포먼스 $P_i$를 순서대로 읽으면서 $R\leftarrow (3R+P_i)/4$로 갱신한다. 문제에서 갱신 결과가 항상 정수라고 보장하므로 나머지를 따로 처리할 필요가 없다.

$R_0$에서 시작하여 $i$번째 퍼포먼스를 처리한 뒤 $R=R_i$라고 가정하자. 다음 퍼포먼스를 읽고 문제의 식을 적용하면 이 된다. 수학적 귀납법에 의해 모든 대회를 처리한 뒤의 은 이다.

$R$과 $P_i$는 최대 $5\cdot10^8$이므로 $3R+{}_{}$는 최대 이다. 따라서 모든 계산에 32비트 정수형을 사용할 수 있다.

서브태스크 1에서도 같은 방법을 사용한다. $P_i\geq R_{i-1}$이므로 레이팅이 감소하지는 않지만, 갱신식은 그대로다. 각 서브태스크의 전체 시간 복잡도는 $O(T+\sum N)$이고, 입력을 차례로 읽으면 추가 공간 복잡도는 이다.

Solution written by GPT5