Educational Codeforces Round 53

スポンサーリンク

A. Diverse Substring

存在するならば長さ 2 のものがあります.

B. Vasya and Books

そのままシミュレーション.列のどこまでが消えているかを持ちます.

C. Vasya and Robot

二分探索します.変更できる区間ができたときの判定ができればよいです.

D. Berland Fair

シミュレーション.一周とりきれない状況になったらそのアイテムを削除するということをします.

E. Segment Sum

桁に現れた集合に対する (cnt, sum) を dp で求められます.

F. Choosing Two Paths

パスの共通部分に含まれうる辺を列挙します.そこから先に次数 2 以下の辺しかないと無理です.生き残ったグラフで直径を求めるとその直径が共通部分にとれます.そこから伸ばせる長さも込みで直径を計算します.

G. Yet Another LCP Problem

suffix array, lcp array を作っておくと, 次のような問題になります:

  • 集合 $A, B$ が与えられる.各 $a\in A,b\in B$ に対する $\min(lcp[a],\ldots,lcp[b-1])$ の和($a>b$ ならその逆)を求めよ.

興味のある suffix array の index だけをとりだし,その隣接する index の間の lcp を求めておくことで,lcp array の大きさは $O(|A|+|B|)$ としてよいです.この問題を $O(|A|+|B|)$ 程度で解ければよいことが分かります.

$b$ をスライドさせながら,$ans[i] = \min(lcp[i],\ldots,lcp[b-1])$ という列 ans を管理することを考えると,この列に $O(n)$ 回の区間変更を行いながら,興味のあるインデックスの部分の sum をとれればよいということになります.

CodeForces
スポンサーリンク
シェアする
maspyをフォローする
maspyのHP
タイトルとURLをコピーしました