geam1113’s diary

主にAtcoderのコンテストの備忘録を書きます。AtCoder緑と水色を行ったり来たりしています。

AtCoder Beginner Contest 295 備忘録

ABC 全組問題

コンテストページ: AtCoder Beginner Contest 295 - AtCoder
コンテスト中AC: A〜D

D - Three Days Ago

便宜上、 $S_0$ が空文字として存在するものとします。なお、以下に示す解法で「文字」と表現したときには空文字は無視し、0,1,2,3,4,5,6,7,8,9を指すものとします。

問題文の $(l,r)$ が満たすべき条件を以下のように言い換えられます。

$S$ の $l$ 文字目から $r$ 文字目までについて、すべての文字の個数が偶数である

更に以下のように言い換えられます。

$S$ の「 $0$ 文字目から $l-1$ 文字目」と、「 $0$ 文字目から $r$ 文字目」について、全ての文字の個数の偶奇が等しい

ここで、10桁の2進数 $f_i$ を定めます。
$f_i$ は、 $S$ の $0$ 文字目から $i$ 文字目までに文字 $j$ が偶数個含まれているなら、 $j$ ビット目が0、奇数個なら1とします。

このようにすると、 $(l,r)$ の条件は更に言い換えられます。

$f_{l-1} = f_r$

そこで、 $i=0,1,2,\cdots ,N$ について、 $f_i$ を計算し、その個数をカウントします。ここから選ばれる2つのインデックスの組は、問題文の条件を満たします。
よって、 $f_i = x$ となるインデックスの個数を $cnt_x$ 個とすれば、 $_{cnt_x}C_2$ 個が条件を満たします。従って、 $x=0,1,\cdots ,2^{10}-1$ の全てについてその総和をとれば、答えとなります。

ここで、 $f_i$ は $f_{i-1}$ の $S_i$ ビット目のビットを反転させることで $O(1)$ で計算可能です。

$f_i$ の記録にハッシュマップを使えば、 $O(N)$ で計算可能です(もしくは、 $2^{10}-1$ の方が大きくなります)。