アルゴリズム忘備録

競技プログラミングとかデータ分析とか

F - Sandglass - AtCoder Regular Contest 082

F - Sandglass

 

容量Xで一秒間に1砂がおちる砂時計がある。時刻集合r[i]が与えられて、各時刻に砂時計をひっくり返すことがスケジュールされている。時刻0で砂時計の上半分をAという。

このとき、q個のクエリ「初期のAにある砂の量がaのとき、時刻tのAの砂の量はいくらか」に答えよ。

 

初期の砂の量をx, 現在の時刻をtとする時、時刻tでの砂の量を返す関数を f(x, t) とおく。この関数をtを固定してシミュレートしてみると、ある時刻(※1)までは一定で、そこから傾き1の直線になり、更に別の時刻(※2)から一定になる、という関数になる。つまり(※1)の時刻と値、(※2)の時刻の3個の数値がtによって変化しているだけである。

 

この3個の値を更にtを変えてシミュレートしてみると、時刻が進むたびに全体にグラフが下に移動し、0を下限として(※1)が潰れていく、その後ひっくり返して全体に上にグラフが移動し、Xを上限として(※2)以降が潰れていくというのを繰り返し、状況によっては最終的に潰れて常にxによらない固定関数に近づく。これをシミュレートしてやればよい。O(Q)。