Codeforces Round #531 (Div. 3)F. Elongated Matrix

問題概要

$n \times m$ の行列が与えられる. この行列について, 行を自由に入れ替える. この結果できた行列を $A$ としたとき, 数列 $s$ を $s = \{a_{11}, a_{21}, \cdots a_{n1}, a_{12}, \cdots, a_{nm}\}$ として定める.

このとき, ある $k$ に対して, 全ての $1 \le i \le nm-1$ について $|s_i - s_{i+1}| \ge k$ が成り立つとき, $s$ は良い数列であるという.

与えられた行列に対し, 良い数列が存在する最大の $k$ を求めよ.

問題へのリンク

制約

$1 \le n \le 16, 1 \le m \le 10^4, 2 \le nm$
$1 \le a_{ij} \le 10^9$

解法

見るからに二分探索です. 解となる $k$ を決め打ちして, 良い数列が構築できるか判定しましょう.

$i$ 番目の行の次に $j$ 番目の行が来れるかどうかは, $min_{1 \le p \le m}|a_{ip} - a_{jp}| \ge k$ ならば来れると判定できます. これは, 各行を頂点とし, 条件を満たすとき $i \rightarrow j$ の辺を張ることにすれば, 全ての頂点をめぐって最初の頂点に帰ってこれるか？という判定問題に帰着することができます.