公式解説 の補足です。

\[ \begin{aligned} \det\begin{bmatrix} a & -e & 0 & 0\\ -e & b & -1 & 0\\ 0 & -1 & c & -f \\ 0 & 0 & -f & d\\ \end{bmatrix} &= \det\begin{bmatrix} a & -e\\ -e & b\\ \end{bmatrix} \det\begin{bmatrix} d & -f\\ -f & c\\ \end{bmatrix} - ad\\ &= (ab - e^2)(dc - f^2) - ad \end{aligned} \]

をベースとします。(これ以外にもさまざまな構築方法があると思います。)

対称的な形なので、\(2 \times 2\) の小行列 (\(\begin{bmatrix} a & -e\\ -e & b\\ \end{bmatrix}\) の部分) の \(\det\) を前計算しておくのが良さそうです。

\(\text{MAX} = 250\) とし、\(a, b, e \le \text{MAX}\) の範囲で \((ab - e^2, a)\) の組を前計算しておき、\(ab - e^2\) でソートします。

上側の \(2 \times 2\) の小行列を \(\begin{bmatrix} a & -e\\ -e & b\\ \end{bmatrix}\) に固定すると、その \(\det\) の大きさによりもう片方の \(\det\) の大きさを絞り込むことができます。

\[ (ab - e^2)(dc - f^2) - a\text{MAX} \le K \le (ab - e^2)(dc - f^2)\\ \frac{K}{ab - e^2} \le dc - f^2 \le \frac{K +a\text{MAX}}{ab - e^2} \]

これにより、探索すべき範囲を大きく削減できるので、全探索で答えを発見できます。

実装例 (C++)

また、これを改変することで、この解法の正当性 (すべての \(K\) に対しこの形の答えが存在すること) を 40 秒ほどの実行で確かめることができます。

実装例 (C++)