Official
E - Max Matrix 2 Editorial
by
E - Max Matrix 2 Editorial
by
sounansya
\(X\) に同じ要素が \(2\) つ以上含まれる場合の答えは No です(\(Y\) も同様です)。以降はこれ以外の場合を考えます。
\(A\) に \(N\times M\) から \(1\) まで大きい順に要素を埋めていくことを考えます。
\(v\) より大きい要素を全て埋めたとして、 \(v\) を埋める場合のルールは次の通りです。
- \(v\) が \(X\) にも \(Y\) にも含まれるとき:\(X_i=Y_j=v\) として、\(A_{i,j}\) に \(v\) を埋める。
- \(v\) が \(X\) のみに含まれるとき: \(X_i=v\) として、 \(Y_j>v\) かつ \(A_{i,j}\) がまだ埋まっていないような \(A_{i,j}\) に \(v\) を埋める。
- \(v\) が \(Y\) のみに含まれるとき: \(Y_j=v\) として、 \(X_i>v\) かつ \(A_{i,j}\) がまだ埋まっていないような \(A_{i,j}\) に \(v\) を埋める。
- \(v\) が \(X,Y\) どちらにも含まれないとき:\(X_i>v\) かつ \(Y_j>v\) かつ \(A_{i,j}\) がまだ埋まっていないような \(A_{i,j}\) に \(v\) を埋める。
\(v\) を大きい順に埋めていくことから、埋められる数字の候補は単調増加するため上記のルールを満たす箇所であれば好きに埋めていけば良いです。
以上の発想を実装に落とし込めば良いですが、上のルールをそのまま実装すると計算量が悪く TLE となります。実装する上では、 \(A_{i,j}\) は \(v < \min(X_i,Y_j)\) となれば自由に埋めて良いと考え \(v=\min(X_i,Y_j)\) を満たす \((i,j)\) をリストで管理するなどすれば良いです。詳しくは実装例を参考にしてください。
実装例(Python3)
import sys
from collections import deque
input = sys.stdin.readline
def solve():
n, m = map(int, input().split())
nm = n * m
x = [v - 1 for v in map(int, input().split())]
y = [v - 1 for v in map(int, input().split())]
gx = [-1] * nm
gy = [-1] * nm
for i in range(n):
if gx[x[i]] != -1:
print("No")
return
gx[x[i]] = i
for j in range(m):
if gy[y[j]] != -1:
print("No")
return
gy[y[j]] = j
ok = [[] for _ in range(nm)]
for i in range(n):
for j in range(m):
ok[min(x[i], y[j])].append((i, j))
ans = [[-1] * m for _ in range(n)]
q = deque()
for v in range(nm - 1, -1, -1):
if gx[v] == -1 and gy[v] == -1:
if not q:
print("No")
return
i, j = q.popleft()
ans[i][j] = v + 1
for ii, jj in ok[v]:
q.append((ii, jj))
continue
if gx[v] == -1 or gy[v] == -1:
if not ok[v]:
print("No")
return
i, j = ok[v].pop()
ans[i][j] = v + 1
for ii, jj in ok[v]:
q.append((ii, jj))
continue
i, j = gx[v], gy[v]
ans[i][j] = v + 1
for ii, jj in ok[v]:
if i != ii or j != jj:
q.append((ii, jj))
print("Yes")
for r in ans:
print(*r)
for _ in range(int(input())):
solve()
posted:
last update:
