ARC110-E Shorten ABC 解法メモ

公式解説と若干違う解法だったのでメモしておきます

解法

まず公式解説と同様に A,B,C をそれぞれ 1,2,3 に対応させます。このとき、1 xor 2 = 3、1 xor 3 = 2、2 xor 3 = 1 なので、操作は隣接要素をその xor に置き換える操作と言い換えられます。（ここまでは公式解説と同じです）

次に、累積 xor を取ります。 $A_0 = 0,\ A_i = A_{i-1}\oplus S_{i}\ (1\le i\le N)$ とします。こうすると、操作は以下のように言い換えることができます。

$1\le i\le N-1$ かつ $A_{i-1}\neq A_{i+1}$ であるような $i$ を選び、 $A_i$ を列から消去する。

この結果できる列を数え上げれば良いです。これは、消去しない要素を選ぶ、即ち部分列の数え上げと捉えることができるため、部分列 dp の要領で、以下のような動的計画法で数えられます。

$dp[ i] := 0,\cdots ,i$ 番目の要素まで考えて、最後に $A_i$ を消去せずに残すような部分列の取り方の総数。

ただし、部分列dpと同様に、最終的な列を決めたとき、残す文字は可能な限り先頭のものを選ぶことにします。 $dp[ i]$ からの遷移を考えます。次に取る値を $d = 0,1,2,3$ とし、 $i \lt j$ であって $A_j = d$ であるもののうち、最小の値を $next(d)$ とおきます（そのような $j$ がない場合は遷移しません）。

$d = A_i$ のとき : まず、 $S_i\neq 0$ なので、 $A$ の隣接項は互いに異なります。すると、 $next(d) \gt i+1$ が分かります。このとき、どのような消去手順を取っても最終的に $A_i$ と $d$ に挟まれた値を消去できないことは明らかなので、遷移不能です。
$d\neq A_i$ のとき : 必ず遷移できます。これは、 $i\le k\lt j$ を満たす全ての $k$ に対して、 $A_k\neq d$ であるので、必ず $d$ の手前の値を消去できるためです。

以上より、この dp は $O(N)$ で全て計算できます。

最終的な答えを求めます。明らかに、末尾の値は消去不能なので、残る部分列の末尾の値は $A_N$ であることがわかります。先ほどの部分列 dp のルールから、末尾が $A_N$ である部分列の総数とは、 $A_i = A_N$ であるような全ての $1\le i\le N$ に対する $dp[ i]$ の総和として求まります（ $A_N=0$ のとき、 $A_0=0$ が末尾のパターンを数えないように注意）。