連続するピースを区間と呼びます。

二分探索を行うことにより、以下の判定問題が（高速に）解ければよいことがわかります。

• \(N\) 個のピースをすべて質量が \(X\) 以上である \(K\) 個の区間に分けられるか
• 分けられるのであれば条件を満たすすべての分け方において切られることのない切り目の個数は何個であるか

各 \(1 \leq i \leq N\) に対し、切り目 \(i\) を切り条件を満たす分け方が存在するか考えます。

\(1 \leq i \leq N\) なる \(i\) について \(A_{N + i} \coloneqq A_i\) と定めることにより \(A\) の長さを \(2N\) とします。

\(A_i + A_{i + 1} + \ldots + A_{j - 1} \geq X\) を満たす \(j (\leq 2N + 1)\) が存在する場合、そのような \(j\) のうち最小のものを \(f(i)\)、存在しない場合 \(f(i) = \infty\) とおきます。また、\(f(\infty) = \infty\) とします。\(f\) の値は尺取り法を用いることで合わせて \(O(N)\) 時間で計算できます。

切り目 \(i\) を切る条件を満たす分け方が存在することの必要十分条件は \(f^K(i + 1) \leq N + i + 1\) であることです。

\(f\) の値から \(f^K\) の値は \(f^2, f^4, f^8, \ldots\) の値を計算していくようなダブリングの要領で \(O(N \log K)\) 時間で計算できます。

したがって、切り目 \(i\) を切る分け方が存在する \(i\) の個数が \(O(N \log K)\) 時間で計算できます。切り目 \(i\) を切る分け方が存在する \(i\) の個数が \(0\) 個でないことと \(N\) 個のピースをすべて質量が \(X\) 以上である \(K\) 個の区間に分けられることが同値であることに注意するとこれにより判定問題を解くことができます。

また、\(f^K\) の値は \(i \neq f(i)\) なる \(i\) に対し \(i\) と \(f(i)\) の間に辺を張って得られる森の Level Ancestor Problem に帰着できるため判定問題を \(O(N)\) で解くこともできます。ただ、writer や tester の実装では実際の実行時間はダブリングを用いた解法より遅くなりました。