ferinの競プロ帳

競プロについてのメモ

SRM631 div1 easy TaroJiroGrid

概要

各マスが黒か白に塗られているn*nの二次元グリッドが与えられる。同じ色がN/2マスより長く連続している列が存在する時、そのグリッドはだめなグリッドである。操作を繰り返すことでだめなグリッドを解消したい。このとき最小の操作回数を求めろ。なお、1回の操作では以下のいずれかを行う。

  • 行を一つ選び黒いマスを全て白に塗る
  • 行を一つ選び白いマスを全て黒に塗る

解法

各操作はある行を全て黒いマスで塗るか白いマスで塗ることと等しい。
N/2マス以上同じ色が存在しないようにするには中央の2行を黒と白でそれぞれ塗ればいいので操作回数は2以下で抑えられる。したがって、操作回数0または1で条件を満たすものがあるか全て試せばよい。愚直に計算してもO(N^4)なので解ける。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = (1LL<<60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
//#define int ll

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

class TaroJiroGrid {
   public:
   int getNumber(vector <string> g)
  {
    vector<string> s = g;
    int n = g.size();
    int ret = 2;

    REP(i, 2*n+1) {
      g = s;
      int cnt = 0;
      if(i != 0) {
        if(i <= n) g[i-1] = string(n, 'W');
        else g[i-n-1] = string(n, 'B');
        cnt++;
      }

      int ma = 0, con = 1;
      REP(x, n) {
        con = 1;
        FOR(y, 1, n) {
          if(g[y][x] == g[y-1][x]) {
            con++;
          } else {
            ma = max(ma, con);
            con = 1;
          }
        }
        ma = max(ma, con);
      }
      if(ma <= n/2) {
        chmin(ret, cnt);
      }
    }

    return ret;
  }
};