問題一覧 > 通常問題

No.2986 Permutation Puzzle

レベル : / AI推定難易度 : 1150 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : （AC するまで非表示） / 解いたユーザー数 19
作問者 : ID 21712
お気に入りにしたユーザー ProblemId : 11672 / 自分の提出
問題文最終更新日: 2024-12-13 13:37:01
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2024 (順位表) の他の問題:
2024-12-13 Update 1: Added the wording "click to open"
2024-12-13 Update 2: Raised the level from ★2 to ★2.5

Problem Statement

There is a matrix $A$ with $N$ rows and $N$ columns in which each column and each row is a permutation of $1$$\dots$$N$. 

$N=4の一例$
$4\ 1\ 3\ 2$
$2\ 4\ 1\ 3$
$3\ 2\ 4\ 1$
$1\ 3\ 2\ 4$
Matrix $B$ is generated by performing, $K$ times on this matrix $A$, the action of choosing and executing one of the following operations.
  • Choose $1$ column, and rearrange the positions of the columns of the matrix according to the numbers of the permutation in that column.
  • Choose $1$ row, and rearrange the positions of the rows of the matrix according to the numbers of the permutation in that row.
Pseudocode of the rearrangement (click to open) 
# A, B, S, T ... 行列
# .At(i, j) ... 行列の i 行目 j 列目の値を参照したり、値を代入したり
# P <- Q ... 右辺 Q から左辺 P への値・行列のコピー

# 行列 S の X 列目を選択して列の位置を並び替える
function reorder_cols_by_col_perm(S, X)
    T <- S
    for r in range(1...N)
        for c in range(1...N)
            S.At(r, T.At(c, X)) <- T.At(r, c)
    return S

# 行列 S の Y 行目を選択して行の位置を並び替える
function reorder_rows_by_row_perm(S, Y)
    T <- S
    for r in range(1...N)
        for c in range(1...N)
            S.At(T.At(Y, r), c) <- T.At(r, c)
    return S

# 行列 A から K 回操作して行列 B にする処理(テストケース生成)のイメージ
    S <- A
    for _ in range(1...K)
        e <- random_one(1...2N)
        if e <= N
            X <- e
            S <- reorder_cols_by_col_perm(S, X)
        else
            Y <- (e - N)
            S <- reorder_rows_by_row_perm(S, Y)
    B <- S


$操作の例:\ N=4,K=3$
        
$1回目の操作:\ 3列目を選び列を並び替える$
$3列目の順列\ \dots\ 3\ 1\ 4\ 2$
$操作前$    $操作後$
$4\ 1\ 3\ 2$    $1\ 2\ 4\ 3$
$2\ 4\ 1\ 3$    $4\ 3\ 2\ 1$
$3\ 2\ 4\ 1$    $2\ 1\ 3\ 4$
$1\ 3\ 2\ 4$    $3\ 4\ 1\ 2$
$・操作前の1列目を3列目に移動$
$・操作前の2列目を1列目に移動$
$・操作前の3列目を4列目に移動$
$・操作前の4列目を2列目に移動$

$2回目の操作:\ 4行目を選び行を並び替える$
$4行目の順列\ \dots\ 3\ 4\ 1\ 2$
$操作前$    $操作後$
$1\ 2\ 4\ 3$    $2\ 1\ 3\ 4$
$4\ 3\ 2\ 1$    $3\ 4\ 1\ 2$
$2\ 1\ 3\ 4$    $1\ 2\ 4\ 3$
$3\ 4\ 1\ 2$    $4\ 3\ 2\ 1$
$・操作前の1行目を3行目に移動$
$・操作前の2行目を4行目に移動$
$・操作前の3行目を1行目に移動$
$・操作前の4行目を2行目に移動$

$3回目の操作:\ 4行目を選び行を並び替える$
$4行目の順列\ \dots\ 4\ 3\ 2\ 1$
$操作前$    $操作後$
$2\ 1\ 3\ 4$    $4\ 3\ 2\ 1$
$3\ 4\ 1\ 2$    $1\ 2\ 4\ 3$
$1\ 2\ 4\ 3$    $3\ 4\ 1\ 2$
$4\ 3\ 2\ 1$    $2\ 1\ 3\ 4$
$・操作前の1行目を4行目に移動$
$・操作前の2行目を3行目に移動$
$・操作前の3行目を2行目に移動$
$・操作前の4行目を1行目に移動$
Make matrix $B$ equal to matrix $A$ by performing the same kind of operations on it at most $1000$ times. Output that sequence of operations.
If there are multiple sequences of operations that make them equal, you may output any of them (you do not need to minimize the number of operations; any sequence of at most $1000$ operations is acceptable).

Input

$N\ K$
$A_{1,1}\ A_{1,2}\ \dots\ A_{1,N}$
$A_{2,1}\ A_{2,2}\ \dots\ A_{2,N}$
$:$
$A_{N,1}\ A_{N,2}\ \dots\ A_{N,N}$
$B_{1,1}\ B_{1,2}\ \dots\ B_{1,N}$
$B_{2,1}\ B_{2,2}\ \dots\ B_{2,N}$
$:$
$B_{N,1}\ B_{N,2}\ \dots\ B_{N,N}$

$4\ \le\ N\ \le 10$
$2\ \le\ K\ \le\ 4$
$1\ \le\ A_{i,j}\ \le N\ (1\ \le\ i,j\ \le\ N)$
$1\ \le\ B_{i,j}\ \le N\ (1\ \le\ i,j\ \le\ N)$
Each row and each column of matrix $A$ and matrix $B$ is a permutation of $1$$\dots$$N$.
Matrix $B$ is generated by applying exactly $K$ operations to matrix $A$.
Only cases where matrix $A$ and matrix $B$ are not equal are selected as test cases.

Output

$M$
$X_1\ P_1$
$X_2\ P_2$
$:$
$X_M\ P_M$
Output the operations that make matrix $B$ equal to matrix $A$.
When the number of operations is $M$, output $M$ on the first line, followed by $M$ lines describing the operations in the order they are performed.
$X_i$ indicates whether the operation is on a column or a row: the character "C" when operating on a column, and the character "R" when operating on a row.
$P_i$ is the index of the selected position.
(Example: C 3 if column $3$ is selected, R 10 if row $10$ is selected)
Print a newline at the end.
$1\ \le\ M\ \le\ 1000$
$X_i\ =\ "C"\ または\ "R"\ (1\ \le\ i\ \le\ M)$
$1\ \le\ P_i\ \le\ N\ (1\ \le\ i\ \le\ M)$

Sample

Sample 1
Input
4 3
4 1 3 2
2 4 1 3
3 2 4 1
1 3 2 4
4 3 2 1
1 2 4 3
3 4 1 2
2 1 3 4
Output
2
R 1
C 4

This sequence of operations proceeds as follows. 

操作前     R 1        C 4
    $4\ 3\ 2\ 1$    $2\ 1\ 3\ 4$    $4\ 1\ 3\ 2$
    $1\ 2\ 4\ 3$    $3\ 4\ 1\ 2$    $2\ 4\ 1\ 3$
    $3\ 4\ 1\ 2$    $1\ 2\ 4\ 3$    $3\ 2\ 4\ 1$
    $2\ 1\ 3\ 4$    $4\ 3\ 2\ 1$    $1\ 3\ 2\ 4$
The sequence of $5$ moves R 4, R 1, C 4, C 2, C 1 also makes it equal to matrix $A$, so outputting these $5$ moves also gets AC.

Sample 2
Input
4 3
4 1 3 2
2 4 1 3
3 2 4 1
1 3 2 4
2 4 1 3
1 3 2 4
4 1 3 2
3 2 4 1
Output
1
R 1

Sample 3
Input
7 2
2 1 7 5 4 3 6
6 5 4 2 1 7 3
1 7 6 4 3 2 5
5 4 3 1 7 6 2
4 3 2 7 6 5 1
3 2 1 6 5 4 7
7 6 5 3 2 1 4
5 3 4 6 7 1 2
7 5 6 1 2 3 4
1 6 7 2 3 4 5
4 2 3 5 6 7 1
3 1 2 4 5 6 7
2 7 1 3 4 5 6
6 4 5 7 1 2 3
Output
5
R 5
R 5
C 6
C 5
C 6

Sample 4
Input
10 4
9 8 7 5 1 4 2 10 3 6
3 2 1 9 5 8 6 4 7 10
8 7 6 4 10 3 1 9 2 5
5 4 3 1 7 10 8 6 9 2
1 10 9 7 3 6 4 2 5 8
6 5 4 2 8 1 9 7 10 3
2 1 10 8 4 7 5 3 6 9
7 6 5 3 9 2 10 8 1 4
4 3 2 10 6 9 7 5 8 1
10 9 8 6 2 5 3 1 4 7
7 1 3 5 6 9 10 4 2 8
10 4 6 8 9 2 3 7 5 1
1 5 7 9 10 3 4 8 6 2
2 6 8 10 1 4 5 9 7 3
5 9 1 3 4 7 8 2 10 6
3 7 9 1 2 5 6 10 8 4
9 3 5 7 8 1 2 6 4 10
6 10 2 4 5 8 9 3 1 7
4 8 10 2 3 6 7 1 9 5
8 2 4 6 7 10 1 5 3 9
Output
19
R 2
R 4
R 8
R 7
R 3
C 4
C 4
C 4
C 4
C 4
R 1
R 10
R 7
R 3
R 3
R 9
R 5
R 3
R 9

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。