Single Round Match 430 (Div1/250point)

正の整数xとkを与えるのでx + y = x | y となるようなyのうち小さい方からk番目のものを答えなさい、という問題。(説明が楽な問題だ！)

x | yがx + yになるということは要するにx & y == 0ということだから、xとkを両方2進数で表現してxが1の所に0を挿入したkを作ればいい。図で書くとx=5, k=3のとき

k =     1 1
x = 0 1 0 1
y = 1   1

というわけでこんな感じのコードになった。自作ライブラリから整数を二進数のvectorにする関数to_binをコピーした。

vector<int> to_bin(int N){
  vector<int> buf;
  while(N){
    buf.push_back(N % 2);
    N /= 2;
  }
  return buf;
}

class BitwiseEquations {
public:
  long long kthPlusOrSolution(int x, int k) {
    vector<int> kbin = to_bin(k);
    vector<int> xbin = to_bin(x);
    size_t i=0, j=0, p=1;
    LL result=0;
    while(i < xbin.size()){
      if(xbin[i] == 1){
	i++;
	p *= 2;
      }else{
	i++;
	if(j == kbin.size()) break;
	result += p * kbin[j];
	j++;
	p *= 2;
      }
    }
    while(j < kbin.size()){
      result += p * kbin[j];
      j++;
      p *= 2;
    }
    DP(p);
    return result;
  }
}

チャレンジで落とされた。resultはlong longだが、pがintなので桁数が多いとオーバーフローして0になる。

	result += p * kbin[j];
	j++;
	p *= 2;

long longの値を扱うときは大きくなりうる値が他にないか考えないとダメですな。