\(k\) を固定したとき、どの経路も下に移動する回数がちょうど \(k\) 回で等しいため、右に移動する回数の最小値が分かれば良いです。

移動方法として、下に移動できるなら下に移動し、できないなら右に移動することを繰り返す戦略が最善です。右への移動の回数を最小化するとき、右への移動はどの行でも同じようにできることから、必要に迫られるまで右に移動する必要がないことに因ります。 これによって、始点を固定すれば移動経路が一意に定まるようになりました。

始点の左からの位置と終点の左からの位置の組 \(W\) 通りを管理しながら、\(k\) の昇順に計算して行きます。 \(k\) 回目の処理では、終点が \(A_k\) 以上 \(B_k\) 以下であるすべての組に対して終点を \(B_k+1\) に変更したのち、終点から始点を引いた値の最小値を答えます。ただし \(B_k=W\) のとき、終点は \(W+1\) ではなく\(\infty\) に変更します。

この操作はセグメント木によって処理することもできますが、セグメント木を用いず順序集合を用いて処理することもできます。

一度終点が等しくなった二つの組はその後も終点が等しいため、その中で始点が最も大きいものだけを残して他は以降無視して良いです。(終点,始点)のペアのsetと終点から始点を引いた値のmultisetを持ち、前述のように不要になった要素を随時削除しつつ更新していけば、計算量は全体で \(O((H+W)log(H+W))\) になります。