とてもしょうもない理由で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に出そうな問題。