第19回日本情報オリンピック　二次予選

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

解説

まず，JOI 君は以下の順番で作業を行うとしてよい．

• ポスターを回転させる．
• その後，各マス目を塗り替える．

よって，最初にポスターを回転させる量を固定すれば，各マス目を塗り替える作業だけを行う場合を考えればよくなる．

その場合にかかる時間は，元のポスターと新しいポスターで色が異なるマス目の個数と等しいので，これは盤面のサイズに対して線形時間で求めることができる．

以上より，この問題は O(N²) の計算量で解くことができる．