人 \(i\) を、人 \(i\) の属する国とは 異なる国 に属する人気者と間接的に友達にする

の異なる国がなければ、この問題は多始点の Dijkstra 法で解くことができます。

ここで、国 \(1, 2, \dots, \frac K2\) をグループ A 、国 \(\frac K2 + 1, \dots, K - 1, K\) をグループ B とします。
すると、「グループ A に属する 人 \(i\) を、グループ B に属する 人気者と間接的に友達にする最小コスト」は、同様に多始点の Dijkstra 法で解くことができます。

そこで、グループの分け方を乱択することにします。アルゴリズムは以下のようになります。

以下を \(X\) 回繰り返す。

1. 国 \(1, 2, \dots, K\) をランダムに \(2\) つのグループ A, B に分ける。
2. 「グループ A に属する人 \(i\) を、グループ B に属する人気者と間接的に友達にする最小コスト」を求め、グループ A に属する人 \(i\) の答えを更新する。

人 \(i\) の答えが正しくなるためには、人 \(i\) がグループ A に属し、答えを最小にする人気者が属している国 \(j\) がグループ B に属すことが \(1\) 回でも起これば良いので、その確率は \(1-\left(\frac34\right)^X\) 以上 、

\(N\) 人全員の答えが正しい確率は \((1-\left(\frac34\right)^X)^N \approx 1 - N \times \left(\frac34\right)^X\)

\(N = 10^5\) が \(50\) ケースあるとして、\(X = 80\) とすれば、\(1 - 10^5 \times 50 \times \left(\frac34\right)^{80} \approx 0.9995\) 以上の確率で AC することができます。

決定的アルゴリズムにする

実は、このアプローチを決定的アルゴリズムにすることができます。

すなわち、任意の \((i, j)\ (i ≠ j)\) の組について、国 \(i\) がグループ A に属し、国 \(j\) がグループ B に属すことがあれば良いです。

\(i, j\) がどこかの bit では異なっていることに注目すると、以下のアルゴリズムを作ることができます。

\(b = 0, 1, \dots, 16\) について以下を行う。

1. 国 \(1, 2, \dots, K\) のうち、\(2\) 進表示で \(2^b\) の位が \(0\) であるものをグループ A に、\(1\) であるものをグループ B に入れる。
2. 「グループ A に属する人 \(i\) を、グループ B に属する人気者と間接的に友達にする最小コスト」を求め、グループ A に属する人 \(i\) の答えを更新する。
3. 「グループ B に属する人 \(i\) を、グループ A に属する人気者と間接的に友達にする最小コスト」を求め、グループ B に属する人 \(i\) の答えを更新する。

計算量は \(O((N + M) \log (N + M) \log N)\) です。

出典

https://twitter.com/tatyam_prime/status/1507716009427619840
https://twitter.com/m_99kyopro/status/1507717061325193224