操作の逆を考える． \(f(y) := y / 2 \ (\text{if}\ y \equiv 0 \ mod \ 2)\), \(g_{+}(y) := y + 1\), \(g_{-}(y) := y - 1\). これらの操作で \(Y\) から \(X\) を作ることを考える． 操作 \(f\) のおかげで，小さくしていくので計算量の見積りもし易い． \(O(log Y)\) 程度になることが期待できる． そのためには， \(g_{+}, g_{-}\) の操作をまとめて行いたい．
操作の性質
\(g_{+}, g_{-}\) は連続で行うメリットがない． また，\(g_{+}\) を 2回以上連続で行った後に \(f\) を行うのは， 先に \(f\) を行ったあとに \(g_{+}\) を何回かすることで 操作の回数を減らせる． よって，基本的には \(f, g_{+} or g_{-}\) の繰り返しになる． その前後に \(g_{*}^{k}\), \(* \in \{+, -\}, k \in \mathbb{N}\) を掛けた形にが最善．
\(y\) における答えを \(a_{y}\) とおく． 2で割る操作 \(f\) をある程度行ったあとは， \(g_{+}\) or \(g_{-}\) を連続で繰り返すことになる． よって基本的には，
- \(y \equiv 0\) のとき: \(a_{y} = min(abs(X-y), a_{y}/2 + 1)\)
- \(y \not\equiv 0\) のとき: \(a_{y} = min(abs(X-y), a_{y+1}/2 + 2, a_{y-1}/2 + 2)\)
となる． ただし，このまま再帰で \(a\) を求めると無限ループになる． \(y = 0, y = 1\) だけ個別に求めておく． これらの場合は，\(f\) を用いるメリットが無いので \(abs(X-y)\) が答えとなる．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
