SRM649div2hard:XorSequenceEasy

問題:http://community.topcoder.com/stat?c=problem_statement&pm=13657&rd=16313

解法:注目すべき性質は２つ。
①整数の大小関係はbit数の大きいものを優先に決定される
②整数aとbのk番目のbit数が同じであるとすると、k番目のbitが1の整数cを使ってa = a^c, b = b^cとしても大小関係は変化しない
解法のアイデアとしては、「k番目のbitを0にするか1にするか？」ということを考える。これを考える時、考慮しなければならないことは、A[i], A[j](i < j)のk番目のbitが、A[i]とA[j]で異なる最大のbit数であるような(i, j)の組み合わせのみである。なぜかというと、まずkより大きいbit数で大小関係が決定されるものについては性質①より、k番目のbit数は何も影響しない。またkより小さいbit数で大小関係が決定されるものは、k番目のbit数は同じことになるので、性質②より大小関係は変化しない。
よって、解法としては、すべての組み合わせ(i, j)(i < j)について、k番目のbitが、A[i]とA[j]で異なる最大のbit数であるとすると、Bのk番目のbitを1にすることで得になる/ならないで点数をつけて、すべてのbitについてそれを最大化すれば良い。ソースコード見たほうがわかりやすそう。
以下ソースコード

class XorSequenceEasy {
public:
    int getmax(vector <int> A, int N) {
        int n = A.size();
        int K = 0, cur = 1;
        int ret = 0;
        while (cur < N) {
            K++; cur <<= 1;
        }
        vector<int> point(K); // bitを1にした時良くなるスコア
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                if (A[i] < A[j]) ret++;
                for (int k = K-1; k >= 0; k--) {
                    int a = (A[i]>>k) & 1;
                    int b = (A[j]>>k) & 1;
                    if (a != b) {
                        if (a < b) point[k]--;
                        else point[k]++;
                        break;
                    }
                }
            }
        }
        for (int k = 0; k < K; k++) {
            if (point[k] > 0) ret += point[k];
        }
        return ret;
    }
};