AtCoder Grand Contest 023 B - Find Symmetries

• 問題

B - Find Symmetries

• 解法

2つ目の盤面が良い盤面であるかどうかチェックするには愚直にやるとの計算量時間がかかる。考えられるの個数は個なので全てのに対して2つ目の盤面をチェックする方法ではの計算量時間がかかってTLEになる。
なので盤面チェックの時間を減らすか、考えるの個数を減らすかのどちらかができないか考える。
ここで、あるに対してこのときの2つめの盤面が良い盤面なら、に対する2つ目の盤面も良い盤面であることに気がつく。
すると、考えるはだけでよいことになる。
この方法ならの計算量時間で問題が解けて制限時間に間に合う。

#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <numeric>
#include <cmath>

using namespace std;

typedef long long int ll;

#define all(x) x.begin(),x.end()

const ll mod = 1e9+7;
const ll INF = 1e9;
const ll MAXN = 1e9;

int main()
{
  int n;
  cin >> n;
  vector<string> s(n);
  for(int i = 0; i < n; i++){
    s[i].resize(n);
    for(int j = 0; j < n; j++){
      cin >> s[i][j];
    }
  }

  int ans = 0;

  vector<string> t(n);
  for(int a = 0; a < n; a++){
    bool flag = true;
    for(int i = 0; i < n; i++){
      t[i].resize(n);
    }
    for(int i = 0; i < n; i++){
      for(int j = 0; j < n; j++){
        t[i][j] = s[(i+a)%n][j];
      }
    }
    for(int i = 0; i < n; i++){
      for(int j = 0; j < n; j++){
        if(t[i][j] != t[j][i]) flag = false;
      }
    }

    if(flag) ans += n;
  }

  cout << ans << endl;

  return 0;
}