CODE FESTIVAL 2017 Qual C

B - Similar Arrays

問題：数列Aに「似ている」数列の中で、各項を全て掛け合わせると偶数になるようなのはいくつ？（「似ている」の定義は問題文参照）

各Aiにつき、取り得るBiは3通り（Ai-1, Ai, Ai+1）
Bの全項の積が偶数になる数＝Bの項に偶数が1つでもある数＝（全体の数）ー（Bの項が全て奇数の数）
Aiが奇数の時、（Ai-1, Ai, Ai+1）の中で奇数はAiのみ
Aiが偶数の時、（Ai-1, Ai, Ai+1）の中で奇数はAi-1, Ai+1の2通り
$3^N - 2^{{\rm Aに含まれる偶数の数}}$

C - Inserting 'x'

C: Inserting 'x' - CODE FESTIVAL 2017 qual C | AtCoder

問題：英小文字からなる文字列sの好きな位置に'x'を挿入して回文にできるか？できるなら何回挿入すればいい？

sを前後双方から1文字ずつ見ていって、同じか調べる

両方同じなら両方次の文字へ
片方が'x'なら、そうで無い方に'x'を挿入。'x'である方を次の文字へ
両方'x'以外で異なるなら、回文にできない
前からの探索と後ろからの探索がぶつかったら終わり

D - Yet Another Palindrome Partitioning

D: Yet Another Palindrome Partitioning - CODE FESTIVAL 2017 qual C | AtCoder

問題：英小文字からなる文字列sを分割する。分割された各項は、並べ替えると回文が作れるようになっていなくてはならない。最小の分割数を求める。

文字列tを並び替えると回文が作れる＝tに含まれる文字ごとに出現回数をカウントすると、奇数個含まれる文字が0～1個であり、他の文字は全て偶数個である。

文字は英小文字のみという制約があるので、26種類。奇数か偶数かだけ分かればいいので、ビットフラグが使える。'a'=0x001, 'b'=0x010, 'c'=0x100, …とする。

ある文字列sに含まれる文字が奇数個ならビットを立てる。たとえば'aabbccdddef'は、d,e,fが奇数個なので、0x111000で表される。これをsのハッシュと呼ぶことにする。すると、以下に置き換えられる。

文字列tを並び替えると回文が作れる＝tのハッシュで立っているビットの数が0～1個である

（で、ハッシュにするにはしたが、その後がわからず。普通にやるとTLEなので、動的計画法で上手いことやるんだろーなとは思いつつ、時間終了。以降、ほぼ解答の書き写しになってしまうが）

ポイントは、以下の点。

最初からi文字目までの文字列 $s[0,i)$ のハッシュ $a_i$ をあらかじめ計算しておく。
$s[l,r)$ のハッシュ値は、 $a_l \oplus a_r$ で求められる（ $\oplus$ は、bitwise-xor）

これにより、任意の文字列のハッシュが高速に求められる。その上で、問題を以下の部分問題に分割する。

$opt_i$ を、 $s[0, i)$ の最小の分割数とする。 $opt_0=0$ として、i=1から順に計算する。最終的に $opt_N$ が答えとなる。

いま、 $opt_i$ を求めることを考える。 $opt_j \ (1 \le j \lt i)$ は計算済みとする。

$s[0, i)$ を、 $s[k, i)$ が回文を作れるような位置kで $s[0, k)$ と $s[k, i)$ に分けると、暫定的に $opt_i = opt_k + 1$ となる。

具体的に考える。 $s[0, i)=$ 'abcdabcab'とする。たとえば $k=4$ として'abcd' + 'abcab'に分けると、'abcab'は回文を作れる。よって、暫定的に $opt_i ={\rm ('abcd'の最小分割数)}+1$ となる。'abcd'は1文字ずつに分割するしか無いので $opt_k=4$ 。暫定で $opt_i=5$ となる。

最終的な $opt_i$ は、kを $1 \le k \lt i$ の範囲で調べて、その中の最小値となる。

先ほどの例では、 $k=2$ として'ab' + 'cdabcab'と分けても、'cdabcab'が回文を作れる。その方が $opt_i={\rm 'ab'の最小分割数}+1=3$ となり、より適した分割になる。

が、これでは $opt_{1 ... N}$ の計算に $O(N)$ 、その各計算の中で $k=1 ... i$ のループに $O(N)$ 、合計で $O(N^2)$ かかるのでTLE。

次のポイントは、

先頭からの2つの文字列のハッシュ値が同じ（ $a_i=a_j$ ）場合、 $opt_i=opt_j$

2つの文字列のハッシュ値が同じということは、つまりs[i, j)には「各文字がちょうど偶数回ずつ出現する」ということ。回文を作れる文字列の末尾にそのような文字列をくっつけたり（取れるなら）取ったりしても、回文を作れることに変わりない。よって最適な分割数も変わらない。

これで何がいいかというと、kの具体的な値がわからなくても、たとえば「 $a_k$ が0x110010になるようなkの $opt_k$ 」は一意に決まる。

その上で、

調べるのは、 $s[k, i)$ が回文を作れるような $k$ だけでよい
- つまり、 $s[k, i)$ のハッシュ値は、 $\{0, 2^0, 2^1, ..., 2^{25}\}$ のいずれかである
- つまり、 $s[0, k)$ のハッシュ値 $a_k$ は、 $a_i \oplus b$ のいずれかである。ただし $b \in \{0, 2^0, 2^1, ..., 2^{25}\}$

よって、ハッシュ値 $a_k$ をキー、そのハッシュ値を持つ文字列の最小分割数 $opt_k$ を値とした辞書によるDPをおこなう。

調べるのは各 $a_i$ のループにつき27個で済むため、 $O(N)$ となり、間に合う。