問題リンク
問題概要
連続するN日間のうち、次のルールでK日を選んで働くとする。
- 働いた日から次に働くまでC日以上空ける。
- あらかじめ指定された働かない日は働かない。
働く日をどのように選んでも、必ず働くことになる日を全て求めよ。
なお、条件を満たす労働日の選び方が存在することは保証される。
解法
まず、働かなくても良いような日が満たす条件を考えると、
ある労働計画を考えた時に対して
- その日は働かない
- 他の労働日をできるだけ前に移動させて、その労働日を前にずらせる
- 後の労働日をできるだけ後に移動させて、その労働日を後にずらせる
のどれかを満たせば良さそうとわかる。
したがって、D日目が必ず働く日になる条件は、
労働日を前から貪欲に決めた\(s_1 < s_2 < \ldots < s_K\)と後ろから貪欲に決めた\(t_1 < \ldots < t_K\)に対して
\(D = s_i = t_i\)となる\(i\)が存在することである。
提出
https://atcoder.jp/contests/abc161/submissions/11519168
感想
500点で貪欲が出るとなんか見落としてそうでちょっと不安になる。
