\(L_i :=\) 部屋 \(i, i+1\) を繋ぐ廊下を渡るのに必要な鍵がある部屋 \(j\) のうち、 \(j \leq i\) であるような最大の \(j\)

と定義されるような \(L\) 、また同じように右の部屋について考える \(R\) を作っておきます。この情報を用いて、今部屋 \([l, r)\) を通行できるという状態で通行できる部屋を左右に拡張できるかを定数時間で判定できます。ここまでにかかる計算量は \(\mathrm{O}(N + \sum_{k=1}^{N} B_k)\) です。

\(i = 1,2, \cdots ,N\) について順に、はじめ部屋 \([i, i+1)\) を通行できる状態から限界まで区間を広げた状態を求めるアルゴリズムは、単純な実装では最悪で \(\mathrm{O}(N^2)\) の時間がかかります。

ランダムな \(N\) 要素の順列 \(P\) を用意して \(P_1, P_2, \cdots ,P_N\) の順で区間を広げた結果を求めていくアルゴリズムを考えます。\(P_i\) からの拡張の過程で部屋 \(x\) にたどりついたとしたら、はじめ部屋 \([x, x+1)\) を通行できる状態から限界まで拡張した区間に含まれる部屋については全て \([P_i, P_i + 1)\) から始めても通れることがわかります。そのため、もし \(P_j=x\) であるような \(j\) が \(j < i\) であれば、枝狩りをすることができます。ランダムな \(P\) を適切に用意することで、十分高速です。