No.643 Two Operations No.2
No.643 Two Operations No.2 - yukicoder
考察
xとyの比を取って、p = x/yと置くとx=yにするということはp=1にするということと同値であることが分かります。
（ただし、y=0のときはp=∞であると考えることにします。また(x, y) = (0, 0)は少し特殊なので無いものとします）
このpで与えられた各操作を考えてみると、
- 操作1:p -> 1/p
- 操作2:p -> (p+1)/(p-1)
にすることであるということが計算によって分かります。この操作を繰り返してp=1にするゲームだと思えばいいことになります。
p=1に1ステップで行ける状態を考えてみます。操作1は1を1にするだけなので考えてもしょうがないです。操作2は(p+1)/(p-1)=1となるpを求めることになりますが本来ならそのようなpは存在しません……
ですがp=∞とすると、（∞+1)/(∞-1) = ∞/∞ = 1なのでp=∞からp=1へは１ステップで行けることが分かりました。（この計算は本当はめちゃくちゃなので、元の(x,y)で計算して確かにこれが正しいことを示す必要があります）
次にp=∞に1ステップで行ける状態を考えてみます。操作1を考えると1/0=∞なので0から１ステップで行けます。操作2を考えると分母が0になるpということなのでp=1から操作2で１ステップで行けます。（本当はめちゃくちゃ）
さらにp=0に1ステップで行ける状態。操作1では1/∞=0なので∞から0へ１ステップで。操作2ではp=-1のとき分子が0になるので、-1から0へ１ステップで。
さらにp=-1に1ステップで行ける状態。操作1では明らかに-1から-1。操作2では(p+1)/(p-1)=-1を解くと、p=0。0から-1へ１ステップ。
ここで状態がもう増えなくなったので結局どういうことになっているかをグラフにまとめると以下のようになっています。
よって、与えられた(x,y)からpを求めて、それがこのグラフに乗っていればその最短距離を返す。
これ以外の点であれば、これらの操作を繰り返してもp=1に到達することはできないので-1を返します。
感想
とても難しい★２だと思いました。コンテスト中には解けませんでしたが……楽しかったです。
この考え方は、testestestさんがまとめていてくれている「射影空間へうつす」という奴に対応しているはずでそれを使うと今回の議論が正当化できるはずです……多分。
