B: Find Symmetries | AtCoder Grand Contest 023

よい盤面である条件は、1<=i<=Nについてi行目とi列目が等しいことと同値。例えばN=4については、以下が等しければよい。 f:id:parukii:20180501134418j:plain 更にこの図から、任意の自然数の組(A, B)について(A+x, B+x) (xは自然数) も(A,B)と比較対象が同じであることがわかる。たとえば、(A, B) => (A+1, B+1)において比較する行と列がすべて右下にずれる(ただし下端、右端は循環)。よって、各A-B=Cについて(C, 1) をチェックする。この可否は(C, x) (1<=C<=N)と等しいのでN回だけチェックすればいい。1回のチェックはO(N2)かかり、全体でO(N3)の時間で間に合う。

公式解説の実装

int N, re = 0;
cin >> N;
vector<string> S(N);
rep(a, N)cin >> S[a];
rep(a, N) {
    re += [&] {
        rep(x, N)rep(y, N)
            if (S[(x + a) % N][y] != S[(y + a) % N][x])RT 0;
        RT N;
    }();
}
cout << re << endl;

思いつき方?

計算量多すぎ=>どこをまとめて計算する?=>盤面を分類

だめな別解(ローリングハッシュ)