零完しました。$x’ = f(x) = x \ll i + j$の$i$を総当たればよいのは気付いていたが、その先をDPだと思い込んでしまっていた。

Easy: DoubleOrOneEasy

問題

正整数の対$(a,b)$が与えられる。 以下の変換を用いて$(a’,b’)$を作るとき、必要な変換の操作の回数の最小値はいくらか。

  • $(x,y)$を$(x+1,y+1)$に変換する。
  • $(x,y)$を$(2x,2y)$に変換する。

解法

一連の変換操作は、$(x,y)$から$(f(x),f(y))$への変換で、$f(x) = x \ll i + j$と表せる。 この$i$、つまり答えとなる変換の中の2倍する回数について総当たりする。

$i$を固定すると$j$が定まる。これは$a,b$で一致しなければならない。 ここで答えは$i+j$ではない。$i$回のshift演算を使って$j$を効率的に作れるからである。 下位$i$-bitはshiftにより$1$回のincrementで作れ、それより上のbitの部分$j \gg i$はincrementをそれ自身の回数$j \gg i$回用いなければならない。

実装

#include <bits/stdc++.h>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
typedef long long ll;
using namespace std;
class DoubleOrOneEasy {
public:
    int minimalSteps(ll a, ll b, ll newA, ll newB);
};

int DoubleOrOneEasy::minimalSteps(ll a, ll b, ll newA, ll newB) {
    ll result = INT_MAX;
    repeat (i,32) {
        if (newA - (a<<i) == newB - (b<<i)) {
            ll j = newA - (a<<i);
            if (j < 0) continue;
            result = min(result, i + (j >> i) + __builtin_popcount(j & ((1ll<<i) - 1)));
        }
    }
    return result == INT_MAX ? -1 : result;
}