2019年3月18日月曜日

AGC 031 B - Reversi

AGC 031 B - Reversi

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

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

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

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

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

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

f(i)={f(i1)+f(l(i)1)+f(l(l(i))1)+...(CiCi1)f(i1)(Ci=Ci1) 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(i1)f(i-1)は石iiをreversiに含めない場合に対応し、f(l(i)1)f(l(i)-1)は、[l(i),i][l(i), i]をreversiする場合に対応する。求めたいのはf(n1)f(n-1)である。

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

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

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