AGC 031 B - Reversi

• 問題
• AC

数え上げは明らかに苦手分野なので、改善したい。

与えられた操作をreverseと呼び、ひとまず入力例３に基づいて考える。以下、すべて0-basedとする。

位置	0	1	2	3	4	5	6
色	1	3	1	2	3	3	2

この例でreverseが可能な区間は$[0, 2], [1, 4], [1, 5], [3, 6]$の４種類である。同じ色が連続している部分は$[1, 4]$と$[1, 5]$のように同じ列を生むので、もっとも左にあるものに代表させることにすると、異なるreverseに対応する区間として$[0, 2], [1, 4], [3, 6]$の３種類が残る。一般には

• 異なるreverseが（互いの操作結果を変えない形で）実行可能である $\Leftrightarrow$ reverseを表す区間が重なっていない

が成り立ち、最終的な列は（区間が重ならないような）reverseの組み合わせと一対一に対応している。あとはこれを数え上げればよい。$f(i)$を区間$[0, i]$に操作を行って得られる列の総数とし、$l(i)$を石$i$と同色でひとつ前にある石とする。（前述の通り、連続する同色の石は１つの石とみなし、もっとも左にある石で代表させる。）このとき、漸化式は次のように書ける。

$f(i) = \begin{cases} f(i-1) + f(l(i)-1) + f(l(l(i))-1) + ... & (C_i \neq C_{i-1}) \\ f(i-1) & (C_i = C_{i-1}) \end{cases}$

$f(i-1)$は石$i$をreverseに含めない場合に対応し、$f(l(i)-1)$は、$[l(i), i]$をreverseする場合に対応する。求めたいのは$f(n-1)$である。

しかし、このままDPすると${\mathcal O}(n^2)$なのでTLEする。そこで$f(l(i)) = f(l(i)-1) + f(l(l(i))-1) + ...$に注目すると、結局$f(i) = f(i-1) + f(l(i))$とまとまって${\mathcal O}(n)$で計算できる。

ただ、最後の式が何を意味しているのか、すぐにはわからなかった。区間$[0,i]$から得られる列は、区間$[0,i-1]$から得られる列に$C_i$をくっつけたものか、あるいは区間$[0, l(i)]$から得られる列に$C_iC_i...C_i$（$i-l(i)$個）をくっつけたものとして得られるということか。そう言われればそうだなとなるけど、いきなりこれを思いつくのは厳しい。（しかし、最初にこの発想になる人も普通にいるっぽい。）

参考: https://qiita.com/vain0x/items/9adda58a3fc6d31fff3e