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

2019年7月2日

問題

方針

累積和

'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})\]

となります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N, M;
  cin >> N >> M;
  char c[N][M];
  for (int i = 0; i < N; i++) {
    string s;
    cin >> s;
    for (int j = 0; j < M; j++) {
      c[i][j] = s[j];
    }
  }
  int a[N][3]{};
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
      if (c[i][j] == 'W') a[i][0]++;
      else if (c[i][j] == 'B') a[i][1]++;
      else a[i][2]++;
    }
  }
  int b[N + 1][3]{};
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < 3; j++) {
      b[i + 1][j] += b[i][j] + a[i][j];
    }
  }
  int ans = 10000000;
  for (int i = 1; i < N - 1; i++) {
    for (int j = i + 1; j < N; j++) {
      int v = M * i - b[i][0] + M * (j - i)- (b[j][1] - b[i][1])
            + M * (N - j) - (b[N][2] - b[j][2]);
      ans = min(ans, v);
    }
  }
  cout << ans << "\n";
  return 0;
}