Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Regular Contest 142 B問題 Unbalanced Squares

AtCoder ARC ARC142 B問題 400 pts

問題

提出解答

問題の概要

$N$ 行 $N$ 列のマス目がある. 各マスに対して $1$ 以上 $N^2$ 以下の整数を $1$ 個ずつ書く書き込み方のうち, 以下の条件を満たすような書き込み方を $1$ つ挙げよ. ただし, $i$ 行目 $j$ 列目のマス目に書く整数を $x_{i,j}$ と書くことにする.

$k=1,2, \dots N^2$ に対して, $x_{i,j}=k$ となる整数の組 $(i,j)$ が唯一存在する.
あるマスの上下左右斜めに隣接するマスをそのマスの近傍と呼ぶとき, 各マス $(i,j)$ について, $x_{i,j}$ より大きい整数が書かれている近傍のマスの数と, $x_{i,j}$ より小さい整数が書かれている近傍のマスの数が異なる.

制約

$1 \leq N \leq 500$

解法

$A:=\{1,2, \dots, N^2\}$ の分割 $A=S \coprod L$ を

$S:=\left \{1,2, \dots, N \left \lceil\dfrac{N}{2} \right \rceil \right\}$
$L:=\left \{ \left \lceil\dfrac{N}{2} \right \rceil+1, \dots, N^2 \right\}$

とする. このとき,

奇数行目にある $\displaystyle N \left \lceil\dfrac{N}{2} \right \rceil$ 個のマスに $S$ の要素を1個ずつ書き込む.
偶数行目にある $\displaystyle N^2-N \left \lceil \dfrac{N}{2} \right \rceil$ 個のマスに $L$ の要素を1個ずつ書き込む.

ような書き込み方は条件を満たす. 実際,

$1$ 行目, $N$ 行目, $1$ 列目, $1$ 行目にあるマス目における近傍のマスの数はそもそも奇数なので, どのような書き込みでも条件を満たす.
それ以外のマスにおいては近傍のマスの数はであるが
- 奇数行目のマスにおいては, $x_{i,j} \in S$ であるが, 上斜め左, 上, 上斜め右, 下斜め左, 下, 下斜め右のマスに書かれている整数は全て $L$ の要素なので, 少なくとも $6$ 個の近傍には $x_{i,j}$ より大きい整数が書かれているので条件を満たす.
- 偶数行目のマスにおいては, $x_{i,j} \in L$ であるが, 上斜め左, 上, 上斜め右, 下斜め左, 下, 下斜め右のマスに書かれている整数は全て $S$ の要素なので, 少なくとも $6$ 個の近傍には $x_{i,j}$ より小さい整数が書かれているので条件を満たす.

となるからである.