Official

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: