ABC161 E. Yutori

問題

N日間のスケジュールSが与えられ、i日目の予定S[i]がoならその日は仕事ができて、xなら仕事はできない。
このスケジュールの中、K日選んで仕事をしたい。
ただし、ある日に仕事をしたら、その直後のC日間は働いてはいけない。

このとき、必ず働く日の日付をすべて答えよ。

制約

• 1 <= N <= 2*10^5
• 1 <= K <= N
• 0 <= C <= N
• 条件を満たすように働く日を選ぶことが可能

解法

最大でM回働けるとする。
これは、日付の順方向にできるだけ最小の日付を取れるだけ取っていけば求められる。

このM回のうち、x回目に働く可能性がある日には幅がある。その幅の範囲にoの日が1個だけならば、その日は必ず選ぶ必要がある。
この幅＝幅の両端を求めたい。

これは、日付の順方向に最小の日付を取れるだけ取っていった場合と、逆方向に同様に向かって取っていった場合を考えれば、それぞれの両端の日付がわかる。

両端の幅の日付が同じ場合＝その幅の中にoの日が1つだけであるので、その日を出力すればよい。