結果
問題 |
No.2986 Permutation Puzzle
|
ユーザー |
![]() |
提出日時 | 2025-04-17 15:55:23 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,327 bytes |
コンパイル時間 | 851 ms |
コンパイル使用メモリ | 12,544 KB |
実行使用メモリ | 18,852 KB |
最終ジャッジ日時 | 2025-04-17 15:55:28 |
合計ジャッジ時間 | 4,721 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 3 TLE * 1 |
other | -- * 40 |
ソースコード
# this code was generated by grok 3 beta (x.com) from itertools import product def inverse_permutation(perm): # 順列の逆順列を計算 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, perm): # 行全体を順列に基づいて並び替える(行のインデックスを変更) n = len(matrix) new_matrix = [row[:] for row in matrix] new_rows = [0] * n for i in range(n): new_rows[i] = matrix[perm[i] - 1] for i in range(n): new_matrix[i] = new_rows[i][:] return new_matrix def apply_col_perm(matrix, col_idx, perm): # 列全体を順列に基づいて並び替える(列のインデックスを変更) n = len(matrix) new_matrix = [row[:] for row in matrix] new_cols = [[0] * n for _ in range(n)] for j in range(n): for i in range(n): new_cols[i][j] = matrix[i][perm[j] - 1] for i in range(n): for j in range(n): new_matrix[i][j] = new_cols[i][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": perm = current[pos - 1] current = apply_row_perm(current, pos - 1, perm) else: # op_type == "C" perm = [current[i][pos - 1] for i in range(len(A))] current = apply_col_perm(current, pos - 1, perm) return current 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 = [] for op_type, pos in reversed(ops): # 同じ行/列を逆順列で操作 reverse_ops.append((op_type, pos)) # 逆操作を適用して A に戻るか確認 current = [row[:] for row in B] for op_type, pos in reverse_ops: if op_type == "R": perm = current[pos - 1] inv_perm = inverse_permutation(perm) current = apply_row_perm(current, pos - 1, inv_perm) else: # op_type == "C" perm = [current[i][pos - 1] for i in range(N)] inv_perm = inverse_permutation(perm) current = apply_col_perm(current, pos - 1, inv_perm) if check_equal(current, 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}")