ARC124 A LR Constraints
カードごとに書き込める数字の数を計算していくことを考える. ここで, 各数字ごとに, 使うことのできないカードを数えることにする. ある数字$ iについて, $ c_i = Lならば, $ k_iよりも前のカード, $ c_i = Rならば, $ k_iよりも後のカードについて$ iを用いることができない. また, カード$ k_iで使用する数字は$ iに一意に定まる.
以上を適切に実装することによりこの問題を解くことができる.
計算量は$ O(NK)となり, これは十分高速である.