AGC031 B - Reversi

解法

まず、1つ性質を確認しておきます。それは「石の色を塗り替える操作について、両端と同じ色を間にも含むような区間に対する操作は考えなくても良い」ということです。具体的には以下の図の上側に示すような操作です。このような操作は下側のように小分けにした操作と同じになるので、小分けにした操作だけを考えて良いです。この性質は後で使います。

f:id:betrue12:20190317011038p:plain

答えの求め方ですが、左からDPをします。以下のようにDPテーブルを定義します。

$dp\lbrack i \rbrack =$ 左端から $i$ 番目までの石だけで考えた時の、色の塗られ方の場合の数

$dp\lbrack i \rbrack$ を求めるための遷移を考えます。 $dp\lbrack i \rbrack$ としてあり得るものとして、まず「 $i-1$ 番目までの塗られ方それぞれについて、単純に最後に $i$ 番目の石を足したもの」があります。この場合の遷移元は $dp\lbrack i-1 \rbrack$ です。

それ以外にあり得るのは「 $i$ 番目を右端とするような操作をして $i-1$ 番目の石の色を変えたもの」で、この場合は先ほど数えたものとは異なる塗られ方が得られます。

最初に確認した性質を振り返ると、このときの操作の左端としては $i$ 番目より左側にある同じ色の石で一番近いものだけを考えればよいです。この一番近い石を $j$ 番目とします。もしここで $j = i-1$ の時（つまりすぐ左隣が同じ色である時）は、操作をしても $i-1$ 番目の石の色が変わらないのでこちらの遷移は考えなくて良いです。