C - Filling 3x3 array Editorial by kzrnm
\(i\) 行 \(j\) 列の値を \(a_{i, j}\) とします。
この問題は9つの変数 \(a\) についての連立方程式と考えることができます。
\(i=1,2,3\) および \(j=1,2,3\) で
- \(h_i = a_{i, 1} + a_{i, 2} +a_{i, 3}\)
- \(w_j = a_{1, j} + a_{2, j} +a_{3, j}\)
が成り立つので、6つの連立方程式が立てられます。
連立方程式を解くのは面倒なので、\(a_{1,1}, a_{1,2}, a_{2,1}, a_{2,2}\) を適当な値で初期化して残りの値を矛盾なく割り当てられるかどうかで判定することにします。
制約より、あきらかに \(0 \lt a_{i, j} \lt 29\) なので、\(a_{1,1}, a_{1,2}, a_{2,1}, a_{2,2}\) をそれぞれ \(1,2,...,28\) で初期化して条件をみたすか判定すれば求められます。
計算量は \(28^4=614656\) 回程度になります。
posted:
last update: