AGC031 B - Reversi

問題
提出コード

解法

まずはじめに、が以降も連続していた場合、その連続している部分の石は必ず同じ色になるので、1つの石に圧縮してしまいます。
この操作を行った、残りの石の列について考えていきます。

次のような操作について考えてみます。
左側が1番、そこから1ずつ増えていって、右端が9番とします。
ここで、一番上の初期状態から、の石に対して操作を行った後、の石に対して操作を行うと、上の図の一番下の列のような結果になります。
さて、この操作を見ると、明らかにに対して行った操作が意味をなしていません。ということで、に対して操作を行うとき、ただし )の操作は無視してもよいことになります。
さて、次のようなDPを考えます。
番目までの石に対する列の種類数
場合分けをしていきます。

• が区間の右端となるような操作を行わない場合
  このように決めた場合、番までに対して操作を行ったときの種類数がそのまま番目までの種類数になります。ので、このパターンについては
  
  を参照すればよいです。

• が区間の右端となるような操作を行う場合
  上の図についてみてきたように、となるを区間の左端として、に対して操作を行うとした場合、この区間内の操作はどのようにしても1通りにしかなりません。
  さて、上の図において、青い石は番目に3つ存在しています。このとき、に対する操作は、に対して操作を行った後、に対しても操作を行うことと等しくなります。
  に対する操作は、にすでに含まれている(の定義が、その場所までの全ての石の色の並び方を網羅していることになっているため)ので、特別な操作を行う必要はなく、結局、が区間の右端となるような操作を行う場合は、
  (ただし、はかつとなる数字のうち最も大きいもの)
  がそのまま新たな種類数となります。
  
  ということで、
  (ただし、はかつとなる数字のうち最も大きいもの)
  という計算を行っていけば、が答えになります。
  は、前計算をするなり、DPの遷移と同時に計算していくことで求められます。
  
  

  感想

  今回はA問題を自力で解けなかったので、こちらだけ解くことができました。問題を読んでからわりとすぐに考察を終えることができたので、なかなか良かったかなと思います。
  思考の過程としては割と解法そのままで、まずは連続した部分が必要ないこと、そして片方の区間がもう片方の区間を完全に含んでいた場合に、小さい方の区間の操作が全く意味をなさないことに気づきます。
  その後、2つの区間でダブりがあるものについても、どちらか片方しか操作ができないことがわかり、あとは、上の青い石のような、3つ以上存在するパターンの処理の仕方について考えました。
  明らかに区間DPが通らないので、この処理をどうするかわかれば、1次元のDPができそうだなと思い、悩んでいると、3つの石のうち、一番遠い2つについての操作は、2つの操作に分けることができるということに気づけたので、あとは遷移を丁寧に求め、この問題が解けました。