現在の進捗
満点解法まですべて作成済みです。
他の問題はこちらから。
https://qiita.com/clara775/items/57dbe85edcad1f4483c8
問題
日本語問題文はこちら
小課題1 N=2
この小課題では、Anika以外にもう1人しか参加者がいません。他の参加者をBと呼びましょう。この時、答えが0にならないのはどういう場合でしょうか？
例えば、Anikaが2回連続でBを追い越す時、Bは前にしか進んでいないことから1回目の追い越しと2回目の追い越しの間にAnikaは丸一周したことがわかります。よく考えると、これが唯一答えが増えるチャンスであるとわかります。
より具体的には、ある追い越しについて、その一つ前のイベントも追い越し（つまり入力が1）であれば答えを1つ増やします。追い抜き（-1）が起きた際にはこれをリセットします。
小課題2 Anikaは追い越しのみ行う
この小課題では他の参加者の動きは考える必要がなく、立っているものとみなしてAnikaのみが走ることにしても成り立ちます。よって、それぞれの参加者についてAnikaに追い越された回数を数え、その最大-1が答えとなります。
小課題3 N,Qが100以下
この小課題では、小課題1の解法を改善する必要があります。
まず、Anika以外の参加者はそれぞれAnikaの前にいるか、後ろにいるかという2つの状態を持っています。もしAnikaが追い越す直前に参加者が前にいれば、状態を「後ろにいる」に変更すれば良いです。もし追い越す直前に参加者が後ろにいれば、Anikaは少なくとも一周する必要があります。また、この際には他のすべての参加者の状態をAnikaの前にする必要があります（もし後ろに参加者がいるとすると、その参加者も追い越したことになるため）。
これで答えの下限を計算でき、この下限はそれぞれの参加者が追い越しに必要な最小限の距離を動くことで達成できます。
計算量は$O(N^2)$で、これは参加者全員の状態を毎回変更する必要があるかもしれないからです。
小課題4 満点解法
小課題3の解法の、特に全員の状態をAnikaの前にする部分を高速化すれば、満点が取れそうだと考えます。これにはいくつかやり方があります。
- それぞれの参加者の状態をbool型で保持しておくのに加えて、Anikaの後ろにいる参加者のリストをvectorで持っておきます。すると、状態の更新部分をNに比例ではなく、後ろにいる参加者の数に比例した計算量で実現できます。ある一つのイベントでは最大でも1人しか新たにAnikaの後ろにならないので、ならし計算量は$O(1)$であり、全体計算量は$O(N+Q)$となります。
- Anikaの後ろにいる参加者のリストはsetでも持つことができ、この方法では更新のたびにsetをclearすることで管理することができます。これで、全体計算量はlogなしのsetでは$O(Q)$、log付きのsetでは$O(QlogN)$となります。
- bool型で状態を管理する代わりに、他の参加者それぞれについて、Anikaが何周目の時にAnikaの後ろに来たかをintなどで管理します。すると、更新のたびに今Anikaが何周目か（ラップ数）をインクリメントすることで、前か後ろかの状態を以下のように判断することができます。
- 今のAnikaのラップ数=管理してある数値：その参加者はAnikaの後ろ
- 今のAnikaのラップ数>管理してある数値：その参加者はAnikaの前
よって全員に対して更新を行う必要はありません。全体計算量は$O(N+Q)$となります。