第一回日本最強プログラマー学生選手権予選 C - Cell Inversion

• 問題
• AC

区間の組み合わせの総数が求まれば、操作の順番の総数は$N!$を掛けて得られるので、前者を求めればよい。

$S$を左から走査して、閉じていない区間を保持しながらDPすることを考える。つまり、

$\operatorname{dp}[x][y] := x$文字目までみて、閉じていない区間が$y$個あるような場合の数

というDPをする。$x$文字目が$W$で$y$が偶数、もしくは$x$文字目が$B$で$y$が奇数なら、ここで$y$個の（閉じていない）区間のどれかを閉じるのが正しいので、

$$\operatorname{dp}[x+1][y-1] \operatorname{+=} y \cdot \operatorname{dp}[x][y]$$

$x$文字目が$B$で$y$が偶数、もしくは$x$文字目が$W$で$y$が奇数なら、さらに新しい区間を開始して反転を1増やすべきなので

$$\operatorname{dp}[x+1][y+1] \operatorname{+=} \operatorname{dp}[x][y]$$

このDPは${O}(N^2)$の形になっているが、実際にやってみると各$x$について有効な$y$は高々1つしかないことがわかるので、線形で書ける。

---

コンテスト当時にはまったくわからなくて、解説を読んでも天才解法に見えた問題だった。今見ると、いわゆる箱根駅伝DPを書けばアドホックな考察をしなくても解けてしまうことがわかる。

ただ、${O}(N^2)$のDPが見えているときに、それの延長として想定解が導ける場合とかなり難しい場合があって、コンテスト中にそちらにどこまで頭を使うかは微妙なところとは思う。今出ても、ムーブ次第ではまりかねない気がする。