WARush

SRMの結果とか、解けた問題のコードを書いていきます

SRM677 Div1 Easy "DoubleOrOneEasy"

解法

青いボタンを何回使ったかで全探索するとよい。
青いボタンをn回使ったとすると、aは2^n * aとなり、あとは、赤いボタンをnewA - 2^n * a 回だけ押せばよいことになる(この回数をxと置く)
bの方も同じように2^n * bとなり、赤いボタンはnewB - 2^n * b 回だけ押せばよいことになる(この回数をyと置く)
この時、x = yとなっていれば、赤いボタンと青いボタンを同じ回数だけ押したときにnewA, newBとなるため、問題の条件をクリアする。

で、青いボタン⇒赤いボタンと順番をまとめてしまうと押す数が最小回数とならない。
例えばnewA = 2^3 * a + 9となった場合。順番をまとめると青いボタン3回・赤いボタン9回で12回押すことになるが、赤いボタンをまず1回押しておいて、それから青いボタンを3回押す。(これにより赤いボタンを8回押した効果が得られる)それから赤いボタンを1回押せば、最小で済む。つまり、2^3 * a + 9 を 2^3 * a + 2^3 + 2^0ととらえると、青いボタン3回・赤いボタン2回となって5回で済む。また例えば、newA = 2^4 * a + 15となった場合、2^4 * a + 15 を 2^4 * a + 2^3 + 2^2 + 2^1 + 2^0ととらえると、青いボタン4回・赤いボタン4回となる。赤いボタンの効果を青いボタンで上手いこと増幅してあげるようにボタンを押すとよい。

ソースコード

class DoubleOrOneEasy {
    public:
    int minimalSteps(int a, int b, int newA, int newB) {
        long long pow2 = pow(2, 30);
        for (int blue = 30; blue >= 0; blue--) {
            long long x = static_cast<long long>(newA) - a * pow2;
            if (x >= 0) {
                long long y = static_cast<long long>(newB) - b * pow2;
                if (x == y) {
                    int red = 0;
                    while (pow2 != 0) {
                        red += x / pow2;
                        x %= pow2;
                        pow2 /= 2;
                    }
                    return blue + red;
                }
            }
            pow2 /= 2;
        }
        return -1;
    }
};