olpheの競プロ帖

競プロ問やアルゴリズム等の考察します

連鎖(09予選3)

N匹のキャラクターが縦一列に並んでいる。

(1<=N<=10000)

同じ色のキャラクターが4匹以上隣接すると彼らは消滅する。

また、初期段階で消滅する条件を満たしていることはない。

一度だけ、任意のキャラクターの色を好きなように変えることができるのだが、一番多くのキャラクターを消すと、どれだけキャラクターは残るかな、といった問題。

(色は3種類)

 

全ての色の変え方を試せばよいだけなのだが、実装がめちゃくちゃつらい。

私は、消えた範囲をもって、その上下で色の比較をした。

オーダーの話をすればO(N^2)なので通る。(当時だと怪しいけど定数はめちゃくちゃ小さいので問題ないかと思われる)

 

特殊な知識などは必要ないが、発想や高い実装力が求められるので難易度は7程度に感じられた。

 

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2243195#1