IJPC 2012 #1: 解説: 銀メダル(Silver Medal)

• Problem Proposal: JAPLJ
• Problem Statement: qnighy
• Testing: qnighy
• Solution: qnighy

Subtask 1

1. 全ての日について、O(N)の時間をかけて、その日に意識している模試の個数を数える。O(NW)
2. 全てのk(1≦k≦N)と、日付の範囲[A,B]について、[A,B]内に意識している模試の個数がk以上かどうかを調べる。O(NW^3)

全体でO(NW^3)

Subtask 2

1. 全ての日について、O(N)の時間をかけて、その日に意識している模試の個数を数える。O(NW)
2. 全ての日付の範囲[A,B]について、[A,B]内の日付で、意識している模試の個数が一番小さい日を調べる。O(W^2)

全体でO(NW+W^2)

Subtask 3

1. それぞれの模試について、意識しはじめる日と意識し終わる日を調べ、それら2N個のイベントを日付順にソートする。このとき、同じ瞬間であれば、意識し始めるほうが早く来るようにする。
2. スタックを用意して、ちょうどk個の模試を意識し始めた直近の日付を記憶しながら、それらのイベントを順に処理する。

全体でO(N)