No.642 Two Operations No.1

No.642 Two Operations No.1 - yukicoder

考察

とりあえず整数を頂点、操作を辺としてグラフにしてみると以下のような感じになります。

頂点数はNで辺の数は2Nなので、N <= 10^6程度ならこのグラフで頂点1からBFSをすることで
最短距離（最小操作回数）が求められますが、今回はN <= 10^9なのでもう少し工夫しないといけないようです。

頂点iへの最短距離をdist(i)と書くことにします。

グラフをよく見てみると、奇数の頂点は１つ大きい数からしか到達できないのでi = 2k + 1とすると、dist(2k + 1) = dist(2k + 2) + 1となっていることが分かります。

問題は偶数の頂点で、この頂点には辺が２つ入ってきます。なので
dist(2k) = min(dist(k), dist(2k+1)) + 1
と書けます。何となく、小さいケースでいくつか試してみると、常にdist(k) <= dist(2k+1)が成り立っているような気がします。

実際に、頂点2kの周りとkの周りの関係を書いてみると以下のようになります。

もしここで、dist(k) > dist(2k+1)が成り立っていたとしたら最短路を逆順にたどっていくと、2k -> 2k+1 -> 2k+2までは一直線に進みます。ここでまた分岐するのですが、もしここで2k+2 -> k+1と戻る枝を使ったとすると、結局k+1から3ステップで2kに来ることになるので、dp(2k) = dp(k+1) + 3となります。（下図赤線）
一方で、k+1 -> k -> 2kと高々2stepで行くことができるので、dp(2k) <= dp(k+1) + 2であることが分かります。（下図青線）
これは矛盾しているので、2k+2 -> k+1と戻る枝を使ったことは誤りとなります。

なのでさらにさかのぼって2k -> 2k+1 -> 2k+2 -> 2k+3 -> 2k+4と行ってまた枝分かれするんですが、ここでも2k+4 -> k+2と戻る枝を使うと仮定すると矛盾が起こることが同様に分かります。

よって帰納的にこのようなことが示せてしまうので、結果的にはそもそもdist(k) > dist(2k+1)と仮定していたこと（つまり2k <- 2k+1が最短路に含まれていたと仮定したこと）が誤りであるということが言えます。よってdist(k) <= dist(2k+1)なので、「2kに行くにはkから来る枝を使う」としていいことが分かります。

上の議論によって何が言えるかというと、

• nが奇数のときは、n+1に戻ればよい
• nが偶数のときは、n/2に戻ればよい

ということなので、後はこれをn = 1になるまで繰り返せばよいということになります。2回に1回はnが半分になるので計算量的にもだいたいO(logN)なのでこれで十分間に合うということが分かります。

感想

難しい★２だと思いました。