E - Shorten ABC(AtCoder Regular Contest 110)

解説とは若干違う解法。

A,B,Cからなる長さNの文字列が与えられる。

この文字列に、次の操作を0回以上繰り返して得られる文字列は何通りか。

連続する2文字で、文字が異なっているものを選び、そのどちらとも異なる文字1つに置き換える(すなわち、AB,BA→C、AC,CA→B、BC,CB→Aと置き換える)

Aを1、Bを2、Cを3とする数列と見る。

すると、操作は連続する2要素をxorをとったもので置き換える操作に言い換えられる。

自分の解法では、ここからさらに累積xorをとった。

こうすることで、操作は単純に前の要素の消去に言い換えられるので、部分列の数え上げに帰着できる。ただし、同じ要素が連続するようなものはダメ、かつ一番後ろの要素は消去できないので、「同じ要素が連続しない、最後の要素を含む部分列の総個数」を数えることになる。

サンプル1を例に変換の過程を示す。

ABAAC

→ 1 2 1 1 3（A,B,Cを1,2,3に）

→ 1 3 2 3 0 (累積xorをとる)

この時、例えば部分列「1 3 2 0」は、最後のACに対して操作を行ったと考えると文字列「ABAB」に対応していることがわかる。

また、例えば「1 3 3 0」のような数列は作れない。なぜなら、累積xorをとる前の復元すると「1 2 0 3」となり、0に対応する文字は存在しないからである。(これはAA,BB,CCに対して操作を行ってしまったことに相当する) また、1文字目に0が来ることも有り得ない。

これらの条件を満たしていて、かつ2種類以上の文字が存在すれば全ての部分列に対して上の操作を繰り返して得られる(はずだが、未証明)。一方、最初の時点で文字が1種類ならば答えは1になる。

よって、サンプル1の答えは「10」「20」「30」「120」「130」「230」「320」「1230」「1320」「3230」「13230」に対応する11が答え。

部分列の数え上げは自分は初めてやったがかなり典型らしく、drkenさんの記事

などにまとまっている。

また、JOI2011春合宿のdeciphering - 解読 (Deciphering)がこの問題とほぼ同じ処理になる。

最初、同じ部分列でも位置が違えば別々にカウントできると勘違いしていてかなりタイムロスした。その後もかなりバグった。

hitoare日記