ferinの競プロ帳

競プロについてのメモ

ARC095 E - Symmetric Grid

問題ページ
E - Symmetric Grid

考えたこと

  • 行、列全体をswapするような操作をしてもその行、列に含まれる文字の集合は変わらない
  • 行と列独立に考えたくなる

  • 行を交換する操作について考える

  • ある行を二つ取り出してきたときにその二つの行の組み合わせで点対称になるように出来るか
  • s[i],s[j]に対して(s[i][k],s[j][k]) (0<=k<w) のような組の個数を数える
  • 文字c,dに対して (c,d)の個数 = (d,c)の個数 ならok
  • 例としてs[i]="abcb"、s[j]="cdad"みたいな文字列の組に対して判定をしてみる
  • (a,c)(d,b)(c,a)(b,d)みたいな組ができる
  • (a,c)の個数=(c,a)の個数=1、(b,d)の個数=(d,b)の個数=1 なのでこれはok
  • 注意としてWが奇数だと一つ真ん中に何でもおける場所が存在する
  • 対応を取るのが不可能な行があったら"NO"
  • これで対応させるべき行がわかったので点対称になるような位置に置く
0 aabbzz
1 bbaazz
2 cdefgg
3 efcdgg

みたいなのがきたら(0,1)、(2,3)が対応するので

0 aabbzz
2 cdefgg
3 efcdgg
1 bbaazz

にする。Hが奇数のときに注意

  • 列を交換する操作について考える
  • 点対称にするときに対応させられる2列の組について考える
  • もう行の入れ替えは適切なものになってるので気にしない
  • するとi列目とj列目が対応する条件は i列目 = j列目の反転 になる
  • 行の交換操作と同様に対応させる列がわかる
  • 対応を取るのが不可能な列があったら"NO"
  • Hが奇数の場合1行対応が取れていなくてもいい行があることに注意
  • 行に関しても列に関しても対応が取れたら"YES"

H,Wが奇数のときに注意

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#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 PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

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); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

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

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int h, w;
  cin >> h >> w;
  vector<string> s(h);
  REP(i, h) {
    cin >> s[i];
  }

  VI can(h, -1);
  REP(i, h) {
    if(can[i] != -1) continue;
    FOR(j, i+1, h) {
      if(can[j] != -1) continue;
      // s[i]とs[j]を組み合わせて点対称を作れるか
      vector<pair<char, char>> v(w);
      map<pair<char, char>, int> mp;
      REP(k, w) {
        v[k] = {s[i][k], s[j][k]};
        mp[{s[i][k], s[j][k]}]++;
      }
      bool flag = true, able = w%2==1;
      for(auto k: mp) {
        cout << k << endl;
        pair<char, char> p = k.first;
        if(mp.find({p.second, p.first}) == mp.end()) {
          flag = false;
          break;
        }
        // ok
        if(mp[{p.second, p.first}] == k.second) continue;
        // ng
        if(abs(mp[{p.second, p.first}] - k.second) == 1) {
          if(able) able = false;
          else {
            flag = false;
            break;
          }
        }
        if(abs(mp[{p.second, p.first}] - k.second) > 1) {
          flag = false;
          break;
        }
      }
      if(flag) {
        // s[i]とs[j]がok
        can[i] = j;
        can[j] = i;
        break;
      }
    }
  }
  // cout << can << endl;

  vector<string> t1, t2;
  string center;
  vector<bool> used(h, false);
  bool able = h%2==1;
  REP(i, h) {
    if(used[i]) continue;
    if(can[i] == -1) {
      if(able) {
        able = false;
        continue;
      } else {
        cout << "NO" << endl;
        return 0;
      }
    }
    t1.PB(s[i]);
    used[i] = true;
    t2.PB(s[can[i]]);
    used[can[i]] = true;
  }
  reverse(ALL(t2));
  if(h%2) {
    REP(i, h) if(!used[i]) center = s[i];
  }

  vector<string> t(t1);
  if(h%2) t.PB(center);
  REP(i, t2.size()) t.PB(t2[i]);

  // REP(i, t.size()) cout << t[i] << endl;

  able = w%2 == 1;
  used.assign(w, false);
  REP(i, w) {
    if(used[i]) continue;
    // i列目と対応する列を見つける
    int idx = -1;
    REP(j, w) {
      if(i==j || used[i] || used[j]) continue;
      string tmp1 = "", tmp2 = "";
      REP(k, h) tmp1 += t[k][i], tmp2 += t[k][j];
      reverse(ALL(tmp1));
      if(tmp1 == tmp2) {
        idx = j;
        used[i] = used[j] = true;
        break;
      }
    }
    if(idx == -1) {
      if(able) {
        able = false;
      } else {
        cout << "NO" << endl;
        return 0;
      }
    }
  }

  cout << "YES" << endl;

  return 0;
}