AtCoder Grand Contest 031：B - Reversi
問題
解法
dp(i) := i 個目の石までの塗り方の数
とする．このとき，i 個目の石と同じ色の石が j (j < i) 個目にあるとき，[j, i] の区間を i 個目の石の色で塗ることが可能．塗るときの塗り方の数は考えられる j について dp(j - 1) を足したものになる．よって，dp(i) は dp(i - 1) と dp(j - 1) (j < i で C_i = C_j を満たす全ての j) の和になる．このままだと O(N^2) かかってしまうが，後者の和を C_i ごとにメモしておくことで O(1) で遷移できるようになる．これで全体で O(N) になり解ける．
解答
コンテスト中は全体を見て答えを一発で求めようとしてしまっていた．こういう問題で DP は生きてくると思った．
