Kazun の競プロ記録

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

AtCoder Beginner Contest 256 C問題 Filling 3x3 array

AtCoder ABC ABC256 C問題 300 pts

問題

提出解答

問題の概要

3行3列からなるマス目がある. この $9$ 個のマス目のそれぞれに整数を書くとき, 以下を全て満たすような整数の書き込み方は何通りか?

整数は全て正の整数.
上から $i$ 行目に書いた $3$ 個の整数の総和は $h_i$ である ( $i=1,2,3$ ).
左から $j$ 列目に書いた $3$ 個の整数の総和は $w_j$ である ( $j=1,2,3$ ).

制約

$3 \leq h_i, w_j \leq 30$

解法

上から $i$ 行目, 左から $j$ 列目に書く整数を $x_{i,j}$ と書くことにする. このとき, 以下がわかる.

4つの整数 $a_{1,1}, a_{1,2}, a_{2,1}, a_{2,2}$ に対して, $x\_{i,j}=a\_{i,j}~(i,j=1,2)$ となる条件を満たすような書き込みは存在するならば一意である.

実際, $x_{1,3}, x_{2,3}, x_{3,1}, x_{3,2}$ は書き込みが存在するならば,

$x_{1,3}=h_1-(x_{1,1}+x_{1,2})$
$x_{2,3}=h_2-(x_{2,1}+x_{2,2})$
$x_{3,3}=h_3-(x_{3,1}+x_{3,2})$
$x_{3,1}=w_1-(x_{1,1}+x_{2,1})$
$x_{3,2}=w_2-(x_{1,2}+x_{2,2})$

でなくてはならない.

また, 書き込み整数は正なので, $M:=\max(h_1, h_2, h_3, w_1, w_2, w_3)$ としたとき, $1$ 以上 $M$ 以下でなくてはならない.

このことから, $a_{1,1}, a_{1,2}, a_{2,1}, a_{2,2}$ として $1$ 以上 $M$ 以下の整数を割り当てたそれぞれの場合において, 上で定めた $x_{1,3}, x_{2,3}, x_{3,3}, x_{3,1}, x_{3,2}$ が条件を満たすかどうかを見ればよい. 具体的に調べなくては行けない条件は

$x_{1,3}+x_{2,3}+x_{3,3}=w_3$
$x_{1,3}, x_{2,3}, x_{3,3}, x_{3,1}, x_{3,2} \gt 0$

である.

計算量は $O(M^4)$ であり, $M \leq 30$ なので, 十分高速に計算できる.