Google Code Jam Qual-indicium

codingcompetitions.withgoogle.com

実装が難しいので、必要な考え方を書いていきます。
indiciumはラテン語で行列のtraceの意味なんですね、へ～！

問題
「次数がnのラテン方陣が与えられたとき、traceがk（n<=k<=n*n）になるものがあるなら一つ求めよ」
n次のラテン方陣とは、各行・各列が1, 2, ... , nの順列になっているもののことです（下図（n=3））

まず、明らかに題意を満たすようなラテン方陣が存在しない場合を考えてみると、次の二つがあります。
・k=n+1

・k=n*n-1

どちらも同じような理由で不適です。
では、k=n+2としてみるとどうでしょうか？

上図のように、最初は1, 1, ... , 1, 3と並べておきます。この並び方はk=n+1の場合と同様に不適です。
しかし、次に最後の2つの（1, 3）を（2, 2）にすることによって、k=n+1とは違ったパターンにすることができます。
（ただし、（n, k）＝（3, 5）の場合は、（1, 1, 3）の並びを（1, 2, 2）にしてもk=n+1のパターンと同じになってしまい不適です。同様の理由で、
（n, k）＝（3, 7）の場合も不適です（k=n*n-2）。）

さて、ラテン方陣が存在するパターンと存在しないパターンの違いについて考えてみます。
k=n+1, n*n-1の場合、行列の対角成分をすべて決めたとき、残った1（またはn）を書き込む場所がなかったことが問題でした。
では逆に、k≠n+1, n*n-1の場合を考えてみましょう。

上図のように、対角成分のうちn-2個が1の場合、対角成分をすべて決めても1を書き込む場所があります。
ある数i（1<=i<=n）に着目したとき、対角成分にあるiの数がn-2個以下なら、対角成分をすべて決めた後でもiを書き込む場所があることは明らかに分かります。

また、対角成分に書き込む数字の数は高々3つでokと言えそうです（証明略）。
対角成分に用いた数字については図のように埋めておきます（すぬけさんのツイッター）。

ここで、iをラテン方陣の（p, q）に書き込むことは「n個の行→n個の列を対応させる二部マッチングについて、pからqに辺をひく」という操作と考えることが出来ます。

さらに、ここでHallの結婚定理を使います。
mathtrain.jp
ここで言いたいことは、「対角成分を定めたときに、1からnまでのすべての自然数iについて、行（集合Uとする）→列（集合Vとする）の完全マッチングが存在する」ことです。

対角成分に数字を書き込んだ後、残ったものの数をjとします（集合U, Vの要素数もjとなります）。

数字をp行q列目に書き込んだら、U, Vの辺p-qを消しておきましょう。
すると、U, Vの頂点の次数はすべてjとなります。
行、列ともに頂点数はj個なので、

条件1：Uのすべての頂点をカバーするマッチングが存在する

が言えればよいです。Hallの結婚定理は

条件2：任意のUの部分集合Aについて、|A|<=|Γ(A)|が成り立つ

としたときに、条件1と条件2が同値である、というものです。
よって、条件2を示せば十分でしょう。

Uのうちからx個の頂点を選んだとき、これらの頂点から出ている辺の数はxj個です。
一方、実際にUのx個の頂点と繋がっているVの頂点数をyとすると、yから出ている辺の数も同様にyjと分かります。
よって、xj=yjよりx=yなので、x<=yが成り立ちます。
これで完全マッチングの存在を示すことができました。
にしても、考察はさておき実装が大変そうですね。二部マッチングの復元ってどうやるんでしょう。
（後々編集するかもしれません）