まずは最も短くなるときの長さを求める.

ヤバさ \(i\) のバイナリの最小の長さを \(f(i)\) とすると,

\[f(i) = \min_k \{ f(i - k^2) + k \}\]

という DP でこれを求めることができる.

次にバイナリを作成するために DP を復元する. 辞書順最小にするためにはできるだけ 0 が続く部分が前に来るように, そうでなければできるだけ 1 が続く部分が後ろに来るように選べばいい. これを実現させるには, 長さが奇数となる分割を選べるときにはなるべく小さい奇数を選ぶ. そうでないときにはなるべく大きい偶数, なるべく小さい偶数, なるべく大きい偶数, と交互に選ぶ.