SRM 677 Div1 Easy DoubleOrOneEasy

https://community.topcoder.com/stat?c=problem_statement&pm=14101&rd=16627

問題概要

整数a, b, newA, newBが与えられる。 (a, b)に対しそれぞれ同時に+1または*2する操作を繰り返して(newA, newB)に変える時の、操作の最少回数を求める。（変えられないなら-1）

ゆるふわな解法

+1を2回することは*2を1回することと等しいので、一番最初に*2をする前以外で+1を2回以上するのは無駄だよね。 という話から、最初に+1する回数をx、*2をする回数をnとすると、操作は(a * 2^n) + (x * 2^n) + (1or0 * 2^(n-1)) + ... + (1or0 * 2^1) + (1or0 * 2^0)みたいな式で表せることがわかる。
(x * 2^n) + (1or0 * 2^(n-1)) + ... + (1or0 * 2^1) + (1or0 * 2^0)をkとおくと、a * 2^n + k == newA && b * 2^n + k == newBとなる時のnが答えの操作で*2する回数になる。 このnはたかだかlog(newA)<30程度なので1から順に試せばOK。
ちなみに(1or0 * 2^(n-1))以降の1or0の並びはnewA - (a * 2^n) + (x * 2^n)を2進数で表した時と等しくなるので、この部分で+1した回数はpopcountで求められて嬉しい。
計算量O(log(newA))

コード

INT_MAXのところを始めINF(= 1 << 29)にしていて落ちたりした。不注意...
そもそもa==bの時以外はremA==remBになったらすぐreturnしてもいいんだけどね。

#include "bits/stdc++.h"
using namespace std;

const int INF = 1 << 29;

//VSでコーディングしてるので拝借してきました http://www.nminoru.jp/~nminoru/programming/bitcount.html
int popcount(int bits)
{
    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
    bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
    bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
    return (bits & 0x0000ffff) + (bits >> 16 & 0x0000ffff);
}

class DoubleOrOneEasy
{
public:
    int minimalSteps(int a, int b, int newA, int newB)
    {
        int kake = 1;
        int ksum = 0;
        int ans = INT_MAX;
        while (a * kake <= newA && b * kake <= newB)
        {
            int remA = newA - a * kake;
            int remB = newB - b * kake;
            if (remA == remB)
            {
                int tmp = ksum + remA / kake + popcount(remA % kake);
                ans = min(ans, tmp);
            }

            kake *= 2;
            ksum++;
        }

        return ans == INT_MAX ? -1 : ans;
    }
};

解いた問題をブログに上げるというのを初めてやってみたところ、意外と書くのが面倒で解説はもはや分からせる気も厳密に書く気もない感じになってしまった。
この問題はなんとなく競プロしようと思って最近の問題から適当に選んだけど、久しぶりに（自分にとって）やるだけじゃない問題を解いた気がする。
SRM Div1の問題を提出したのは初めてかもしれない。TopCoderとCodeforcesは今までほとんどやって来なかったのでどんどんやっていきたいなあ。

（操作ミスで記事を消してしまったため再投稿です）