ヒント

人 \(1\) は単独優勝する可能性があるか？ \(\cdots(*)\)

という問題をある程度早く解ければ、これを \(N\) 回解くことで元の問題を解くことができます。

想定解では、\((*)\) を 最大フロー を用いて解きます。

ここまでのヒントで、グラフを色々作ってみて \((*)\) が解けるかどうか試してみることをお勧めします。

解答

人 \(p\) は単独優勝する可能性があるか？

という問題を、最大フローを用いて解きます。

まず、人 \(p\) の試合のうち結果が分かっていないものについては、人 \(p\) が勝ったとして良いです。
人 \(p\) の勝利数を \(win\) とします。\(win=0\) のときは単独優勝できないので、以下 \(win \geq 1\) とします。

頂点 \(S,T,A_{i,j}( 1\leq i\lt j\leq N),B_i (1\leq i \leq N)\) を用意します。
\(S\) が始点、 \(T\) が終点で、\(A_{i,j}\) は人 \(i,j\) の試合、\(B_i\) は人 \(i\) を意味しています。

辺は全て容量 \(1\) として、以下のように張ります。

• \(S \rightarrow A_{i,j}\) に \(1\) 本

• 人 \(i,j\) の試合について、

  • \(i\) が勝ちなら、\(A_{i,j} \rightarrow B_i\) に \(1\) 本
  • \(j\) が勝ちなら、\(A_{i,j} \rightarrow B_j\) に \(1\) 本
  • 試合をしていないなら、\(A_{i,j} \rightarrow B_i\) と \(A_{i,j} \rightarrow B_j\) に \(1\) 本

• \(B_p \rightarrow T\) に \(win\) 本

• \(B_i(i\neq p) \rightarrow T\) に \(win-1\) 本

このグラフにおける \(S\) から \(T\) への最大フローが \(\frac{N(N-1)}{2}\) であることが、人 \(p\) が単独優勝する可能性があることの必要十分条件です。

このグラフは辺の容量が全て \(1\) で、辺数が \(O(N^2)\) なので、\(O(N^3)\) で解くことができます。

これを \(p=1,2,\ldots N\) について解くので、問題全体を \(O(N^4)\) で解くことができました。