虚無の一日を過ごした。起きたら昼だったし、気付いたら夕方だった。

---

今日解いた競プロの問題。

ABC217-F: なんとか自力AC。一応区間DPと呼ばるるものだろうか。

まず単純に$dp[L][R]:=(区間[L,R]の生徒を全て列から抜く操作方法の数)$として計算していくことを考えてみる。区間$[L,R]$を全て抜きとるには「区間$[L+1,R-1]$が全て抜けてる場合にさらに1ペア抜き取る」場合と「区間$[L,M]$と$[M,R]$に分割してそれぞれで全て抜き取る」という二つの場合があり得る。

1ペア抜き取る方は簡単だ。

• 生徒Lと生徒Rの仲が良い場合は$dp[L][R]$に$dp[L+1][R-1]$を足す

これは良いが、区間$[L,R]$を分割する場合が厄介。

• 全ての$L<M<R$について$dp[L][R]$に$dp[L][M]\times dp[M][R]\times _{(R-L)/2}C_{(M-L)/2}$を足す

これだと重複して数えてしまう。例えば区間A,B,Cと並んでいた場合に、A→B→Cを(A→B)→(C)と(A)→(B→C)と重複して数えてしまう。

そこで、「2つ以上に分割可能な区間」と「分割不可能な区間」の二つに分けて考える。

$dp[L][R][D]:=(区間[L,R]の生徒を全て列から抜く操作方法であって、D=0なら分割不可能/D=1なら分割可能なものの数)$

このようにする。

• 全ての$L<M<R$および$D=0,1$について$dp[L][R][1]$に$dp[L][M][D]\times dp[M][R][0]\times _{(R-L)/2}C_{(M-L)/2}$を足す

こうすれば「分割不可能な区間を1つづつ足し続ける」という形を保つことができ、同じ分割を二度数える心配がなくなる。

区間DPするだけかと思いきや、ちょっと考察が必要な問題だった。単に自分が慣れていないタイプというだけかもしれないが。