No.130 XOR Minimax

No.130 XOR Minimax - yukicoder

• 解説を読んでもパッとソートが必要な理由(ソートしてうまく行く理由)がわからなかった。
• 事前にソートしておくことで分割を繰り返しても先頭 k ビット目が一致しているって条件が担保できるのか。

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;
    }
};