WARush

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

Codeforces #173 Div2 E "Sausage Maximization"

問題

かの国のソーセージは奇妙な事に、
負ではない整数の配列で表現される。

ソーセージの美味さは、その配列の値をを全てxor演算したのもになる。

例
ソーセージ 1 2
美味さ 3 (1 xor 2)

ソーセージ 1 2 3
美味さ 0 (1 xor 2 xor 3)

今、配列の長さNの1本のソーセージを前からと後ろから切り出して、
2本のソーセージを作る。(ただし、切り出す長さは0でもよい)

2本のソーセージの美味さの合計は、
それらに含まれる整数を全てxor演算したものである。

2本のソーセージの美味さの最大値を返せ。

制約

1 <= N <= 10^5
0 <= ソーセージの整数 <= 10^12

ACしてるソースコードをカンニング
  • 基本的な考察

例えばソーセージの値が
6, 14, 3, 8, 7, 4
だとする。
前(プレフィックス)から6, 14, 3と使うと決めた時、
後ろ(サフィックス)からは最大で8, 7, 4まで使える。

だから、
6, 14, 3 - 8, 7, 4
6, 14, 3 - 7, 4
6, 14, 3 - 4
6, 14, 3 - 0(後ろからは切らない)
の中から一番いい組み合わせを探せばよい。

これを素直に全探索すると、
ざっと見積もっても、
プレフィックスの数(N) * サフィックスの候補数(N)
でO(N^2)= 10^10=100億・・・とても無理。

最大10^5の数にもなるサフィックスの候補から、
ベストなものを素早く選ぶ工夫が必要になってくる。

  • 重要な考察

プレフィックスのxorしたものが 1001 だとして、
ベストなサフィックスは当然 0110 である。
よいサフィックス順に並べてみると
0110
0111
0100
0101
0010
0011
0000
0001
1110
1111
1100
1101
1010
1011
1000
1001
となる。

ここで、上位のビットが優先される事が分かる。
よって、サフィックスの候補をを0と1で分かれる二分木で持つ事によって、
高速にベストなサフィックスを見つけることが出来る。

サフィックスのデータの持ち方の例
f:id:Ekaing:20130315191812j:plain

ベストなサフィックスの探し方の例(プレフィックスは1001)
f:id:Ekaing:20130315194810j:plain

上記のイメージだと深さは4つとなっているが、
サフィックスの最大値10^12(Mとする)を表現するには
ビット数がlogM = 40必要なので、
深さ40の二分木を作れば、おk

これで各プレフィックスのベストなサフィックスを探す計算量がlogMとなり、
全体の計算量はO(NlogM)となる。

注意点として、プレフィックスによって、
サフィックスの候補が変わってくる所。
まずプレフィックスはソーセージ全て使うものから
全く使わないものの順番で調べていき、
その都度、使用できるようになるサフィックスの候補を
二分木に足していけばよい。

ソースコード
typedef long long ll;

class Node{
public:
    Node(){
        next[0] = next[1] = 0; // nullを入れとく
    }
    // next[0] != null bit 0のものが存在する
    // next[1] != null bit 1のものが存在する
    Node* next[2];
};

const int MAX_N = static_cast<int>(1e6);
const int MAX_B = 40; // 10^12を表す最低限のbit数
int n;           // ソーセージの長さ
ll a[MAX_N+1];   // ソーセージの配列(base 1)
ll pre[MAX_N+2]; // 1~i番目までのソーセージの美味さ(プレフィックス)
ll suf[MAX_N+2]; // N~i番目までのソーセージの美味さ(サフィックス)
ll res;
Node* root;

// サフィックス[sid]を追加する
void insert( int sid ){
    ll n = suf[sid];
    
    Node* p = root;
    
    for( int s = MAX_B; s >= 0; s-- ){
        int bit = (n & (1LL << s)) ? 1 : 0;
        if( !p->next[bit] ){
            p->next[bit] = new Node();
        }
        p = p->next[bit];
    }    
}

// 現在のサフィックス状態で、
// プレフィックス[pid]と一番相性の良いものを探し、
// 結果を更新する
void update( int pid ){
    ll n = pre[pid];

    Node* p = root;

    ll best_suf = 0; // ベストなサフィックスの値
    for( int s = MAX_B; s >= 0; s-- ){
        ll good_bit = (n & (1LL << s)) ? 0 : 1; 
        ll not_good_bit = (n & (1LL << s)) ? 1 : 0; 
        if( p->next[good_bit] ){
            p = p->next[good_bit];
            best_suf |= (good_bit << s);
        }else{
            p = p->next[not_good_bit];
            best_suf |= (not_good_bit << s);
        }        
    }

    res = max( res, n ^ best_suf );
}

int main() {
    cin >> n;
    for( int i = 1; i <= n; i++ ){
        cin >> a[i];
    }

    // pre,sufを初期化
    pre[0] = 0;
    for( int i = 1; i <= n; i++ ){
        pre[i] = pre[i-1] ^ a[i];
    }
    suf[n+1] = 0;
    for( int i = n; i >= 1; i-- ){
        suf[i] = suf[i+1] ^ a[i];
    }

    res = 0;
    root = new Node();
    for( int pid = n; pid >= 0; pid-- ){
        // suf[pid+1]を追加
        insert( pid+1 );
        // pre[pid]で最大値を探す
        update( pid );
    }

    cout << res << endl;
}