結果

問題 No.2986 Permutation Puzzle
ユーザー ID 21712
提出日時 2025-04-17 15:57:12
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 3,363 bytes
コンパイル時間 293 ms
コンパイル使用メモリ 12,288 KB
実行使用メモリ 18,852 KB
最終ジャッジ日時 2025-04-17 15:57:16
合計ジャッジ時間 4,182 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3 TLE * 1
other -- * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

# this code was generated by grok 3 beta (x.com)

from itertools import product

def inverse_permutation(perm):
    # 順列の逆順列を計算（1-based）
    n = len(perm)
    inv = [0] * n
    for i in range(n):
        inv[perm[i] - 1] = i + 1
    return inv

def apply_row_perm(matrix, row_idx):
    # 行 row_idx の順列に基づいて行を並び替える
    n = len(matrix)
    perm = matrix[row_idx]  # 行 row_idx の順列
    new_matrix = [None] * n
    for i in range(n):
        new_matrix[i] = matrix[perm[i] - 1][:]  # 行 perm[i] を i 番目に
    return new_matrix

def apply_col_perm(matrix, col_idx):
    # 列 col_idx の順列に基づいて列を並び替える
    n = len(matrix)
    perm = [matrix[i][col_idx] for i in range(n)]  # 列 col_idx の順列
    new_matrix = [[0] * n for _ in range(n)]
    for j in range(n):
        for i in range(n):
            new_matrix[i][j] = matrix[i][perm[j] - 1]  # 列 perm[j] を j 番目に
    return new_matrix

def check_equal(matrix1, matrix2):
    # 2つの行列が等しいか確認
    return all(row1 == row2 for row1, row2 in zip(matrix1, matrix2))

def simulate_operations(A, operations):
    # 操作を適用して結果の行列を返す
    current = [row[:] for row in A]
    for op_type, pos in operations:
        if op_type == "R":
            current = apply_row_perm(current, pos - 1)
        else:  # op_type == "C"
            current = apply_col_perm(current, pos - 1)
    return current

def get_reverse_operations(operations, A, B):
    # 操作列の逆操作を生成
    reverse_ops = []
    current = [row[:] for row in B]
    for op_type, pos in reversed(operations):
        if op_type == "R":
            perm = current[pos - 1]  # 現在の行 pos-1 の順列
            inv_perm = inverse_permutation(perm)
            # 逆順列で並び替える（ただし、行の並び替えは現在の順列を使う）
            current = apply_row_perm(current, pos - 1)
            reverse_ops.append((op_type, pos))
        else:  # op_type == "C"
            perm = [current[i][pos - 1] for i in range(len(A))]
            inv_perm = inverse_permutation(perm)
            current = apply_col_perm(current, pos - 1)
            reverse_ops.append((op_type, pos))
    return reverse_ops

def solve(N, K, A, B):
    # すべての可能な K 回の操作を列挙
    choices = [(t, p) for t in ["R", "C"] for p in range(1, N + 1)]
    for ops in product(choices, repeat=K):
        # A に操作を適用して B になるかチェック
        simulated_B = simulate_operations(A, ops)
        if check_equal(simulated_B, B):
            # B になった場合、逆操作を生成
            reverse_ops = get_reverse_operations(ops, A, B)
            # 逆操作が A に戻すか確認（デバッグ用、理論的には不要）
            simulated_A = simulate_operations(B, reverse_ops)
            if check_equal(simulated_A, A):
                return reverse_ops
    return []  # 解が見つからない場合（問題保証により発生しない）

# 入力処理
N, K = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]
B = [list(map(int, input().split())) for _ in range(N)]

# 解を求める
ops = solve(N, K, A, B)

# 出力
print(len(ops))
for op_type, pos in ops:
    print(f"{op_type} {pos}")
0