概要

\(N \times N\) ピクセルの画像に対し、指定された \(K \times K\) の正方形領域を時計回りに 90 度回転させる操作を \(Q\) 回行うシミュレーション問題です。

考察

この問題で最も重要なのは制約の読み解きです。 操作回数 \(Q\) は最大 \(2 \times 10^5\) と非常に大きいですが、制約に \(Q \times K^2 \leq 2 \times 10^7\) という記述があります。これは「すべての操作で回転させるピクセルの総数が \(2 \times 10^7\) 以下である」ことを意味しています。

通常、計算量が \(2 \times 10^7\) 程度であれば、愚直なシミュレーションで間に合わせることができます。ただし、Python のようなインタープリタ言語では、単純な二重ループによる更新は低速なため、工夫なしでは制限時間内に終わらない可能性があります。

そこで、Python の組み込み関数やスライス操作など、内部が C 言語で実装されている高速な処理を組み合わせて実装する必要があります。

アルゴリズム

以下の手順でシミュレーションを行います。

1. 初期状態の保持: 画像を文字の 2 次元リスト grid として読み込みます。各行をリストにすることで、部分的な書き換えを可能にします。

2. 回転操作の実行 (\(Q\) 回): 各操作 \((R_j, C_j)\) に対して以下を行います。

   • 切り出し: grid から \(K \times K\) の部分領域を抽出します。
   • 回転: 抽出した領域を時計回りに 90 度回転させます。
     • Python では zip(*subgrid[::-1]) というイディオムを使うことで、2 次元リストの 90 度回転を高速に行えます。
   • 書き戻し: 回転後のデータを元の grid の位置に上書きします。
     • リストのスライス機能（grid[i][c : c + K] = new_row）を使うことで、1 行ずつまとめて高速に更新できます。

3. 最終状態の出力: すべての操作が終わった後、grid を連結して出力します。

計算量

• 時間計算量: \(O(N^2 + Q \cdot K^2)\)
  • 初期の読み込みと最後の出力に \(O(N^2)\) かかります。
  • 各操作において \(K \times K\) 個の要素を処理するため、全体で \(O(Q \cdot K^2)\) となります。制約よりこれは \(2 \times 10^7\) 程度であり、高速な実装であれば十分に間に合います。
• 空間計算量: \(O(N^2 + K^2)\)
  • 画像を保持する領域 \(O(N^2)\) と、回転時に一時的に使用する領域 \(O(K^2)\) が必要です。

実装のポイント

• 高速な入出力: sys.stdin.read().split() を使って一括で入力を取得し、sys.stdout.write で出力することで、入出力のボトルネックを解消しています。

• 2次元リストの回転: zip(*subgrid[::-1]) は、まず行を上下反転させ（[::-1]）、それをアンパック（*）して zip で各列の要素をまとめることで、結果的に時計回り 90 度の回転を実現するテクニックです。

• スライス代入: grid[i][c : c + K] = rotated_row のようにスライスに対してリストを代入することで、ループを回して 1 要素ずつ代入するよりも遥かに高速に動作します。

• 1-indexed への対応: 問題文の座標は \((1, 1)\) から始まるため、プログラム内では \(0\) から始まるインデックスに補正（\(-1\)）して扱います。

  ソースコード

import sys

# The problem asks for an efficient simulation of Q clockwise 90-degree rotations
# of a KxK subgrid within an NxN image. The key constraint is Q * K^2 <= 2 * 10^7,
# which suggests that an O(Q * K^2) simulation is acceptable if implemented efficiently.
# In Python, we can achieve high performance by using built-in operations like
# list slicing, zip, and slice assignment.

def solve():
    # Read all input at once and split into a list of strings for faster processing.
    # This approach is generally more efficient than multiple calls to input() or sys.stdin.readline().
    data = sys.stdin.read().split()
    if not data:
        return
    
    # N: image size, K: rotation square size, Q: number of operations.
    N = int(data[0])
    K = int(data[1])
    Q = int(data[2])
    
    # grid: N x N image represented as a list of lists of characters ('0' or '1').
    # We use lists of characters because they are mutable and allow for efficient slice assignment.
    # The grid data starts from data[3] to data[N+2].
    grid = [list(data[i]) for i in range(3, N + 3)]
    
    # If K is 1, a 1x1 rotation has no effect on the image, so we can skip the simulation.
    if K > 1:
        # Operations start from data[N+3] and each operation consists of two integers (R and C).
        # We use an iterator to traverse the operations efficiently.
        it = iter(data[N + 3:])
        for _ in range(Q):
            try:
                # Top-left coordinates of the K x K square (converted to 0-indexed).
                r = int(next(it)) - 1
                c = int(next(it)) - 1
            except StopIteration:
                break
            
            # Extract the K x K subgrid to be rotated.
            # grid_view is a list of references to the K rows involved in the operation.
            grid_view = grid[r : r + K]
            # subgrid is a new list of K lists, where each list is a copy of a K-length segment.
            # Slicing is highly optimized in Python.
            subgrid = [row[c : c + K] for row in grid_view]
            
            # Rotate the subgrid 90 degrees clockwise.
            # The idiom zip(*subgrid[::-1]) is a standard and efficient way to rotate 2D lists in Python.
            # 1. subgrid[::-1] reverses the order of the rows.
            # 2. * unpacks these rows as separate arguments to the zip function.
            # 3. zip() takes the i-th element from each argument to form the i-th tuple (new row).
            # This results in a clockwise 90-degree rotation.
            rotated = zip(*subgrid[::-1])
            
            # Put the rotated rows back into the original grid.
            # Slice assignment (grid_view[i][c:c+K] = rotated_row) is very fast as it's implemented in C.
            # Since grid_view contains references to the actual rows in the grid, this updates the image.
            for i, rotated_row in enumerate(rotated):
                grid_view[i][c : c + K] = rotated_row

    # Final output: join characters into strings and strings into the final output.
    # sys.stdout.write is faster than calling print() multiple times.
    sys.stdout.write("\n".join("".join(row) for row in grid) + "\n")

if __name__ == "__main__":
    solve()

この解説は gemini-3-flash-thinking によって生成されました。