こういう貪欲に突き進む処理を書くの、実はかなり苦手かもしれない

問題概要

$N$ 個の 0 以上の整数 $a_{1}, \dots, a_{N}$ が与えられる。上手に正の整数 $X$ を選ぶことで、

$X$ XOR $a_{1}$
$X$ XOR $a_{2}$
...
$X$ XOR $a_{N}$

の値の最大値の最小値を求めよ。

制約

$1 \le N \le 10^{5}$

考えたこと

最小値を求めたいということで、一番上の桁から順に辞書順に決めていく。まず一番上の桁 $d$ 桁目について、

$N$ 個の整数について、 $d$ 桁目がすべて 1 なら、丸ごとすべて 0 にできる
すべて 0 なら、そのままで丸ごとすべて 0 にできる

ということがわかる。そうでない場合には、

0 の組を 1 にする代わりに、1 の組は 0 にする (このとき、1 の組のことはケアする必要がなくなる)
1 の組を 1 にする代わりに、0 の組は 0 にする (このとき、0 の組のことはケアする必要がなくなる)

という二択がある。いずれの場合も、答え res にとりあえず (1<<d) を加算した上で、

「0 の組」のみに index を絞って次の桁へ進む場合
「1 の組」のみに index を絞って次の桁へ進む場合

を両方試して、小さい方を採用すれば OK。計算量は実のところ、再帰が分岐していったとしても、どの桁についても結局 $N$ 個の整数を一個ずつなめていくことになるので、 $O(N\log{A})$ となる ( $A$ は $a$ の最大値)。

 #include <iostream>
#include <vector>
using namespace std;

int N;
vector<long long> a;

// a のうち ids で表される index のものについて、d 桁目について考える
long long rec(int d, const vector<int> &ids) {
    if (d < 0) return 0;

    // d 桁目が 1 のやつと 0 のやつ
    vector<int> one, zero;
    for (auto i : ids) {
        if (a[i] & (1LL<<d)) one.push_back(i);
        else zero.push_back(i);
    }

    // どちらかが空なら d 桁目を 0 にできる
    if (one.empty() || zero.empty()) return rec(d - 1, ids);

    // そうでないなら d 桁目は 1 にする代わりに次回以降を絞る
    else return (1LL<<d) + min(rec(d-1, one), rec(d-1, zero));
}
 
int main() {
    cin >> N;
    a.resize(N);
    for (int i = 0; i < N; ++i) cin >> a[i];
    vector<int> ids(N);
    for (int i = 0; i < N; ++i) ids[i] = i;
    cout << rec(50, ids) << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

Codeforces #613 (Div. 2) D. Dr. Evil Underscores (R1800)

問題概要

制約

考えたこと