解説
を問題 より前にある問題の難易度の最大値、 をそれより後にある問題の難易度の最小値とする。前に問題がない場合は 、後に問題がない場合は とする。最初に解けなくなる問題が 番である被害者の人数は
である。
この値をすべての について足し合わせる。右から走査して を求めた後、左から を更新しながら合計を計算する。時間計算量と空間計算量はいずれも である。
証明
難易度順に並べ替えられている場合、実力が の参加者は難易度が 以下の問題をすべて解く。したがって、被害者となるための必要十分条件は、最初に解けずに止まる問題より後に、その参加者が解ける問題が残っていることである。
最初に解けなくなる問題が 番であるための条件は であり、後に解ける問題が存在するための条件は である。両方の条件を満たす実力の個数は である。各被害者について最初に解けなくなる問題は一意なので、合計に重複も漏れもない。