olpheの競プロ帖

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

JOI紋章(13本選1)

H*Wの旗があって各マスにJかOかIの文字が書かれている。

2*2の欲しい文字の並びと、白い布(最大で最大で一度一つの文字を上書きできる)が与えられるので、最大何回理想の並びが登場するかな?という問題。

まず、最初の段階で何個理想の並びが存在するか調べておき、各マスごとにJに変えたとき、Oに変えたとき、Iに変えたときの登場回数の差分を記録して置き、最大値を出力する。

なお、張り替えたときに調べるのは張り替えたマスが左上、右上、左下、右下となる4パターンのみでよいので、O(H*W)となる。

発想は簡単だが実装に苦戦したので、難易度は6程度に感じられた。

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