CodeJam 2014:如何解决"新彩票游戏"任务？

Question

我想知道新彩票游戏问题的有效方法.

彩票正在改变!彩票曾经有一台机器来生成随机中奖号码.但由于作弊问题,彩票公司决定增加另一台机器.新的中奖号码将是两台机器生成的两个随机数之间的按位与运算的结果.

要找到X和Y的按位AND,请将它们写成二进制; 然后,如果X和Y的相应位都是1,则二进制结果中的一位有1,否则为0.在大多数编程语言中,X和Y的按位AND写为X和Y.

例如:旧机器生成数字7 = 0111.新机器生成数字11 = 1011.中奖号码将是(7和11)=(0111和1011)= 0011 = 3.

通过这一措施,彩票公司希望减少欺诈性索赔的案件,但不幸的是,彩票公司的一名员工泄露了以下信息:旧机器将始终生成小于A的非负整数,新的机器将始终生成小于B的非负整数

卡塔利娜想要赢得这个彩票并试一试,她决定购买低于K的所有非负整数.

鉴于A,B和K,Catalina想知道机器可以通过多少种方式生成一对数字,这将使她成为赢家.

---

对于小输入,我们可以检查所有可能的对,但如何使用大输入.我想我们首先将二进制数表示为字符串然后检查排列,这将给出小于的答案K.但我似乎无法弄清楚如何计算2个二进制字符串的可能排列.

Answer 1

我使用了一种通用的DP技术,我在另一个答案中详细描述了这种技术.

我们想要计算对(a,b)使得a <A,b <B和a&b <K.

第一步是将数字转换为二进制,并通过添加前导零将它们填充到相同的大小.我只是将它们填充到40的固定大小.这个想法是逐步建立有效的a和b.

令f(i,loA,loB,loK)为大小为40-i的a和b的有效后缀对的数量.如果loA为真,则意味着直到i的前缀已经严格小于A的相应前缀.在这种情况下,a的下一个可能位没有限制.如果loA为假,则A [i]是我们可以放在当前前缀末尾的下一位的上限.loB和loK有类似的含义.

现在我们有以下过渡:

long long f(int i, bool loA, bool loB, bool loK) {
  // TODO add memoization
  if (i == 40)
    return loA && loB && loK;
  int hiA = loA ? 1: A[i]-'0';  // upper bound on the next bit in a
  int hiB = loB ? 1: B[i]-'0';  // upper bound on the next bit in b
  int hiK = loK ? 1: K[i]-'0';  // upper bound on the next bit in a & b
  long long res = 0;
  for (int a = 0; a <= hiA; ++a)
    for (int b = 0; b <= hiB; ++b) {
      int k = a & b;
      if (k > hiK) continue;
      res += f(i+1, loA || a < A[i]-'0',
                    loB || b < B[i]-'0',
                    loK || k < K[i]-'0');
    }
  return res;
}

结果是f(0,false,false,false).

如果添加了memoization以确保每个子问题仅解决一次,则运行时为O(max(log A,log B)).