ABC229 参加記録 - geam1113’s diary

コンテスト中AC:A〜E

連続させたい個数をm個に固定すると、S連続する部分列のうち、m個の要素を含むものについて、いずれか1つでも全てXにできれば、連続m個を達成できます。

必要な操作回数は、部分列に含まれる'.'の個数に他ならず、予め'.'の個数に関する累積和をとっておけば、各部分列で $O(1)$ で計算できます。

したがって、全部分列の判定は、 $O(|S|)$ で可能です。

例　入力例1 m = 4の時

XX...X.X.X.

部分列は、

XX..

X...

...X

..X.

.X.X

X.X.

.X.X

X.X.

最小2回で、4個連続が可能

K回以下なので、達成可

m個連続させられるかという問題は、m個が可能なら、m-1個も可能です(連続する部分列を１つ短くする)。また、m個ができないなら、m+1個も達成できません。

よって、最大個数は二分探索可能です。

従って、 $O(|S|log|S|)$ で問題を解くことができました。

追記:公式解説はしゃくとり法でした。

連結成分の管理はUnion-Findで可能なので、初期状態から削除していくより、最終状態から追加していく方が簡単な場合が多いです。

今回も、頂点がない状態(頂点Nを消した直後)から開始し、頂点Nから2までを順に追加していきます。(頂点iを追加した後の状態は、頂点i-1を削除した直後の状態となります。)

頂点iを追加した時の動きは、

・頂点iの分、連結成分の個数を1つ増やす

・頂点iと接続する辺e=(i,j)について、

　jがまだ追加されてない(j<i)なら、無視

　jが既にiと連結なら無視

　iとjが非連結なら、iとjを併合する。この時、連結成分の数が1つ減る。

となります。

各頂点につき1回、接続する辺を調べるため、 $O(N+M)$ です。