SRM 522 div1 med:CorrectMultiplication

問題

TopCoder Statistics - Problem Statement

解法

とりあえず 1 * 1 = 1 なので 答えは a+b+c-3 に抑えることが出来ます。

また, a <= b とすると, 明らかに A <= B となる方が得です。この時, A の値は 10^5 程度に抑えられます。
A の値をとある一つの値に決めた時, あと B と C の値を決定する必要がありますが, c に合わせるほうが得です(b に合わせると, c から C の値が A ( >= 1) ずれるが, c に合わせると b から B の値は たかだか 1 しかずれない)。

よって, B の値は c/A + o (-1 <= o <= 1) だけを試せば良いです。

class CorrectMultiplication {
public:
    long long getMinimum(int a, int b, int c) {
        if (a > b) swap(a, b);
        ll ret = (ll)a+b+c-3;
        for (ll A = 1; A <= 100000; A++) {
            for (int o = -1; o <= 1; o++) {
                ll B = c/A+o;
                if (B <= 0) continue;
                ll C = A*B;
                ret = min(ret, abs(A-a)+abs(B-b)+abs(C-c));
            }
        }
        return ret;
    }
};