今回は、記事の名前の通り「完全グラフ \(K_{2N}\) を \(N-1\) 個のハミルトン閉路と \(1\) 個の完全マッチングに分解」していこうと思います。 まず、この分解の意味について。具体的には Doofish Matrix という問題を解くときにこれを調べててヒットしなく…

この記事は Dwango Programming Contest 6th でNosubをやってしまったお詫びとして書かれたものです。このコンテストのB問題もこの記事の中で解説されます。 まず、この記事で説明する「主客転倒」とは、 得点 \(A_i\) をいくつか足した和で表される総得点 \…