読者です 読者をやめる 読者になる 読者になる

TopCoder SRM 699 Div1 Easy: OthersXor

問題

N 匹の狼が 0〜2^30-1 の中の数字から 1 つずつ数字を選んでそれぞれ持っています。各狼は「黙秘する」か「自分以外の全ての狼の数字のXOR」かのどちらかを教えてくれます。

教えてもらった情報から、全狼の数字の合計の最小値を求めてください。

解法

30 個のビットそれぞれについて以下の問題を考えます。

N人の人がいて、1か0の数字を持っています。「自分以外の合計が奇数である」と主張する人と、「自分以外の合計が偶数である」と主張する人と、何も言わない人がいます。条件を満たす最小の合計を求めてください。

この場合、全体の合計が偶数だと仮定すると、「自分以外の合計が奇数である」と主張する人の人数が奇数であれば、彼ら全員に1を持たせ、人数が偶数であれば、何も言わない人を1人連れてきて人数を奇数にすることで条件を満たせます。

偶数だと仮定した場合と、奇数だと仮定した場合の2回試せば良いです。

コード

public class OthersXor {

  public long minSum(int[] x) {
    long ans = 0;
    for (int bit = 0; bit < 30; bit++) {
      int othersOdd = 0;
      int othersEven = 0;
      int mutual = 0;
      for (int y : x) {
        if (y < 0) mutual++;
        else if ((y & (1 << bit)) != 0) othersOdd++;
        else othersEven++;
      }

      int best = Integer.MAX_VALUE;

      // すべての合計が奇数とした時
      if (othersOdd % 2 == 0) best = Math.min(best, othersOdd);
      else if (mutual > 0) best = Math.min(best, othersOdd + 1);

      // すべての合計が偶数とした時
      if (othersEven % 2 == 1) best = Math.min(best, othersEven);
      else if (mutual > 0) best = Math.min(best, othersEven + 1);

      if (best == Integer.MAX_VALUE) return -1;
      ans += ((long) best << bit);
    }

    return ans;
  }
}