mayoko’s diary

プロコンとかいろいろ。

SRM 519 div1 easy:BinaryCards

SRM519の練習会に参加しました。今回はeasyもmedも難しい印象です(easyに関しては僕だけかも)。

解法

とりあえず気づかないといけないのは,ある数xからx+1に変わる時カードをひっくり返すことによって得られる最大の数は(x or (x+1))となるということです。

ということで,B-Aの最大値が10^9程度だったらこれだけで愚直解が通る勢いです。ただ,今回はB-Aの最大値は10^18なので流石にそれだけでは通りません。

そこで,最大値になるような状況を考えます。サンプルを見てるとなんとなくわかりますが,例えば7から8になる場合,
0111 と 1000 のorを取ることになりますが,こうすると1111になって最強っぽいです。他にも,11から12になる場合,
1011 と 1100 のorを取ることになりますが,これは1111となります。
要するに何が言いたいかというと,

????1111 とかなってるのと
???10000 となっているもののorを取ると大きくなるということです。

?の部分のところはなるべく大きくしておくのが得なので?をなるべく大きくしながら上のような状況になっている数を探します。それで得られた数が答えです。

class BinaryCards {
public:
    long long largestNumber(long long A, long long B) {
        if (B-A < 1000000) {
            ll ret = A;
            for (ll i = A; i < B; i++) {
                ret = max(ret, (i|(i+1)));
            }
            return ret;
        }
        ll mini = 0;
        int index = 0;
        for (int i = 0; i < 64; i++) {
            if ((1ll<<i) > B) break;
            index = i;
            mini = 1ll<<i;
        }
        if (mini-1 >= A) return (mini | (mini-1));
        for (int i = index-1; i >= 0; i--) {
            if (mini-1 >= A) {
                return (mini | (mini-1));
            } else {
                if (mini + (1ll<<i) <= B) mini += (1ll<<i);
            }
        }
        return (mini-1) | mini;
    }
};