概要

\(N \times N\) の画像に対して、指定された \(K \times K\) の正方形領域を時計回りに90度回転させる操作を \(Q\) 回行い、最終的な画像の状態を求める問題です。

考察

問題の理解

まず、「時計回りに90度回転」とは何かを具体例で確認しましょう。

\(3 \times 3\) の領域を考えます：

回転前:        回転後:
1 2 3          7 4 1
4 5 6    →    8 5 2
7 8 9          9 6 3

左端の列（1, 4, 7）が上端の行（7, 4, 1）になり、真ん中の列が真ん中の行に、右端の列が下端の行になります。

座標変換の導出

回転前の座標 \((i, j)\) にある要素が、回転後にどこへ移動するかを考えます。

• 回転前: \((i, j)\) の要素
• 回転後: \((j, K-1-i)\) の位置へ移動

逆に言えば、回転後の位置 \((i, j)\) には、回転前の \((K-1-j, i)\) の要素が来ます。

計算量の確認

この問題では、制約に \(Q \times K^2 \leq 2 \times 10^7\) が与えられています。これは「すべての回転操作で扱うピクセルの総数」の上限を示しています。

素朴に各操作で \(K \times K\) 個のピクセルを処理しても、全体で \(O(Q \times K^2) = O(2 \times 10^7)\) となり、十分間に合います。

アルゴリズム

1. 画像の読み込み: \(N \times N\) の画像を2次元リストとして保持する

2. 回転操作の実装: 各操作について以下を行う

   • 回転する \(K \times K\) 領域を一時的な配列にコピーする
   • 座標変換の式を使って、回転後の位置に書き戻す

3. 結果の出力: 最終状態の画像を出力する

回転の実装詳細

左上が \((r, c)\) の \(K \times K\) 領域を回転させるとき：

回転後の (r+i, c+j) = 回転前の (r+K-1-j, c+i)

これは領域内のローカル座標で考えると： - ローカル座標 \((i, j)\) には、回転前のローカル座標 \((K-1-j, i)\) の値が来る

計算量

• 時間計算量: \(O(N^2 + Q \times K^2)\)

  • 画像の読み込みに \(O(N^2)\)
  • 各回転操作で \(K^2\) 個のピクセルを処理し、これを \(Q\) 回行うので \(O(Q \times K^2)\)
  • 制約より \(Q \times K^2 \leq 2 \times 10^7\) なので十分高速

• 空間計算量: \(O(N^2 + K^2)\)

  • 画像の保持に \(O(N^2)\)
  • 回転時の一時領域に \(O(K^2)\)

実装のポイント

1. 0-indexed への変換: 問題文では座標が1始まりですが、プログラム内では0始まりで扱う方が便利です。入力された座標 \((R, C)\) を \((R-1, C-1)\) に変換します。

2. 一時配列へのコピー: 回転操作では、元の領域を読みながら同じ領域に書き込むと、まだ読んでいない値が上書きされてしまいます。そのため、まず領域全体を一時配列にコピーしてから書き戻します。

3. 座標変換式の正確な実装: 時計回り90度回転の式は間違えやすいので、小さな例で手計算して確認するとよいでしょう。

   ソースコード

import sys

def rotate_region(grid, r, c, k):
    """K×K領域を時計回りに90度回転させる"""
    # 回転前の領域を取得
    region = []
    for i in range(k):
        row = []
        for j in range(k):
            row.append(grid[r + i][c + j])
        region.append(row)
    
    # 時計回りに90度回転させて書き戻す
    # 回転後: new[j][k-1-i] = old[i][j]
    # つまり: new[i][j] = old[k-1-j][i]
    for i in range(k):
        for j in range(k):
            grid[r + i][c + j] = region[k - 1 - j][i]

def main():
    input_data = sys.stdin.read().split('\n')
    idx = 0
    
    n, k, q = map(int, input_data[idx].split())
    idx += 1
    
    # 画像を2次元リストとして読み込む
    grid = []
    for i in range(n):
        grid.append(list(input_data[idx]))
        idx += 1
    
    # Q回の操作を実行
    for _ in range(q):
        r, c = map(int, input_data[idx].split())
        idx += 1
        # 0-indexedに変換
        rotate_region(grid, r - 1, c - 1, k)
    
    # 結果を出力
    for row in grid:
        print(''.join(row))

if __name__ == "__main__":
    main()

---

この解説は claude4.5opus によって生成されました。