J - 回転と反転/Rotate and Reverse Editorial by blackyuki


愚直に回転・反転をしていては実行時間超過してしまうので、効率の良い解法が必要です。

そこで、実際に盤面を回転・反転させるのではなく回転・反転の回数のみを数えることにします。盤面の回転の状態は全部で \(8\) 通りあり、現在どの状態かを管理しておくと、現在のマスが最初どの位置にあったかを計算することが可能です。

マスを塗り換える時には現在の位置ではなくそれに対応する最初の位置を塗り換えます。

全体の計算量は \(O(N^2+Q)\) です。

posted:
last update: