DOJ Beginner Contest 8 G - Nostalgia
- サイト
- DOJ
- コンテスト
- DOJ Beginner Contest 8
- 問題
- G - Nostalgia
のマスに、 から までの整数を 1 つずつ書き込みます(マス の値を とします)。各列の最大値の和を 、各行の最大値の和を とします。
整数 が与えられるので、 となる書き込み方を 1 つ出力する問題です。存在しなければ を出力します。 の総和は 以下です。
の場合を考えます。 の場合は、 の答えを転置すれば行と列が入れ替わり、 と が入れ替わるので求まります。
とすると、 です。
- の下限:行の最大値を小さい順に とします。最大値が小さいほうから 行には、 以下の相異なる数が 個あるので、 です。よって です。
- の上限:列の最大値は相異なるので、 は大きいほうから 個の数の和 以下です。
この 2 つの差を計算すると になります。したがって、 なら です。
対角線のマスの値を とし、 を満たすように決めます。残りの数は、小さい順に、対角線以外のマスへ行ごとに左から書き込みます。最後に、最下行の対角線以外の マスだけ、左右の順を逆にします。
このとき、次のことがいえます。
- 行の最大値は : 行目の対角線以外のマスには、残りの数のうち小さいほうから 番目から 番目が入ります。 より小さい残りの数は 個あるので、これらはすべて より小さいです。よって です。
- 列の最大値は大きいほうから 個の数:最下行の対角線以外のマスには、残りの数のうち大きいほうから 個が入ります。左右を逆にしたので、大きいものほど左の列に入ります。大きいほうから 個の数のうち、対角線にあるものは と右下からつながっていて、その列の最大値になります。残りは最下行の左側の列に入り、どれもその列の最大値になります。よって は常に上限の値になります。
したがって です。
とすると、 が下限になるので差は です。そこから を増やすと、増やした分だけ差が減ります。 の順に、 を超えない範囲で必要な分だけ増やしていきます。全部を限界まで増やすと、対角線が大きいほうから 個の数になって差は になります。そのため、 以上 以下のどの でも作れます。
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 は、差を から に減らすために対角線の値を増やす量の残りです。ans[-1][:-1] = reversed(ans[-1][:-1]) で最下行を左右逆にしています。