問題

$N \times M$ 行列 $A, D (=\{D_{i, j} | D_{i, j} = M \times (i-1) + j\})$ が与えられる。次の操作を行って $A$ を $D$ に変換するとき、その途中経過である $B, C$ を1つ求める。

$A$ の行ごとに好きに並び替えて $B$ にする
$B$ の列ごとに好きに並び替えて $C$ にする
$C$ の行ごとに好きに並び替えて $D$ にする

atcoder.jp

考察

$B$ の満たすべき条件を考える。まず、 $D$ の要素は、それぞれの行ごとに同じ色がついているとみなす。つまり、 $r$ 行目の要素 $C_{r, j} (M\times (r-1) \lt C_{r, j} \leq M\times r)$ の色は $\mathcal{c}_r$ である。 $C$ は、行の並び替えだけで $D$ になるために、 $C$ の各行も同じ色で、なおかつ、各列には、 $N$ 色の要素がそれぞれ1つずつ存在する。 $B \rightarrow C$ の変換では列ごとの要素が変わらないので、 $B$ はこの制約をみたす必要がある。

$B$ の $j$ 列目について、 $N$ 行それぞれに $N$ 色を分配する方法を考える。 $i$ 行目に $\mathcal{c}_r$ を入れられるかは、 $A$ の $i$ 行目に $\mathcal{c}_r$ があるかどうかで決まる。そこで、行を表す $N$ 個の頂点と色を表す $N$ 個の頂点を持った $2N$ 頂点のグラフを考え、 $i$ 行目に $\mathcal{c}_r$ があるなら、これらに対応する頂点同士に辺を張る。これで、どの行にどの色を割り当てるかを、完全マッチングで決められる。一度使った要素はその行から削除する。ここで、次の補題（証明は後述）より、残りの列も同様に繰り返すことで要素を決めることができる。

制約を満たすような任意の $M-m$ 列の割り当てをおこなったとき、残りの $m$ 列も制約を満たすマッチングが存在する

以上で $B$ を構築できた。 $C$ は $B$ を列ごとに昇順に並べればよい。

証明

[補題]制約を満たすような任意の $M-m$ 列の割り当てをおこなったとき、残りの $m$ 列も制約を満たすマッチングが存在する

$m$ 列残っているとき、各色 $\mathcal{c}_i$ の要素もちょうど $m$ 色ずつ残っている。それぞれの行について、要素が1つ以上存在するので、その行と辺を張った色が1つ以上存在する。また、それぞれの色について、少なくとも1つ以上の行に入っているので、その色と辺を張った行が1つ以上存在する。以上より、 $N$ 色に対して $N$ 行のマッチングがあるので、ホールの定理より、制約を満たすマッチングが存在する。

実装

atcoder.jp

かしのブログ

競技プログラミングとか

AtCoder Grand Contest 037 D - Sorting a Grid

問題

考察

証明

実装