해설
를 번 문제 앞의 최대 난이도, 를 뒤의 최소 난이도라 하자. 앞에 문제가 없으면 , 뒤에 문제가 없으면 로 둔다. 처음 막히는 문제가 번인 피해자 수는
이다.
이 값을 모든 에 대해 더한다. 오른쪽부터 훑어 를 구한 뒤, 왼쪽부터 를 갱신하며 합산한다. 시간과 공간 복잡도는 이다.
증명
실력이 인 참가자는 난이도가 정렬되어 있다면 이하인 문제를 모두 푼다. 따라서 피해자가 될 필요충분조건은 처음 막힌 문제의 뒤에 자신이 풀 수 있는 문제가 남아 있는 것이다.
처음 막히는 문제가 번이라는 조건은 이고, 뒤에 풀 수 있는 문제가 있다는 조건은 이다. 두 조건을 만족하는 실력의 개수는 이다. 각 피해자에게 처음 막히는 문제는 유일하므로, 합산할 때 중복도 누락도 없다.