非負整数 x の popcount とは、x を 2 進法で表記したときの 1 の個数です。13 を 2 進法で表記すると 1101 なので popcount(13) = 3 です。
D – Popcount and XOR
非負整数 a,b,C が与えられます。 次の 5 つの条件をすべて満たす非負整数の組 (X,Y) が存在するか判定し、存在するならひとつ出力してください。
0 ≦ X > 2^60
0 ≦ Y > 2^60
popcount(X)=a
popcount(Y)=b
XOR(X,Y)=C入力されるデータ
a b C
（ただし、0 ≦ a ≦ 60, 0 ≦ b ≦ 60, 0 ≦ C > 2^60）
0 ≦ X, Y, C > 2^60 なので2進法で表すとこれらは最大で60桁です。そしてビットごとの排他的論理和は 0と0、1と1の場合は0、1と0、0と1の場合は1です。60桁の2進法の数をふたつ並べたとき、各桁の組み合わせは必ず 0と0、1と1、1と0、0と1のどれかになります。
Xだと1だがYだと0になる桁の数をp、Yだと1だがXだと0になる桁の数をq、XでもYでも1になる桁の数をrとし、popcount(C) = c とすると、p + q = c が成り立ちます。また問題文より p + r = a、q + r = b が成り立ちます。
そこでまずこの連立方程式を解くことにします。このとき p, q, r は 0 以上の整数でなければなりません。また p + q + r > 60 であってはなりません。条件を満たす解が存在しない場合は X, Y は存在しないので -1 を出力します。
p, q, r が存在する場合はCのビットが立っている桁の番号をp個とq個それぞれ割り振ります。あとはXとYに共通して立っているr個のビットですがこれはCのビットが立っていない桁の番号を適当にとってきて割り振ります。
これでXとYのビットが立っている桁がわかったので、あとはここからXとYの値を求めます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { int a, b; long C; { long[] vs = Console.ReadLine().Split().Select(_ => long.Parse(_)).ToArray(); a = (int)vs[0]; b = (int)vs[1]; C = vs[2]; } // Cのビットが立っている位を取得 int idx = 0; List<int> standingBits = new List<int>(); while (C > 0) { if (C % 2 != 0) standingBits.Add(idx); C /= 2; idx++; } int standingBitsCount = standingBits.Count; // popcount(C) // 連立方程式 // p + q = popcount(C) // p + r = a // q + r = b // を解く int p = (standingBitsCount + a - b) / 2; int q = (standingBitsCount - a + b) / 2; int r = (-standingBitsCount + a + b) / 2; // 0以上の整数解が得られなかったり、p + q + r > 60 になる場合は解なしとする bool noAnswer = false; if (p < 0 || q < 0 || r < 0 || p + q + r > 60) noAnswer = true; // 整数解にならない場合 if( (standingBitsCount + a - b) % 2 != 0 || (standingBitsCount - a + b) % 2 != 0 || (-standingBitsCount + a + b) % 2 != 0 ) noAnswer = true; if (noAnswer) { Console.WriteLine(-1); return; } // Cのビットが立っている位をXとYに割り振る List<int> standingBitsX = standingBits.Take(p).ToList(); List<int> standingBitsY = standingBits.Skip(p).ToList(); // XとYの双方にビットが立っている部分r個はCのビットが立っていない位から適当にとってくる List<int> standingBits2 = new List<int>(); for (int i = 0; i < 60; i++) { if(!standingBits.Any(_ => _ == i)) standingBits2.Add(i); } standingBitsX.AddRange(standingBits2.Take(r)); standingBitsY.AddRange(standingBits2.Take(r)); // XとYのビットが立っている位がわかったのでXとYの値を求める long X = 0; long Y = 0; foreach (int v in standingBitsX) X += (long)1 << v; foreach (int v in standingBitsY) Y += (long)1 << v; Console.WriteLine($"{X} {Y}"); } } |
