コンテンツにスキップ

DOJ Beginner Contest 8 G - Nostalgia

サイト
DOJ
コンテスト
DOJ Beginner Contest 8
問題
G - Nostalgia

N×NN \times N のマスに、11 から N2N^2 までの整数を 1 つずつ書き込みます(マス (i,j)(i, j) の値を Hi,jH_{i,j} とします)。各列の最大値の和を S1S_1、各行の最大値の和を S2S_2 とします。

整数 XX が与えられるので、S1−S2=XS_1 - S_2 = X となる書き込み方を 1 つ出力する問題です。存在しなければ −1-1 を出力します。N2N^2 の総和は 10510^5 以下です。

X≥0X \ge 0 の場合を考えます。X<0X < 0 の場合は、−X-X の答えを転置すれば行と列が入れ替わり、S1S_1 と S2S_2 が入れ替わるので求まります。

F=N(N−1)22F = \dfrac{N (N - 1)^2}{2} とすると、S1−S2≤FS_1 - S_2 \le F です。

  • S2S_2 の下限:行の最大値を小さい順に r1<r2<⋯<rNr_1 < r_2 < \dots < r_N とします。最大値が小さいほうから kk 行には、rkr_k 以下の相異なる数が kNkN 個あるので、rk≥kNr_k \ge kN です。よって S2≥N(1+2+⋯+N)S_2 \ge N(1 + 2 + \dots + N) です。
  • S1S_1 の上限:列の最大値は相異なるので、S1S_1 は大きいほうから NN 個の数の和 N2+(N2−1)+⋯+(N2−N+1)N^2 + (N^2 - 1) + \dots + (N^2 - N + 1) 以下です。

この 2 つの差を計算すると FF になります。したがって、∣X∣>F|X| > F なら −1-1 です。

対角線のマスの値を l1<l2<⋯<lN=N2l_1 < l_2 < \dots < l_N = N^2 とし、li≥iNl_i \ge iN を満たすように決めます。残りの数は、小さい順に、対角線以外のマスへ行ごとに左から書き込みます。最後に、最下行の対角線以外の N−1N - 1 マスだけ、左右の順を逆にします。

このとき、次のことがいえます。

  • 行の最大値は lil_i:ii 行目の対角線以外のマスには、残りの数のうち小さいほうから (i−1)(N−1)+1(i - 1)(N - 1) + 1 番目から i(N−1)i(N - 1) 番目が入ります。lil_i より小さい残りの数は li−1−(i−1)≥i(N−1)l_i - 1 - (i - 1) \ge i(N - 1) 個あるので、これらはすべて lil_i より小さいです。よって S2=l1+⋯+lNS_2 = l_1 + \dots + l_N です。
  • 列の最大値は大きいほうから NN 個の数:最下行の対角線以外のマスには、残りの数のうち大きいほうから N−1N - 1 個が入ります。左右を逆にしたので、大きいものほど左の列に入ります。大きいほうから NN 個の数のうち、対角線にあるものは lN,lN−1,…l_N, l_{N-1}, \dots と右下からつながっていて、その列の最大値になります。残りは最下行の左側の列に入り、どれもその列の最大値になります。よって S1S_1 は常に上限の値になります。

したがって S1−S2=(大きいほうから N 個の和)−(l1+⋯+lN)S_1 - S_2 = (\text{大きいほうから } N \text{ 個の和}) - (l_1 + \dots + l_N) です。

li=iNl_i = iN とすると、S2S_2 が下限になるので差は FF です。そこから lil_i を増やすと、増やした分だけ差が減ります。lN−1,lN−2,…l_{N-1}, l_{N-2}, \dots の順に、li+1−1l_{i+1} - 1 を超えない範囲で必要な分だけ増やしていきます。全部を限界まで増やすと、対角線が大きいほうから NN 個の数になって差は 00 になります。そのため、00 以上 FF 以下のどの XX でも作れます。

Python
from itertools import product, combinations
for _ in range(int(input())):
N, X = map(int, input().split())
t = abs(X)
f = N * (N - 1) // 2 * (N - 1)
if t > f:
print(-1)
continue
f -= t
l = [i * N for i in range(1, N + 1)]
for i in reversed(range(N - 1)):
if f == 0:
continue
p = min(f, l[i + 1] - l[i] - 1)
l[i] += p
f -= p
s = set(range(1, N * N + 1))
ans = [[-1] * N for i in range(N)]
for i in range(N):
s.remove(l[i])
ans[i][i] = l[i]
s = sorted(s, reverse=True)
for i, j in product(range(N), repeat=2):
if ans[i][j] != -1:
continue
ans[i][j] = s.pop()
ans[-1][:-1] = reversed(ans[-1][:-1])
if X < 0:
for i, j in combinations(range(N), r=2):
ans[i][j], ans[j][i] = ans[j][i], ans[i][j]
for a in ans:
print(*a)

コードは 0-indexed です。f は、差を FF から XX に減らすために対角線の値を増やす量の残りです。ans[-1][:-1] = reversed(ans[-1][:-1]) で最下行を左右逆にしています。