結果

問題 No.2986 Permutation Puzzle
ユーザー ID 21712
提出日時 2025-01-23 18:20:17
言語 Standard ML
(MLton 20210117)
結果
AC  
実行時間 372 ms / 2,000 ms
コード長 3,365 bytes
コンパイル時間 6,913 ms
コンパイル使用メモリ 689,020 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2025-01-23 18:20:33
合計ジャッジ時間 13,258 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

type matrix = int Array2.array;

fun rFindMapi (0 : int) (f : int -> 'a option) : 'a option = f 0
	| rFindMapi (i : int) (f : int -> 'a option) : 'a option = let
		val res = f i
	in
		if Option.isSome res then res else rFindMapi (i-1) f
	end;

fun rFindi (n : int) (f : int -> bool) : int option = 
	rFindMapi n (fn i => if f i then SOME(i) else NONE);

fun unfold (f : 'a -> ('a * 'b) option) (s : 'a) : 'b list = case  f s of
	SOME(a,b) => b :: unfold f a
	| NONE => nil;

fun copyMatrix (m : matrix) : matrix = Array2.tabulate Array2.RowMajor (Array2.nRows m, Array2.nCols m, fn (r,c) => Array2.sub (m,r,c));

fun reorderColsByColPerm (s : matrix, x : int) : unit = let
		val t = copyMatrix s
		val rt = {base=t,col=0,row=0,nrows=NONE,ncols=NONE} 
	in
		Array2.appi Array2.RowMajor (fn (r,c,e) => Array2.update (s,r,Array2.sub (t,c,x),e)) rt
	end;

fun reorderRowsByRowPerm (s : matrix, y : int) : unit = let
		val t = copyMatrix s
		val rt = {base=t,col=0,row=0,nrows=NONE,ncols=NONE} 
	in
		Array2.appi Array2.RowMajor (fn (r,c,e) => Array2.update (s,Array2.sub (t,y,r),c,e)) rt
	end;
	
fun isSameM (n : int, a : matrix, b : matrix) : bool = 
	not (Option.isSome (rFindi (n-1) (fn r => Option.isSome (rFindi (n-1) (fn c => Array2.sub (a,r,c) <> Array2.sub (b,r,c))))));

fun isSameA (n : int, a : int array, b : int array) : bool =
	not (Option.isSome (rFindi (n-1) (fn i => Array.sub (a,i) <> Array.sub (b,i))));

fun search (n : int, b : matrix, 0 : int, t : matrix) : int list option = if isSameM (n,b,t) then SOME(nil) else NONE
 | search (n : int, b : matrix, k : int, t : matrix) : int list option = let
		fun find (ope : int) : int list option = let
			val s = copyMatrix t
			val () = if ope < n then reorderColsByColPerm (s,ope) else reorderRowsByRowPerm (s,ope-n)
		in
			Option.map (fn tail => ope :: tail) (search (n,b,k-1,s))
		end
	in
		rFindMapi (2*n-1) find
	end;

fun selectCol (n : int, s : matrix, x : int) : int array =
	Array.tabulate (n, fn r => Array2.sub (s,r,x));

fun selectRow (n : int, s : matrix, y : int) : int array =
	Array.tabulate (n, fn c => Array2.sub (s,y,c));

fun solve (n : int, k : int, a : matrix, b : matrix) : int list = let
		val opes = valOf (search (n, b, k, a))
		fun f (ope : int) : int list = let
			val perm = if ope < n then selectCol (n,a,ope) else selectRow (n,a,ope-n)
			val () = if ope < n then reorderColsByColPerm (a,ope) else reorderRowsByRowPerm (a,ope-n)
			fun uff (z0 : int, t0 : int array) : ((int * int array) * int) option = let
				val z1 = Array.sub (perm,z0)
				val zz = z1 + (ope div n) * n
				val t1 = Array.array (n,0)
				val () = Array.appi (fn (i,e) => Array.update (t1,e,Array.sub (t0,i))) perm
			in
				if isSameA (n,perm,t1) then NONE else SOME(((z1,t1),zz))
			end
		in
			unfold uff (ope mod n, perm)
		end
	in
		(List.concat o rev) (map f opes)
	end;

fun readInt () : int = valOf (TextIO.scanStream (Int.scan StringCvt.DEC) TextIO.stdIn);

fun readMatrix (n : int) : matrix = Array2.tabulate Array2.RowMajor (n,n, fn (_,_) => readInt () - 1);

fun printLine (s : string) : unit = print (s ^ "\n");

val n = readInt ();
val k = readInt ();
val a = readMatrix n;
val b = readMatrix n;
val ans = solve (n, k, a, b);
val () = printLine (Int.toString (length ans));
val () = List.app (printLine o (fn ope => (if ope < n then "C " else "R ") ^ Int.toString ((ope mod n)+1))) ans;
0