以下のような貪欲法があります。

• ある駒を今より低い頂点に移動させる方法であって、移動中と移動後のポテンシャルの最大値が最小になるようなものを実行する

ただし、高さ \(( H_i\) の値 \()\) が等しい頂点があった場合、適当に順序を付けます。

この貪欲法を始状態と終状態の両方から並行してポテンシャルの最大値の小さい順に行い、はじめて始状態からと終状態からの駒の位置がすべて一致したとき、それまでのポテンシャルの最大値の最大値が答えです。

優先度付きキューを用いることで \(O(NK\log N)\) の計算量で解くことができます。

さらに、適切な前処理をしておき、同じ頂点にある駒の移動をまとめて行うことで \(O(N\log N+K)\) の計算量で解くことができます。

正当性の説明

駒のある頂点の場所の組を”状態”と呼ぶことにします。

• ポテンシャルの上限を決め打ったとき、状態 \(A\) と \(B\) に対してそれぞれこの貪欲法を行ったとき最終的に得られる状態が等しいならば、\(A\) と \(B\) がその状態を経由することで互いに遷移可能なことが分かります。遷移は双方向に可能なことに注意してください。
• ポテンシャルの上限を決め打ったとき、状態 \(A\) と \(B\) に対してそれぞれこの貪欲法を行ったとき最終的に得られる状態は、\(A\) と \(B\) が互いに遷移可能ならば等しいです。
  （証明：貪欲法によって最終的に得られる状態は、各駒が到達しうる頂点のうち最も低いものに置かれている状態です。これは、各ステップがある駒を現在より低い頂点に移動させる操作であることと、各駒の置かれた頂点の高さがどれも高くならないため一度可能になった駒の移動がその後不可能になることはないことから従います。\(A\) と \(B\) が互いに遷移可能なことから、各駒が到達しうる頂点の集合は \(A\) からはじめても \(B\) からはじめてもすべて等しいため、貪欲法によって最終的に得られる状態も等しいです。）

よって、ポテンシャルの上限を決め打ったとき、始状態と終状態に対してそれぞれこの貪欲法を行ったとき最終的に得られる状態が等しいことと、始状態と終状態が互いに遷移可能なことが同値です。先のアルゴリズムは、ポテンシャルの上限を決め打って確かめ、続けて上限を少し大きくして同じことを繰り返していると考えれば妥当であることが分かります。