AtCoder GC023 B: Find Symmetries

問題

https://agc023.contest.atcoder.jp/tasks/agc023_b

解法

まず、初期状態で「よい盤面」なものについて考える。

例えば、N=3の場合、以下のような盤面が「よい盤面」である。

a b c
b d e
c e f

これを右方向に1、下方向に1ずらすと

f c e
c a b
e b d

となり、これも「よい盤面」となる。さらに右方向に1、下方向に1ずらしても同じである。

つまり、「よい盤面」を横方向と縦方向に同じだけずらしたものは同様に「よい盤面」となる。

よって、整数A、Bの組み合わせのうち、Bを0に固定し、Aのみ0〜N-1に変えて「よい盤面」になる数を数えて、その結果をN倍すれば解となる。

計算量は「よい状態」かどうかのチェックにO(N²)かかるため、全体ではO(N³)となるが、Nは最大300なので一応間に合う。

実装

n = gets.chomp.to_i
s = []
n.times do
    s << gets.chomp
end

st = s.transpose

ans = 0
n.times do
    ans += 1 if s == st
    n.times {|i| st[i].rotate!}
    s.rotate!
end
ans *= n

puts ans