第8回日本情報オリンピック 予選3

2008年12月23日
情報オリンピック日本委員会

問題
   連鎖

解説

上から i 番目 (1≦i≦N) のキャラクターを場所 i のキャラクターと呼ぶことにする. 場所の i のキャラクターを単に「場所 i」と呼ぶこともある. 全ての場所 i と全ての色 c (1≦c≦3) に対して, 初期状態において 場所 i の色を c に変更した場合に消滅しないで残るキャラクターの個数をを計算し, そせらの最小値を求めれば良い. そのためには, 場所 i の色を c に変更した場合に消滅するキャラクターの個数 no (i, c) を求める関数を実装すればよい.

no (i, c) を求めるには, まず, 場所 i の色を c に変更することで, 場所 i を含む連続する4つ以上のキャラクターが同じ色かどうかを確認する. 同じ色が4つ以上連続する場合は, それらのキャラクターが消滅することにより新たに連続する4つ以上のキャラクターが同じ色になるのかどうかを確認する, ということを消滅するキャラクター数を数えながら繰り返せば良い.

キャラクターが消滅することにより新たに連続する4つ以上のキャラクターが同じ色になるのかどうかを確認する方法はいろいろ考えられるが, ここでは方針を1つ紹介しておこう. 入力の2行目以降のキャラクターの色を配列に格納しているとする. 下図は, 場所 i の色を c に変更することにより, 場所 p+1 から場所 q-1 までが消滅することが確認され, さらに場所 p および場所 q を含む4つ以上のキャラクターが同じ色になるかどうか確認しようとしている様子を表している. (場所 p+1 の色と場所 q-1 の場所は同じ色 c' で, 場所 p の色は c' と異なるし, 場所 q の色も c' とは異なる.)

消滅するキャラクター数を数える

場所 p と場所 q が異なる色ならこれ以上キャラクターは消滅しない. 場所 p と場所 q が同じ色の場合, 場所 p を含めて p-1 の方向に同じ色のキャラクターが連続している個数 s1 と, 場所 q を含めて p+1 の方向に同じ色のキャラクターが連続している個数 s2 を求め, s1 + s1 が 4 以上であればキャラクターの消滅するので, さらに消滅が続くか調べていけば良い.

最初に場所 i を色 c に変更する際と, 両端の処理は特殊になるので, 実装の際に注意すること.