abc 188 F - +1-1x2 (python)

気づくこと
一回でも x を操作する途中で２倍した後は、二回連続で +1, -1 を使わない。
理由
p 回 +1 した後に、２倍して q 回 +1 すると、
(x + p)*2 + q = 2x + 2*p + q
q ≧ 2 のとき 2x + 2*p + q = 2x + 2*p + 2*s + t(s ≧１, t は 0 or 1) となり
p + s 回 +1 してから２倍して 0 または 1 回 +1 した方が
p + s + t < p + 2*s + t = p + q となるので少ない回数で同じ結果を得ることができる。

そこで Y から X を作ることを考える。そうすると考察から、
Y から X を作る時の最適な操作は、
X : 偶数　X → X/2 (x' とする)
X : 奇数　X → X+1 or X-1 → (X+1)/2 or (X-1)/2 (x' とする)
という操作で X から x' を作り、また x' を X と操作することを繰り返し、最後の÷２の操作の後は、|Y-x'| 回 +1 か -1 を適当に行えば求まる。

よって f (y) : y から X を作るのにかかる最小回数とすれば、
f (y) = min( f(y+1/2)+2, f(y-1/2)+2, |y-X| )　y : 奇数のとき
f (y) = min( f(y/2)+1, |y-X| ) y : 偶数のとき
のように遷移する
あとは終了条件に y = 1 のときを書いておいたらおわり。

import sys
sys.setrecursionlimit(10**7)
from functools import lru_cache
X,Y = map(int,input().split())

@lru_cache(maxsize=None)
def f(y):
  global X
  if y == 1:
      return abs(1-X)
  elif y%2 == 1:
    return min(f((y+1)//2)+2,f((y-1)//2)+2,abs(y-X))
  else:
    return min(f(y//2)+1,abs(y-X))    
            
print(f(Y))