three-point leader

この解説でも、…を#と表記します。

まず、次のようなDPをすることを考えます。

・ $DP[i][j][k]:=$ $i$ 番目の.までを見て、.を $j$ 個ストック(部分列を取る時に消えていないこと)していて、現在ストックしている.を全て取り払ったときに最も右の#の区間の長さが $k$ であるような、操作と取った部分列の組の個数

まず、このDPは $k>2$ の場合を考える必要はありません。

このDPの遷移を列挙していきます。

・ 今見ている.をストックする場合 $DP[i+1][j+1][k]+=DP[i][j][k]$

・ 今見ている.をストックせず、ストックがある場合 $DP[i+1][0][k]+=DP[i][j][k]$ ただし、$j>2,k\neq 1$ (今ストックしている.を消すことができず、#が孤立してしまうため)

・ 今見ている.をストックせず、ストックがない場合 $DP[i+1][0][0]+=DP[i][2][k]$

・ 今見ている.とストックしている.を使って#を作り、ストックが完全に消え、その#を部分列を取る時に消す場合 $DP[i+1][0][k]+=DP[i][2][k]$

・ 今見ている.とストックしている.を使って#を作り、ストックが残り、その#を部分列を取る時に消す場合 $DP[i+1][0][0]+=DP[i][j][k]$ ただし、$j>2,k\neq 1$

・ 今見ている.とストックしている.を使って#を作り、ストックが残り、その#を部分列を取る時に消さない場合 $DP[i+1][0][1]+=DP[i][j][k]$ ただし、$j>2,k\neq 1$

・ 今見ている.とストックしている.を使って#を作り、ストックが完全に消え、その#を部分列を取る時に消さない場合 $DP[i+1][0][k+1]+=DP[i][2][k]$

ここで、$j>2$になった場合、どのような遷移をしてもストックが残る遷移に関わってから $j=0$ になるため、この状態をまとめることができます。そのため、それぞれの $i$ ごとに状態数を $4×3=12$ に抑えることができます。これを行列累乗で計算することで、計算量が$Ο(\log N)$となり、ACすることができました。