SRM723 Lv1 : TopXorer
作成日：2017.11.19
最終更新日：2017.11.19
問題概要
$n$人のチームを作る。
各人は非負整数のレートを持っており、$i$人目のメンバーのレートは$x_i$以下でなければならない。
チームを構成するメンバーのレートの$xor$を最大化せよ。
制約
$1 \leq n \leq 50$
$0 \leq x_i \leq 10^9$
考え方
2進数で上の桁から決めていくことを考える。
$x$の要素で$2^i$以上であるものは存在するが、すべて$2^{i+1}$未満であるとする。
この時1人のレートを$2^i$にして残りの人のレートを$0$にすることができることから、答えは$2^i$以上であることが分かる。
$x$の要素で$2^i$以上のものが$x_j$の1つである時は、$j$人目のレートの$2^i$の位が$1$であることが決まる。
この時、残りの桁を考える時には$2^i$の位は考えなくて良いから、$x_j$を$x_j - 2^i$として考え直せば良い。
$x$の要素で$2^i$以上のものが2つ以上ある時は、1人のレートを$2^i$にすると同時に他の一人のレートを$2^i - 1$とすることができる。
残りの人のレートを$0$にして$xor$をとると$2^{i+1} - 1$となるが、これ以上の解が得られないことは明らかである。
以上の考察から答えを求めることができる。
ソースコード
マクロ等はこちら
class TopXorer {
public:
int maximalRating(vector<int> x) {
int n = x.size();
int ans = 0;
repm(i,30,-1){
int z = (1<<i);
bool b = 0;
for(auto &u : x){
if(u < z) continue;
if(b){
ans += z-1;
break;
} else {
ans += z;
u -= z;
b = 1;
}
}
}
return ans;
}
};解法まとめ
$x$の要素で$2^i$以上であるものは存在するが、すべて$2^{i+1}$未満であるような$i$を取ってくる。
$2^i$以上の要素が$x_j$の1つである時、答えの$2^i$の位は$1$で、それより小さい位は$x_j$を$x_j - 2^i$に置き換えて考えた時の答えと同じである。(14-16行)
$2^i$以上の要素が2つ以上ある時は、答えの$2^i$の位以下の位はすべて$1$である。(12,14行)
SRM723の他の問題 Lv2 Lv3