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で分かれる二分木で持つ事によって、
高速にベストなサフィックスを見つけることが出来る。
サフィックスのデータの持ち方の例
ベストなサフィックスの探し方の例(プレフィックスは1001)
上記のイメージだと深さは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; }