概要

\(N \times N\) の 0/1 画像に対し、指定された \(K \times K\) の部分領域を時計回りに \(90^\circ\) 回転する操作を \(Q\) 回行い、最終状態を出力します。

考察

回転操作 1 回は、「領域内の各マス \((i,j)\) が回転後にどこへ移るか」を正しく入れ替える処理です。時計回り \(90^\circ\) 回転では、領域内（左上を \((0,0)\) とする）の対応は

• 回転前 \((i, j)\) → 回転後 \((j, K-1-i)\)

となります。

素朴なアプローチの問題点

各操作でこの対応に従って 2 次元配列上で代入していくと、

• 上書きしてしまい値が壊れる（WA の原因）
• Python の通常のリスト/文字列操作だと定数が重く、\(Q\) が最大 \(2 \times 10^5\) のため遅くなりがち（TLE の原因）

という問題があります。

解決方針

この問題は制約に \(Q \times K^2 \le 2 \times 10^7\) があるため、各操作を \(O(K^2)\) で実装すれば合計は十分間に合います。そこで、

1. 回転対象の \(K \times K\) を一旦バッファにコピー（上書き回避）
2. バッファから回転後の形に並べ替えて元の場所へ書き戻す

を高速に行います。さらに Python では bytearray とスライス代入を使うと、0/1 の文字をバイト列としてまとめて扱えて高速です。

アルゴリズム

各クエリ（左上 \((r,c)\)）について次を行います（以下 0-index）：

1. 切り出し（コピー）
   回転領域の各行を grid[r+i][c:c+K] のスライスで取り出し、長さ \(K^2\) の一次元配列 temp に上から順に詰めます（行優先）。

2. 回転（並べ替え）
   回転後の「行 \(b\)」は、回転前の「列 \(b\)」を下から上へ読んだものになります。
   つまり回転後の行 \(b\)（\(0 \le b < K\)）は、temp の

   • インデックス last_base + b から始めて
   • 1 つ前の行へ戻るために K ずつ引きながら

取り出せば作れます。ここで last_base = (K-1)*K は「最下段の先頭」の位置です。
こうして作った各行を buf[b]（長さ \(K\)）に格納します。

1. 書き戻し
   grid[r+i][c:c+K] = buf[i] を \(i=0..K-1\) で行い、領域を置き換えます。

また、\(K=1\) のときは回転しても変化しないので、クエリを読み飛ばしてそのまま出力します（高速化）。

計算量

• 時間計算量: \(O(N^2 + QK^2)\)
  （初期読み込みが \(O(N^2)\)、各操作が切り出し \(O(K^2)\)＋回転 \(O(K^2)\)＋書き戻し \(O(K^2)\) で合計 \(O(K^2)\)）
• 空間計算量: \(O(N^2 + K^2)\)
  （画像本体が \(N^2\)、作業バッファが \(K^2\)）

実装のポイント

• 上書き事故を防ぐため、必ず一旦バッファにコピーしてから回転します。

• Python では list[str] より bytearray＋スライス代入が高速です（行の部分置換が簡単にできる）。

• 回転の実装は、対応 \((i,j)\to(j,K-1-i)\) を素直に二重ループで書いても \(O(K^2)\) ですが、定数を下げるために
  「回転後の行 = 回転前の列を下から上へ」
  という見方で一次元 temp から連続的に取り出しています。

• \(K=1\) は結果が不変なので特別扱いすると無駄な処理を省けます。

  ソースコード

import sys

def main():
    input = sys.stdin.buffer.readline
    N, K, Q = map(int, input().split())
    grid = [bytearray(input().strip()) for _ in range(N)]

    if K == 1:
        for _ in range(Q):
            input()
        sys.stdout.buffer.write(b"\n".join(bytes(row) for row in grid) + b"\n")
        return

    KK = K * K
    K1 = K - 1
    last_base = K1 * K

    temp = bytearray(KK)
    buf = [bytearray(K) for _ in range(K)]

    for _ in range(Q):
        r, c = map(int, input().split())
        r -= 1
        c -= 1

        idx = 0
        rr = r
        cc = c
        for i in range(K):
            temp[idx:idx + K] = grid[rr + i][cc:cc + K]
            idx += K

        for b in range(K):
            dest_row = buf[b]
            p = last_base + b
            for j in range(K):
                dest_row[j] = temp[p]
                p -= K

        for i in range(K):
            grid[rr + i][cc:cc + K] = buf[i]

    sys.stdout.buffer.write(b"\n".join(bytes(row) for row in grid) + b"\n")

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。