ABC299に出た。

A: 位置を記録して比較するだけ、最近ABCでこんな感じの問題よく見る気がする

B: 面倒だが愚直にやればよい

C: ランレングス圧縮すれば実装楽

D: ちょっと変則的な二分探索問題。白と黒の境目は1か所とは限らないが、「確認された中で最右の白」と「確認された中で最左の黒」を記録すればその間には必ず1か所以上の境目があるため、真ん中の位置の色を見て二分探索の要領で詰めていけば境目を発見できる。

E: 各頂点$p_i$からの各頂点の距離をBFSで求める。$p_i$から距離$d_i$未満の頂点は黒であってはならない。この制約で黒であってはならない頂点を決め、それ以外は全て黒で塗る。$p_i$から距離$d_i$以上の頂点は全て黒でも頂点$p_i$に関する条件には抵触しないからだ。これで構築した結果を検証してみてダメならNo、条件を満たすならYesになる。$O(K(M+N))$で解ける。

F: 分からず。部分文字列の数を数えるDPは知っていたのでその応用だろうとは思ったが、解けなかった。

G: いい感じに段取りを踏んで詰めて解けた。Fにこだわっていなければもっと早く解けていたと思う。

まず、$B_1$を確定することを考える。$A_i$を右から見て行き、1～Mが初めて全て出そろった場所をkとする。kまたはkより左の$A_i$ならばどれでも$B_1$にできることが分かる。辞書順最小を求めるのでkまたはkより左の$A_i$で最も小さいものを$B_1$とすればよい。また、同じ値ならば出来るだけ左から取った方が$B_2$以降を選ぶ幅が広がるのでできるだけ左を取る。

次は$B_2$を決める。$A_i$を右から見て行き、$B_1$を除く1～Mの値が全て出そろった場所を再びkとする。そしてやはり、kまたはkより左の$A_i$で$B_1$を除く最も小さいものを$B_2$とすればよい。以降も同様の手順で選んでいくことで最善の$B$を構築することができる。

これを単純に実装すると、$O(MN)$くらいになってしまう。そこで、kを求めるくだりとkまたはkより左で最も小さい値を見つけるくだりを高速化してやりたい。

まずkを求めるくだり。1～Mの各数字について、同じ数字で最も右のものの位置をsetなどに記録する。そしてその中で一番左のものを見ればよい。$B_2$以降を求める際は既に決めた数字は見なくてよいので、setから順にその数字の最右位置を消していけばよい。

次に最も小さい$A_i$を求めるくだり。これは単純にセグ木で区間minをやればよい。同じ数字なら出来るだけ左からなので、セグ木に(数値, 位置)の組を乗せて辞書式で比較させる。

これで各パートが$O(\log N)$で済み、全体$O(M\log N)$になった。