注意：この解法は、もしかすると出題当時は有効ではないかもしれません。

愚直解法は各回転を \(\text{worst}\) \(\Theta(N^2)\) 回の代入操作、より具体的には \(\frac{5}{4}N^2\) 回でシミュレートします。各実行で必要な代入操作は \(2000\times\frac{5}{4}\times 1000^2=2.5 \times 10^9\) 回です。

この解法を改善するための課題点が \(2\) つあります。

• \(1\) つは \(2.5 \times 10^9\) がいくらなんでも大きすぎることです。このままでは複雑な操作はできません。

• 非常に多い回数のランダムアクセスが必要だということです。というのは、 \(1\) つの行のマスの移動先が多数の行に分散し、このままでは連続したメモリアクセスができません。

各マスに書かれる情報が \(26\) 種類しかないことに注目します。ビット列として \(64\) ビットにパッキングすると、 \(12\) マス分の情報を含められます。これを \(1\) 列分として、 \(12 \times 12\) の領域を高速に回転できたとすれば、上記 \(2\) つの課題点を踏まえても有効そうです。

ここで次の実装が必要になります。

• 入力を \(1 \times 12\) マスごとに、 \(64\) ビット整数に入れる
• 現在のグリッドから任意の \(12 \times 12\) の領域を切り出して バッファ へ保存する。
• \((\ast)\) バッファ にある \(12 \times 12\) を高速に回転する
• 任意の \(12 \times 12\) の領域を バッファ の内容で上書きする
• 角から順に \(12\times 12\) の領域を切り出すと中央の十字部分が残るが、その部分を愚直に回転する
• グリッドを復元して出力する。

\((\ast)\) 以外は特別難しくありません。以下、 \((\ast)\) の方法を説明します。

\(ab \times ab\) の回転は、 \(a \times a\) の小さい回転と、 \(b \times b\) の大きい回転に分割できます。

\[ \left\lbrack \begin{array}{cc|cc} 00 & 01 & 02 &03 \cr 10 & 11 & 12 & 13 \cr \hline 20 & 21 & 22 & 23 \cr 30 & 31 & 32 & 33 \end{array} \right\rbrack \overset{\text{小}}{\rightarrow} \left\lbrack \begin{array}{cc|cc} 01 & 11 & 03 &13 \cr 00 & 10 & 02 & 12 \cr \hline 21 & 31 & 23 & 33 \cr 20 & 30 & 22 & 32 \end{array} \right\rbrack \overset{\text{大}}{\rightarrow} \left\lbrack \begin{array}{cc|cc} 03 &13 & 23 & 33 \cr 02 & 12 & 22 & 32 \cr \hline 01 & 11 & 21 & 31 \cr 00 & 10 & 20 & 30 \end{array} \right\rbrack \]

\(12=2\times 2\times 3\) ですから、必要な回転は \(3\) 段階に分解できます。各段階は、ビットシフトでまとめて動かすことで演算回数を愚直より減らせます。こうしてできたものを愚直同様、ただし \(12\times 12\) をまとめて移動先に動かします。

以上より、愚直な実装から高速化が見込める方法ができました。

以上の方法で実装したものがこの提出(#29938675)です。満点を取れます。