AtCoder Regular Contest 166

　Cまで三完。

コンテストへのリンク

コンテスト後のツイート

AtCoder Regular Contest 166　Cまで。
A Y[i]=CならX[i]=Cでないとダメ。それ以外の場所は、AとBの個数を一致させつつ、右からCをBにしていく。全てのBの位置がXの方がY以降にあればOK。
B a,b,cとlcmについて何回やるか調べるとbit DPになる。
C 実験→oeisしました。

— titia (@titia_til) October 8, 2023

D - Interval Counts

　解説AC。

　コンテスト中は、最小値を取りたいということから、(-∞, ?]や[?, ∞)という区間をいっぱい作りたい……というところから考えてしまったが、この方針はあまり良くない。

　もっと根本的に、[L, R]という区間をいくつか張る問題だということを意識するべきだった。

　そうすると、Yの隣接差分を見ることで、区間が何個始まるか、何個終わるか、の差分が分かる。しかし、ある場所で区間が終わり、同時に始まったとすると、その二つはくっつけた方がいいのは当たり前。

　ということは、Yの隣接差分は、「各場所について区間が何個始まるか、もしくは何個終わるか」を表していることになる。そうすると、貪欲に（できるだけ昔始まった区間から）消費していった方が良いというのは自然。