TopCoder SRM 799 : Div1 Easy CapriciousSorting

またMedium落としたけど、1Chalのお陰でレートは増。
https://community.topcoder.com/stat?c=problem_statement&pm=15460&rd=18494

問題

整数列Aが与えられる。
2^30未満の非負整数Xを選び、全要素A[i] = A[i] xor Xとして値を更新したとする。
更新後の数列が真に単調増加であるためには、Xは何通り選べるか。

解法

Aの隣接要素A[i]とA[i+1]を比較しよう。
異なるビットのうち最上位のものを2^bとする。

• もしA[i]が2^bのビットが立っていて、A[i+1]が立っていないなら、Xは2^bのビットが立っていなければならない。
• もしA[i+1]が2^bのビットが立っていて、A[i]が立っていないなら、Xは2^bのビットが立っていてはならない。

これらの条件を列挙すると、Xの各ビットで取りえる値が定まるので、そのビット毎の組み合わせの積を取ろう。

class CapriciousSorting {
	public:
	int count(vector <int> num) {
		int i,j;
		vector<int> ok(30,3);
		FOR(i,num.size()-1) {
			if(num[i]==num[i+1]) return 0;
			for(j=29;j>=0;j--) {
				if((num[i]&(1<<j))!=(num[i+1]&(1<<j))) {
					if(num[i]&(1<<j)) ok[j]&=2;
					else ok[j]&=1;
					break;
				}
			}
		}
		ll ret=1;
		for(i=29;i>=0;i--) ret*=__builtin_popcount(ok[i]);
		return ret;
		
	}
}

まとめ

本番はもっとややこしいことをやってしまった。
まぁ1Chalのお陰でタイムロスはほぼ関係なかったのだけども。