結果

問題 No.130 XOR Minimax
ユーザー codershifth
提出日時 2015-08-14 23:30:44
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 39 ms / 5,000 ms
コード長 2,404 bytes
コンパイル時間 1,487 ms
コンパイル使用メモリ 163,564 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-12 22:35:53
合計ジャッジ時間 2,900 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned long long ull;

#define FOR(i,a,b) for(int (i)=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define RANGE(vec) (vec).begin(),(vec).end()

using namespace std;


class XorMinMax {
public:
    void solve(void) {
            int n;
            cin>>n;
            vector<int> a(n);
            REP(i,n)
                cin>>a[i];

            // 先頭からみていく。 k ビット目が全ての A[i] で 0 or 1 なら
            // x の k ビット目は 0 or 1 に確定する。
            //
            // そうでないとき x の k ビット目を 0 or 1 にするかで場合分けがあるが、
            // どれかの A[i] xor x の k ビット目は 1 にせざるを得なくてそれがどの A[i]
            // かで場合わけすることになる。
            //

            // 事前にソートしておく
            sort(RANGE(a));

            // a[i..j] の k ビット目以下の xor での最小値
            function<int(int,int,int)> calc = [&](int i, int j, int k) {
                if (k < 0)
                    return 0;
                int ii;
                for (ii = i; ii <= j; ++ii)
                    if (a[ii] & 1<<k)
                        break;

                // 全て 0 bit or 全て 1 ビットのとき。 k ビット目は 0 に確定する
                if (ii == i || ii == j+1)
                    return calc(i, j, k-1); // bit をずらして再帰

                // k   [     0      ]
                // k+1 [  0  ][  1  ]
                // k+2 [ 0][1][ 0][1]
                //  :
                // a を各区間に順次分割していくことになるが
                // ソートしているので a[i..j] の k+1 ビット目までは全て同じになっていて
                // 再帰的にこの性質が保たれる。
                //
                // 前後で分割して試す
                return min(calc(i, ii-1, k-1), calc(ii, j, k-1)) + (1<<k); // (1<<k) は足すざるを得ない
            };
            // 10^9 が最大なので 30 ビット目あたりからみていけばよい
            cout<<calc(0, n-1, 30)<<endl;
    }
};

#if 1
int main(int argc, char *argv[])
{
        ios::sync_with_stdio(false);
        auto obj = new XorMinMax();
        obj->solve();
        delete obj;
        return 0;
}
#endif
0