Kazun の競プロ記録

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

AtCoder Beginner Contest 224 B 問題 Mongeness

AtCoder ABC ABC224 B問題 200 pts

問題

提出解答

問題の概要

$1 \leq i \leq H, 1 \leq j \leq W$ に対して, $A_{i,j}$ が設定されている. このとき, $A$ は以下を満たすか?

$1 \leq i_1 \lt i_2 \leq H, 1 \leq j_1 \lt j_2 \leq W$ なる全ての整数の組 $(i_1, i_2, j_1, j_2)$ に対して, $A_{i_1,j_1}+A_{i_2,j_2} \leq A_{i_2,j_1}+A_{i_1,j_2}$ である.

制約

$2 \leq H,W \leq 50$
$1 \leq A_{i,j} \leq 10^9$

解法

$1 \leq i_1, i_2 \leq H, 1 \leq j_1, j_2 \leq W$ となる整数の組 $(i_1, i_2, j_1, j_2)$ は $(HW)^2$ 通りで, 制約から, 高々 $6250000$ であることから, 以下のような愚直な判定で間に合う.

となる整数の組で以下を満たすようなものが存在すれば, 答えは , 存在しなければ, である.
- $1 \leq i_1 \lt i_2 \leq H, 1 \leq j_1 \lt j_2 \leq W$
- $A_{i_1,j_1}+A_{i_2,j_2} \gt A_{i_2,j_1}+A_{i_1,j_2}$