結果

問題 No.2986 Permutation Puzzle
コンテスト
ユーザー ID 21712
提出日時 2024-11-29 14:08:06
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 635 ms / 2,000 ms
コード長 2,305 bytes
コンパイル時間 163 ms
コンパイル使用メモリ 12,928 KB
実行使用メモリ 11,136 KB
最終ジャッジ日時 2024-12-02 12:32:17
合計ジャッジ時間 10,199 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

#  yukicoder - ProblemID 11672 - writer's solution

class PPuzzle:
	def __init__(self, n):
		self.n = n
		self.f = []
		self.iCol = []
		self.iRow = []
	def scan(self):
		self.f = [list(map(int, input().split())) for _ in range(self.n)]
		self.iCol = list(range(self.n))
		self.iRow = list(range(self.n))
		return self
	def at(self, r, c):
		return self.f[self.iRow[r-1]][self.iCol[c-1]]
	def clone(self):
		p = PPuzzle(self.n)
		p.f = self.f
		p.iCol = self.iCol.copy()
		p.iRow = self.iRow.copy()
		return p
	def is_same(self, p):
		for r in range(1,self.n+1):
			for c in range(1,self.n+1):
				if self.at(r,c) != p.at(r,c):
					return False
		return True
	def select_col(self, c):
		return [self.at(r, c) for r in range(1,self.n+1)]
	def select_row(self, r):
		return [self.at(r, c) for c in range(1,self.n+1)]
	def operate_col(self, c):
		s = self.select_col(c)
		tmp = self.iCol.copy()
		for (i,e) in enumerate(s):
			self.iCol[e-1] = tmp[i]
	def operate_row(self, r):
		s = self.select_row(r)
		tmp = self.iRow.copy()
		for (i,e) in enumerate(s):
			self.iRow[e-1] = tmp[i]

class Problem:
	def __init__(self):
		self.N = 0
		self.K = 0
		self.A = None
		self.B = None
	def scan(self):
		self.N, self.K = list(map(int,input().split()))
		self.A = PPuzzle(self.N).scan()
		self.B = PPuzzle(self.N).scan()
		return self

def solve(p):
	def search(k, x, m):
		if k == 0:
			return m if p.B.is_same(x) else None
		for i in range(1,p.N*2+1):
			y = x.clone()
			m.append(i)
			if i <= p.N:
				y.operate_col(i)
			else:
				y.operate_row(i-p.N)
			if search(k-1,y,m):
				return m
			m.pop()
		return None
	m = search(p.K, p.A, [])
	z = p.A.clone()
	ps = []
	for i in m:
		s = z.select_col(i) if i <= p.N else z.select_row(i-p.N)
		ps.append((i,s))
		if i <= p.N:
			z.operate_col(i)
		else:
			z.operate_row(i-p.N)
	def cycle(s):
		c = 0
		x = s.copy()
		while True:
			c += 1
			y = x.copy()
			for (i,e) in enumerate(s):
				x[e-1] = y[i]
			if x == s:
				return c
	ps.reverse()
	ans = []
	for (i,s) in ps:
		c = cycle(s)
		g = 0 if i <= p.N else p.N
		h = s[i-1-g]
		for _ in range(c-1):
			ans.append(h+g)
			h = s[h-1]
	return ans
			

if __name__ == '__main__':
	p = Problem().scan()
	ans = solve(p)
	print(len(ans))
	for x in ans:
		if x <= p.N:
			print("C", x)
		else:
			print("R", x-p.N)
0