全試合をやらずに順位を決められる?

近所の腕相撲大会を思い浮かべてください。実力には明確な序列があり、強い選手は弱い選手に必ず勝ちます。 でも時間が足りず全員が対戦できず、一部の結果のみが記録されました。

幸い手がかりが1つ。「AがBに勝ち、BがCに勝った」なら——AとCが対戦していなくても、AはCに勝つと確信できます。実力序列が一貫しているからです。

例: 選手5人、記録された結果は P1>P2, P1>P3, P2>P4, P3>P4, P4>P5。順位が確定する選手は3名。 (P1・P4・P5は確定、P2・P3は未対戦で未確定)

問題はこれです。記録された試合だけで、他の全選手との勝敗がすべて決まり、正確な順位が定まる選手は何人でしょう?

なぜフロイド-ワーシャル? (核心アイデア)

「A→B→C なら A→C」というルール、どこかで見ませんでしたか? それがグラフの到達性(reachability)です。結果を矢印として読むと(a→b = aがbに勝つ)、「iはjに勝つか?」は 「iからjへの経路があるか?」 とまったく同じ問いになります。

私たちは全ペアについてこれを知る必要があります。だから、すべての点からすべての点への関係を一度に埋める道具——フロイド-ワーシャルがぴったりです。

ただ1か所だけ変えます。通常のフロイド-ワーシャルは距離を足し、最小を取ります。

•通常: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
•ここでは論理OR: win[i][j] = win[i][j] OR (win[i][k] AND win[k][j])

意味は *「iがkに勝ち、kがjに勝てば、iもjに勝つ」* ——まさに探していた推移規則です。距離行列を勝敗(到達)行列に置き換えれば、フロイド-ワーシャルは推移閉包(transitive closure)の計算機になります。

順位が「確定」するとは?

行列を埋めたあと、ある選手iを見ます。他の選手jごとに、win[i][j](自分が勝つ)か win[j][i](自分が負ける)のどちらかが1なら、その相手との勝敗を知っているという意味です。

•他のN-1人全員との勝敗を知っていれば → その選手の位置は一意に確定。
•一人でも両方向とも0なら(未対戦で推移でも繋がらない) → その2人の相対順位が決められず未確定。

例ではまさにP2とP3がそれです。両者ともP4・P5に勝ちP1に負けますが、互いの勝敗だけが不明で、結局順位が定まりません。

自分の目で確かめる

試合結果が行列に埋まり、経由選手kを1つずつ替えながら win[i][k] && win[k][j] で新しい勝敗が点灯し、最後に選手ごとに「全員との勝敗を知っているか?」を集計する全工程をステップ別の可視化で用意しました。k・i・jと decided カウントの変化まで一目で分かります。

👉 トーナメント順位決定 — ステップ別の可視化で解法を見る

この「距離の代わりに到達関係を埋める」発想は、友人関係の追跡、前後関係(トポロジカル)判定、部品の互換性など無数の変形で登場します。一度原理を目で覚えれば、どんな姿で出ても解けます。