ABC 401-500/ABC402C - Dislike Foods - 競技プログラミング用 知識集積所

---

問題

ABC402C

必要知識

B以下レベルの内容は省略

• 逆写像（未作成）
• 累積和

考え方

単純にやると、各食材が何日目に食べられるようになるか探すのにn回の処理が必要で、それを食材数だけループするとTLEする。
そこで、高速化のためにBの逆写像を用意する。
すなわち、B.at(2)=3（2日目には食材3が解禁される）に対してC.at(3)=2（食材3が解禁されるのは2日目）を作っておけば、食材1つにつき1処理で終わる。

各料理の食材の解禁日の最大値を記録していくことで、「その日に新たに食べられるようになる料理はいくつあるか」を表す数列が作れる。
あとはその累積和を取ってから出力すればよい。

解答例

解答例

注意点

別解

苦手食材数の方を管理する

「各料理の食材数」と「食材ごとにどの料理に入っているか」を記録することでも解ける。
公式解説参照。