Unfair Tournament - Cry's Blog

さっきソファーに突っ伏して仮眠して起きたら，解法っぽいものを思いついた．アルゴリズムが正しいかどうかは知らん．
http://www.kmonos.net/wlog/53.php#_1604050908
前提として，人数は2のべきと仮定します．
まず，表記を導入します．
(A, B, C, D)
といったような表記で順序付き集合を現します．上は要素数が4の順序付き集合です．
次に，上の表記の順序付き集合に対して「連結」という3項演算を定義します．「連結」は，
(a, b, ..., s)
と
(t, u, ..., z)
と
(a, t)
という3つの順序付き集合から
(a, b, ..., s, t, u, ..., z)
という1つの順序付き集合を得る演算です．これを「(a, t) による (a, b, ..., s) と (t, u, ...,z) の連結」と呼ぶことにします．ただし，演算の結果要素が重複するような「連結」，つまり (a, b, ..., s) と (t, u, ...,z) に同じ要素が含まれる場合は定義されない，とします．
例えば，(A, B) と (C, D) の (A, C) による「連結」の結果は (A, B, C, D) となります．また，(A, B) と (C, B) の (A, C) による連結は，(A, B) と (C, B) で B が重複するため，このような連結は定義しません．
以上の表記を用いて問題に対するアルゴリズムを述べます．トーナメントの参加人数をNとします．Nは2の整数べきです．
まず，勝敗表から (勝つ人, 負ける人) という2要素の順序付き集合を全て作る．この集合を $S_1$ とおく．今，k = 1 として以下を繰り返す．

$S_k$ の任意の異なる2つの要素を x, y とし， $S_1$ の任意の要素を z とする．x と y の z による連結を考え，その演算結果が定義されるようなものを全て列挙し，その演算結果の集合を $S_{k+1}$ とする．
k <- k + 1
$k = \log_2 N$ ならば4へ，それ以外ならば1へ戻る．
$S_{\log_2 N}$ の要素のうち，x で始まるものが x が優勝するトーナメントを表す．以下でd.y.d.の具体例でアルゴリズムを動かして見ます．

k=1

勝敗表に対応する2要素の順序付き集合を全て列挙します．
(A, B), (A, E), (A, G)
(B, C), (B, F)
(C, A), (C, D), (C, E), (C, F), (C, G)
(D, A), (D, B), (D, E), (D, F), (D, G), (D, H)
(E, B)
(F, A), (F, E)
(G, B), (G, E), (G, F), (G, H)
(H, A), (H, B), (H, C), (H, E), (H, F)
以上が $S_1$ となります．

k=2

$S_1$ の要素の異なる2つと $S_1$ の要素で，連結が可能な組み合わせを全て列挙します．例えば $S_1$ の要素である (A, B) と (G, E) は (A, G) によって連結できて (A, B, G, E) となります．一方，(A, B) と (E, B) の (A, E) による連結は，B が重複するため定義されません．以下，このような連結の結果をすべて列挙します．
(A, B, G, E), (A, B, G, F), (A, B, G, H), (A, E, B, C), (A, E, B, F), (A, E, G, B), (A, E, G, F), (A, E, G, H)
(B, C, F, A), (B, C, F, E), (B, F, C, A), (B, F, C, D), (B, F, C, E), (B, F, C G)
（C および D で始まるのはめちゃくちゃ多いので省略します．E で始まるものはありません．）
(F, A, E, B), (F, E, A, B), (F, E, A, G)
（G と H で始まるのも多いので省略．）
以上が $S_2$ となります．ちなみに A で始まる $S_2$ の要素は，「A を含めた適当な4人で構成された（部分）トーナメントのうち，A が優勝できるもの」を表しています．

k=3

以下同様です．例えば $S_2$ の要素である (A, E, G, H) と (B, F, C, D) は $S_1$ の要素である (A, B) によって連結できて (A, E, G, H, B, F, E, D) となります．
(A, E, G, H, B, F, C, D)
（以下，計算が超面倒だったので省略）
以上が $S_3$ となります．
$k=log_2 8$ なのでここで終了します．

結果

$S_3$ の要素のうち，A で始まるもの，つまり (A, E, G, H, B, F, C, D) が A が優勝できるようなトーナメントの組み合わせで，実際d.y.d.で紹介されている結果です．このアルゴリズムにおいて， A が優勝できるようなトーナメントとして出力されるのはこれだけです．

いろいろ

要するに単純なDP．このアルゴリズムが十分であることは容易に証明可能なはず．必要かどうかは分からない．多分必要もO.K.だと思うんだけれどにゃー．計算量的には全然考えてないけれど，最悪で $N^4 \cdot \log N$ ぐらい？少なくとも指数にはならないよ〜な気がする．要素の重複チェックでもう1個 $\log N$ がかかるかも．
ちなみにNが2のべきじゃなくてシードがあったりすると，優勝させたい者とシードの組み方全てを試さないとならないはず．少なくとも優勝させたい者を単純にシードにすれば良いと言うことはない（反例がすぐ見つかる）．
間違ってたらごめんなさい．眠いので寝る．おやしみ．
＃ありゃ？ $N^6\cdot \log N$ か？
＃って，途中の演算結果が膨れ上がって指数入るんじゃないかこれ？む〜むむむ．
＃いや，やっぱりめちゃくちゃ緩く見積もっても $N^{3\log N}\cdot\log N$ で，ぎりぎり指数じゃないよ〜な？
＃ちげーよ． $N^{3^\log N}$ だよ．これだと思いっきり指数だよ．なんかうまい上限見つかるかにゃー？
＃って，この程度じゃやっぱ全然ダメダメかにゃー．他のアプローチ考えるべきか？
＃で，ムダに時間を浪費してたら誰かにさらっと「NP-complete でしたよ」と言われたりしたりして．あるあるｗｗｗｗ
＃優勝させたい候補が given だから pruning ができるけれど，それで指数じゃなくなるかと言えば……う〜？