Codeforces Round #732 (Div. 1)_C　AquaMoon and Permutations

あまりに解説が薄すぎてかなり苦労をしたのでメモ

～～問題概要～～

$2n \times n$ のサイズの行列 $A$ を考えます。

各行は、 $1,2,...,n$ の順列です。

上半分は、ラテン方格になっています。

下半分は、ラテン方格とは限りません。

全ての $i(\le n)$ について $A_{i,j} = A_{i+n,j}$ を満たす $j$ が存在します。

$A$ の行をシャッフルした行列が与えられるので、 $n$ 個の行の選び方のうち、それらを繋ぎ合わせたものがラテン方格となる選び方を数えあげ、更に一つ構築してください。

解説

公式の解説はこちら

codeforces.com

解説が短すぎる…というわけで、証明も含めて分かりやすく解説していきたいと思います。

$j$ 列目に、数 $x$ がある状態をタプル $(j,x)$ で表したいと思います。

すると、各行は $n$ 個のタプルの集合と言い換えられます。

この時、問題は、 $2n$ 個の行から $n$ 個の行を選んで、 $n^2$ 種類ある全てのタプルを揃える問題と言い換えることができます。各行が $n$ 個のタプルを持つので、全種類のタプルを $1$ 個ずつ揃える必要があります。

まず、固有(1回しか登場しない)のタプルを持つ行は必ず採用されます。このような行を全てpickupします。

pickupした行と、共通のタプルを持つ行は選ばれることはありません。このような行をすべて削除します。

削除した後、削除していない行の集合に新たな固有のタプルが生まれた場合、それを含む行もpickupします。これを再帰的に行います。

操作後、pickupも削除もされていない行の集合 $S$ について考えます。まず、問題のこの部分に着目します。

全ての $i(\le n)$ について $A_{i,j} = A_{i+n,j}$ を満たす $j$ が存在する。

すなわち、1つの行 $A_i$ がpickupされるとそれに対応する行 $A_{i+n}$ は、 $A_i$ をpickupした時か、それ以前に必ず削除されています。
pickupした行の数以上の数の行が削除行きになっているため、 $S$ に含まれる行の内、半数以上が $A$ の上半分由来です。

$S$ に含まれる行のうち、 $u$ 個が上半分由来だとしましょう。

まず、 $S$ に含まれる行に含まれるタプルは、全て $S$ 内に2回以上登場します。これは、固有のタプルを含む行は全てpickupしたことから自明です。

また、上半分由来のタプルは重複しません(上半分はラテン方格なので)。

そのため、上半分由来の行の持つタプルの種類数は $un$ 個で、全て $1$ つずつです。

上半分由来ではない行の個数を、 $d$ とします。これが含むタプルの個数は、 $dn$ 個です。全ての種類のタプルは2回ずつ登場しなくてはいけないので、 $dn$ 個の中には上半分由来の $un$ 種類のタプルが全て含まれています。 $d \le u$ であることから、 $d=u$ が示され、全てのタプルが $S$ にちょうど2回だけ登場することが分かります。さらに言えば、全てのタプルが上半分由来の行と、下半分由来の行にちょうど1回ずつ登場します。