初回考察

切る切らない2^Nは、Nが10^5とか大きいのでダメ

2NのDPになる？

無理そう

一旦最大限に長く刻んで、その刻みを1つずつ前に移動するスタイルではどうか

しゃくとり法的な、解のありそうなところだけを探索するアプローチ

下限が徐々に上がっていく、下限より小さくなるところは探索しなくても良いので割と探索空間小さめにならないかなー

公式解説

続きあり、一旦この後自分で考えてから。