公式解説 では，「悪いマスが存在しないときにちょうど \(w\) マス進めるか？」という部分問題を DP により解いていました．ここでは，別の方法を紹介します．

ちょうど \(w\) マス進める必要十分条件は， \(w \leq \lfloor w/A \rfloor B\) と表されます．この条件は，以下のようにして導出されます．

ちょうど \(k\) 回の操作で移動できるマスは， \(kA\) から \(kB\) の間のすべてのマスです．逆に，移動できるすべてのマス \(w\) に対して，ある正整数 \(k\) が存在して \(kA \leq w \leq kB\) が成り立ちます．\(kA \leq w\) を満たす最大の \(k\) は \(k^*=\lfloor w/A \rfloor\) であり，この \(k^*\) に対して \(w \leq k^* B\) が成り立つかどうか判定すればよいです．この条件はすなわち \(w \leq \lfloor w/A \rfloor B\) です．

実装例 (Python)