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

問題ページ
Trie木を考える．上の桁(Trie木の浅い方)から順番に見て，0にできるならば必ず0にするべきである ( $2^n \gt 2^{n-1} + \cdots + 2^1 + 2^0$ なので)．

上から $i$ 桁目に0しかない: $X$ の $i$ 桁目を0にすれば答えの $i$ 桁目を0にできる
上から $i$ 桁目に1しかない: $X$ の $i$ 桁目を1にすれば答えの $i$ 桁目を0にできる
上から $i$ 桁目に0,1の両方ある
このときどうやっても答えの $i$ 桁目は1になる． $X$ の $i$ 桁目を 0(もしくは1) にすると $i$ 桁目が 0(もしくは1) であるような数が最大値となることはない．

上から $i$ 桁目(深さ $i$ ) で0,1の両方の辺が存在する場合にどちらに進めばよいのか考える．これはできるだけ浅い位置に子が一つの頂点が存在する方向に進むべきである．各頂点の子孫で，子が一つであるような頂点が存在する深さの集合がわかれば，どちらに進むべきかわかる．この集合をbitでもちながらTrie木上をdfsすると，各頂点でどちらに進むべきか求めることができる．あとは進む方向に応じて， $X$ の $i$ 桁目を0,1のどちらにするべきかがわかるので解けた．

非想定であろう解法を書いたら実装がひどいことになった…
どちらに進んでも子が一つの頂点が同じ深さに存在するパターン抜かしてて時間溶かした

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
using PII = pair<ll, ll>;  
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)  
#define REP(i, n) FOR(i, 0, n)  
#define ALL(x) x.begin(), x.end()  
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }  
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
#ifdef DEBUG_   
#include "../program_contest_library/memo/dump.hpp"  
#else  
#define dump(...)  
#endif  
const ll INF = 1LL<<60;  
  
template <int types = 26>  
struct Trie {  
    struct node {  
        ll idx;  
        vector<ll> next;  
        vector<ll> matched;  
        node() : idx(0), next(types, -1) {}  
    };  
  
    using F = function<int(char)>;  
    vector<node> nodes;  
    int sz; // 文字列の種類数  
    int root;  
    F trans;  
  
    // 初期化  
    Trie() {}  
    Trie(vector<string> pattern, F f = [](char c){return c-'0';})  
    : nodes(1), sz(pattern.size()), root(0), trans(f) {  
        build(pattern);  
    }  
    // 文字列集合patternからtrie木を構築  
    void build(vector<string> pattern) {  
        int now;  
        REP(i, pattern.size()) {  
            ll idx = 1;  
            now = root;  
            for(const auto &c: pattern[i]) {  
                if(nodes[now].next[trans(c)] == -1) {  
                    nodes.push_back(node());  
                    nodes.back().idx = idx;  
                    nodes[now].next[trans(c)] = nodes.size() - 1;  
                }  
                now = nodes[now].next[trans(c)];  
                idx++;  
            }  
            nodes[now].matched.push_back(i);  
        }  
        dp.resize(nodes.size());  
        dep.resize(nodes.size());  
        way.resize(nodes.size());  
    }  
     
    vector<ll> dp, dep, way;  
    ll dfs0(ll v, ll d) {  
        dep[v] = d;  
        ll num = 0, ret = 0;  
        REP(i, types) if(nodes[v].next[i] != -1) {  
            num++;  
            ll tmp = dfs0(nodes[v].next[i], d+1);  
            bool cond = false;  
            REP(j, 31) {  
                if((ret&1LL<<j) && !(tmp&1LL<<j)) {  
                    cond = false;  
                    break;  
                }  
                if(!(ret&1LL<<j) && (tmp&1LL<<j)) {  
                    cond = true;  
                    break;  
                }  
            }  
            if(cond) {  
                ret = tmp;  
                way[v] = i;  
            }  
        }  
        dp[v] = ret;  
        if(num == 1) ret |= 1LL<<d;  
        return ret;  
    }  
  
    ll ans = 0;  
    void dfs1(ll v, ll pw) {  
        vector<ll> ch;  
        REP(i, types) if(nodes[v].next[i] != -1) ch.push_back(i);  
  
        if(ch.size() == 1) {  
            if(ch[0]==1) {  
                ans |= pw;  
            }  
            dfs1(nodes[v].next[ch[0]], pw/2);  
        } else if(nodes[v].next[way[v]] != -1) {  
            if(way[v]==0) {  
                ans |= pw;  
            }  
            dfs1(nodes[v].next[way[v]], pw/2);  
        }  
    }  
};  
  
int main(void) {  
    ll n;  
    cin >> n;  
    vector<ll> a(n);  
    REP(i, n) cin >> a[i];  
    auto b(a);  
  
    vector<string> s(n);  
    REP(i, n) {  
        string t = "";  
        while(a[i] > 0) {  
            t += a[i]%2 + '0';  
            a[i] /= 2;  
        }  
        reverse(ALL(t));  
        t = string(31-t.size(), '0') + t;  
        s[i] = t;  
    }  
    Trie<2> tree(s);  
  
    tree.dfs0(0, 0);  
    tree.dfs1(0, 1LL<<30);  
  
    ll ret = 0;  
    REP(i, n) chmax(ret, b[i]^tree.ans);  
    cout << ret << endl;  
  
    return 0;  
}

最大値になりうる数の集合を保持しつつ，各桁が0の要素と1の要素で集合を分割するというdfsをすると実装がとても簡単になる．

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
using PII = pair<ll, ll>;  
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)  
#define REP(i, n) FOR(i, 0, n)  
#define ALL(x) x.begin(), x.end()  
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }  
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
#ifdef DEBUG_   
#include "../program_contest_library/memo/dump.hpp"  
#else  
#define dump(...)  
#endif  
const ll INF = 1LL<<60;  
  
int main(void) {  
    ll n;  
    cin >> n;  
    vector<ll> a(n);  
    REP(i, n) cin >> a[i];  
  
    function<ll(ll,vector<ll>)> dfs = [&](ll d, vector<ll> ids) {  
        if(d < 0) return 0LL;  
        vector<ll> id0, id1;  
        for(auto i: ids) {  
            if(a[i]&1LL<<d) id1.push_back(i);  
            else id0.push_back(i);  
        }  
        if(id0.empty() || id1.empty()) return dfs(d-1, ids);  
        return (1LL<<d) + min(dfs(d-1, id0), dfs(d-1, id1));  
    };  
  
    vector<ll> ids(n);  
    iota(ALL(ids), 0);  
    cout << dfs(29, ids) << endl;  
  
    return 0;  
}

ferinの競プロ帳

競プロについてのメモ

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