kmjp's blog

競技プログラミング参加記です

TopCoder SRM 723 Div1 Easy TopXorer、Div2 TopXorerEasy

とてもしょうもない理由でMedium落とした…。
https://community.topcoder.com/stat?c=problem_statement&pm=14736
https://community.topcoder.com/stat?c=problem_statement&pm=14737

問題

N個の整数列X[i]が与えられる。
各要素に対し、0~X[i]の範囲の整数を選んだとする。
こうして選んだN個の整数のxorを取った値で得られる最大値を求めよ。

なおDiv2ではN=3固定である。

解法

各整数X[i]について、2進数で最上位桁のビットを2^kとする。
解に2^kを入れようとすると、以下の値は(X[i]-2^k)以下で選ばなければならないが、2^kを入れないようにすれば以下のビットは任意に選択できる。

よって以下の手順で解の最上位ビットから選んでいこう。
今(2^k)が解に含められるか考えるとき、X中そのような値がいくつあるか見ていこう。

  • 0個ならそのビットは立てられない
  • 1個ならそのビットは立てた上で、そのX[i]から2^kを引く
  • 2個以上ならそのビットは立てた上で、以降のビットも立てられる

以下のコードは2個以上ある場合はX[i]を(2^k)-1に置き換える処理をしており、上の記述と異なるが得られる解は同じ。

class TopXorer {
	public:
	int maximalRating(vector <int> X) {
		int N=X.size();
		int ret=0;
		int i,j;
		for(i=29;i>=0;i--) {
			int id=-1;
			FOR(j,N) {
				if(X[j]&(1<<i)) {
					if(id==-1 || X[id]<X[j]) id=j;
				}
			}
			if(id>=0) {
				ret |= 1<<i;
				X[id]^=1<<i;
				FOR(j,N) {
					if(X[j]&(1<<i)) {
						X[j]=(1<<i)-1;
					}
				}
			}
		}
		return ret;
	}
}

まとめ

Codeforcesに出そうな問題。