B: Find Symmetries | AtCoder Grand Contest 023
よい盤面である条件は、1<=i<=Nについてi行目とi列目が等しいことと同値。例えばN=4については、以下が等しければよい。 更にこの図から、任意の自然数の組(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;
思いつき方?
計算量多すぎ=>どこをまとめて計算する?=>盤面を分類