ARC130 参加記録 - geam1113’s diary

コンテスト中AC:A,B

同一文字が連続する領域から、i文字目とj文字目取り除いて $S_i,S_j$ を作る

ことと、

$S_i,S_j$ が等しい

必要性は明らかです。

十分性を示します。

$S_i,S_j$ の取り除く位置をi<jとします。

iはaを取り除くことにします。jは、iで取り除くaの連続した領域でないという仮定なので、aと異なる文字がiからjのどこかに存在し、今回bとおきます。

S: .....a..ab.....

aの連続した領域から1つ取り除くと $S_i$ ではbが左に詰められます。jで取り除くのはb以降なので、 $S_i$ でbが存在する場所には必ずaが存在します。

$S_i$ : .....a..b.....

$S_j$ : .....a..a.....

よって、連続でない領域を取り除くと $S_i,S_j$ は異なり、十分性が示されました。

計算方法としては、

連続する領域について、

aaaa

0123

という風に0からインデックスをふると、このインデックスは連続する領域で、かつ自分より手前にある同一文字の個数(すなわちj番目の文字に対し、i<jであるiの個数)に一致し、これを足していけば答えになります。

ランレングス圧縮して、連続する個数をCとして、C(C-1)/2を足していくのでもよいかもしれません。

操作を逆順で考えると、一回塗った箇所の色の変化がなくなるので考えるのが楽になります。

Q番目から1番目までで、i番目に塗る色の増減は、

・その行、列が既に塗られていたら0

・まだ塗られていない場合、既に塗られている行、列の数をそれぞれ $X_r,X_c$ として、行を塗るなら $W-X_c$ 、列を塗るなら $H-X_r$
となります。

既に塗られた行、列の管理はC++のunordered_mapのようなハッシュマップなら $O(1)$ でできるので、 $O(Q)$ となります。