ABC161 E - Yutori

https://atcoder.jp/contests/abc161/submissions/14637689

• dif16Kなので天才的なプログラミング的思考力が必要
• 働く日が一意に決まる条件および線形時間で処理するロジックの発想が難しい
• 前からの貪欲は自明なので気づける
• 前からの貪欲と後ろからの貪欲を組み合わせる処理を方針の１つとして持っておく

計算量 のロジックを考えるだけでも難しそうな感じがするが、制約から か 程度で処理しなければならない。結論から言うと、前からの貪欲と後ろからの貪欲で実現できる。前からの貪欲でx日目に働く最小値、後ろからの貪欲でx日目に働く最大値が得られるので、前からの貪欲と後ろからの貪欲で同じ番号になる日が答えになる。計算量はになる。

ただ、相当に非自明なので、もう少し理由を考えてみる。

一見すると赤枠のように「C区間（水色グループ）でグループ化したときに働ける日が複数あったとき、働く日が一意に決まらない」というようにも見える。しかし、緑枠のような場合はC区間のグループ内に働ける日が複数あっても働く日が一意に決まる。そこで、以下のような条件で働く日が決められると考える。

1. C区間グループがK個以上ある→働く日にyutoriがあるので空白を出力
2. C区間グループの中に働ける日が1日→その日は絶対に働く
3. C区間グループの中に働ける日が複数日ある→前からの貪欲と後ろからの貪欲で異なるC区間グループの中にある働ける日は取り除き、残った日が1日しかなければ必ず働く

3の条件よりC区間のグループ内に働ける日が複数あっても緑枠は一意に決まる。