[AOJ] No. 0621 ロシアの旗 (Russian Flag)

問題

方針

累積和

‘W’, ‘B’, ‘R’ についてそれぞれ列ごとに累積和を取っていきます。ある列を塗り替えるコストは、\( M \) からその色の個数を引いた値なので、累積和を使って効率よく計算します。\( b_{i, j} \) を 色 \( j \) の \( i \) 行目までの累積和とします。また、\( j = 0\) を ‘W’、\( j = 1\) を ‘B’、\( j = 2\) を ‘R’ とします。

全探索

旗の白い部分の最後の列を \( i \ (1 \leq i \leq N – 2) \) 、青い部分の最後の列を \( j \ ( i < j \leq N – 1) \) とします。このときの色を変えるコストは、

\[Mi – b_{i, 0} + M(j – i) – (b_{j, 1} – b_{i, 1}) + M(N – j) – (b_{N, 2} – b_{j, 2})\]

となります。

コード