次のように言葉を定義しておく。

• 黒マスからなる区間のうち、極大な区間を黒の連結成分と呼ぶ
• 白マスからなる区間のうち、極大な区間を白の連結成分と呼ぶ
• コマが置かれた区間のうち、極大な区間をコマの連結成分と呼ぶ

解法

最終的なコマの配置としてあり得る必要十分条件

最終的なコマの配置としてあり得る必要十分条件は、(A)or(B)である。

(A)

次のように名前をつける。

• a1: 3つ並んだ白マスの真ん中のマス
• a2: 黒の連結成分
• a3: 黒マス

各コマの連結成分に次の手順で丸をつけていくとき、すべてのコマの連結成分に丸をつける方法が存在する

1. a1を含むコマの連結成分を \(1\) つ選び、丸をつけても良い
2. a2を含むコマの連結成分を好きなだけ選び、丸をつけて良い
3. a3を含むコマの連結成分を \(1\) つ選び、丸をつけても良い

(B)

(A)の白と黒を入れ替えた条件

dp

(A)の条件に加えて、コマを置かないといけない場所の条件の両方を満たすようなコマの配置を考える。この条件を満たしている状態のみを管理すると、置くコマの数の最小値をdpで求めることができる。具体的には、次のものを添え字に持って、(A)の条件を満たしているかチェックしながら、置いたコマの数の最小値を管理すればよい。

• 何マス目までコマを置くかどうか決めたか
• 1で丸つけ済フラグ
• 3で丸つけ済フラグ
• \(i\) マス目にコマを置くかフラグ
  • （\(i\) マス目にコマを置く場合）このコマの連結成分がa1を含んでいるかフラグ
  • （\(i\) マス目にコマを置く場合）このコマの連結成分がa2の左端を含んでいるかフラグ
  • （\(i\) マス目にコマを置く場合）このコマの連結成分がa2を含んでいるかフラグ
  • （\(i\) マス目にコマを置く場合）このコマの連結成分がa3を含んでいるかフラグ

同様に(B)の条件をチェックしながらdpをすることができる。 両方の dp で答えのうち最小が答えである。

正当性

条件を満たす盤面であれば、作れる

次のようにすれば置ける。

1. a1 にコマを置く。
2. a2 にコマを置く。各連結成分ごとに置いていく。
3. a3にコマを置く。
4. 全部においたら、各コマの連結成分を適当に広げていく。

条件を満たす盤面だけを考えれば十分

まず、コマの連結成分数を減らす操作はする必要が無いことがわかる。「マス \(l\) から \(i-1\) までのコマの連結成分と、マス \(i+1\) からマス \(r\) までのコマの連結成分があるときに、マス \(i\) にコマを置く」という操作をしなくても良いことが示せる。これは、マス \(l\) から \(i-1\) までのコマの連結成分を作った後、\(i,i+1,\dots,r\) と順番にコマを置いていけば良いためである。

最終的なコマの連結成分それぞれについて石を \(1\) つ以上置いてしまえば、そのあと各連結成分を広げていくのはかんたんなので、最初の連結成分を増やすパートにのみ注目する。

コマを一個ずつ置いていく途中に、各コマの連結成分が

• a 白のみに隣接
• b 黒のみに隣接
• c 両方に隣接

の \(3\) パターンのどれに当てはまるかに注目する。 コマの連結成分数を増やすためには既存のコマの連結成分がすべてaかすべてbである必要がある。

コマの連結成分を増やすタイミングでaであるかbであるかは、コロコロ変えなくていいことが証明できる。つまり、最初にaかbかを選んで、連結成分を増やすタイミングで必ず選んだ方の状態になっているような置き方だけを考えても、最適な置き方が実現できる。

これを示す。ある連結成分があるタイミングですべてのコマの連結成分が a であったのに、今すべて b であるとして、a の状態を経由せずに同じコマの置き方ができることを示せばよい。これは、各連結成分について。次の \(2\) 通りの場合しかない。

• 「あるタイミング」で a1 だったコマの連結成分
  • そのようなコマの連結成分にコマを加えて黒マスのみに隣接するようにする場合、必ず a1 を含む白の連結成分全てにコマを置く必要がある
• 「あるタイミング」で黒の連結成分に置かれていたコマの連結成分
  • そのようなコマの連結成分にコマを加えて黒マスのみに隣接するようにする場合、左隣の白の連結成分と、右隣の白の連結成分の両方にコマを置く必要がある。かわりにこのどちらかに置けば良い

そうなると、(A)か(B)しかないことがわかる。

C++による実装