Cutting Logs

まず、$3, 6, 9 ...$ と $3$ の倍数の小さい数の長さの順に袋の中に入れていくことが最適なのは明らかです。
ここで、次のような判定問題を考えます。

• $K$ 個以上の丸太を袋に入れることができるか。

この判定問題は二分探索を用いて容易に実装することができます。
$3, 6, 9 \: ... \: 3K$ と続く数列の総和は、等差数列の和の公式より、 $3K(1 + K) ÷ 2$ と一つの式で表すことができるので、高速に計算できます。

よって、この問題を十分高速に解くことができました。