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 をとれればよいということになります.