裏紙

ほぼ競プロ、たまに日記

CS Academy #14 - Subarrays Xor Sum

CS Academy programming

問題

問題概要

長さ $N$ の数列 $a$ が与えられる。長さが $A$ 以上 $B$ 以下の部分列に対して、xorを取った値の和を $10^9+7$ で割った余りを答えよ。

$1 \le A \le B \le N \le 10^5$
$0 \le a_i \le 10^9$

アイデア

ビットごとに独立に考えていく。今、ビットを固定する( $b$ とする)と、もとの数列 $a$ は01の数列として見なすことができるようになる((a[i]>>b)&1)。

こうなると、このビット列の中の部分列の中で、xorの値が1になる個数を数えるという問題に答えれば良いということになる。

さて、一般的な数列の部分和と同じように数列の部分に対してxorをとったものも同様に計算できる。 $i$ から $j$ の部分和が欲しければ、prefix sum( $pre$ )を用意しておいてその $pre_j$ と $pre_{i-1}$ に注目すれば良い。

次に、この部分列の長さに対する制約( $A$ 以上 $B$ 以下)をどのように対処するかを考える。個数を数えるにあたって、部分列の区間の右 $j$ を固定して考える。すると、この部分列の制約から区間の左のindexは $j-B+1$ から $j-A+1$ ということになる。つまり、 $pre_j$ の値に注目して、区間 $[j-B, j-A$ ]のpreに対して0と1の値が何個ずつあるかを保持しながら、 $j$ を増やしていくことで、この更新の処理を尺取的にできるので１つのビットに対して $O(N)$ で計算ができ、十分に間に合う。

実装(C++)

続きを読む

CS Academy #20 - Palindromic Concatenation

CS Academy programming

問題

問題概要

文字列が $n$ 個与えられる。 $i$ 番目の文字列を $s_i$ と表す時、 $s_i$ と $s_j$ の連結(この順番に並べて結合した文字列)が回文になるような組 $(i,j)(i \neq j)$ の個数を求めよ。

$1 \le n \le 10^5$
$1 \le \sum_{i=1}^{n} | s_i | \le 10^5$
$s_i$ は英小文字のみで構成される
$(i,j)$ と $(j,i)$ は区別される

アイデア

$s_i + s_j$ が回文になる時、どのような状況になれば条件を満たすかを考えてみる。この条件は文字列の長さに依存するので、以下のように3つに条件を分けて考える：

$| s_i | = | s_j |$
$| s_i | \lt | s_j |$
$| s_i | \gt | s_j |$

1のときに満たすべき条件はシンプルで、 $s_i$ をreverseしたら $s_j$ に一致することである。

次に、2のときに満たすべき条件を考えてみる。 $s_i$ の方が短いので、回文の中心は $s_j$ の途中の位置に来ることになる。よって、それぞれの文字列の長さを $I , J$ とおけば

$s_i$ をreverseした文字列と $s_j$ の末尾から $I$ 文字が一致
$s_j$ の先頭から $J-I$ 文字が回文になっている

という2つの条件を同時に満たす必要があることが分かる。

3についても対称に考えれば、

$s_j$ をreverseした文字列と $s_i$ の先頭から $J$ 文字が一致
$s_i$ の末尾から $I-J$ 文字が回文になっている

という2つの条件を同時に満たす必要があることが分かる。

$n$ の制約から、それぞれのペアをとってきて比較するということは間に合わなさそうなので、別の方針を考える必要がある。そこで、ハッシュ値を利用して各 $s_i$ とペアを作ることが出来る文字列の個数を探す。

条件1に関しては、各文字列をreverseしたときのハッシュ値をカウントしておけば簡単に計算できる。以下では2,3について考える。

まず、 $n$ 個の文字列は長い方から順に処理していくことにする。そして、mapにハッシュ値をカウントしていく。そのときに、先頭から $x$ 文字が回文になっていれば残りの末尾の文字のハッシュ値を+1し、末尾から $x$ 文字が回文になっていれば残りの先頭の文字のハッシュ値を+1とする。

この、「回文になっているかどうか」という判定は、各文字列に対して元の文字列と、reverseした後の文字列でそれぞれローリングハッシュを構築し、そのハッシュ値の比較をすることで $O(1)$ で判定することが可能になる。

各文字列 $s_i$ に対して、ペアを作ることが出来る文字列の個数はこの $s_i$ をreverseしたもののハッシュ値のカウントに一致する。

実装(C++)

続きを読む