Distributed Code Jam Round 1 2017 E. query_of_death

問題

GetValue(i)を呼ぶとi番目の値（0 or 1）が返ってくる。

ただし、あるiを使ってGetValue(i)を呼ぶとシステムが死んでしまう（他のノードに対しては影響はない）。以下ではこのiをi_qodと呼ぶ。

i = 1 〜 NまでのGetValue(i)の和を求めよ。

制約

N <= 10^8

ノード数: 100

解法

semiexp.さんの解法が綺麗。

まずノードをmasterとslaveに分ける。

masterは計算する範囲をslaveに渡す。slaveは与えられた部分問題をといてmasterに返却する。1回目のbatchで1つのslaveが死ぬが、i_qodを含む範囲が1/99に絞られる。続いて2回目のbatchでも1つのslaveが死ぬが、i_qodを含む範囲がさらに1/98に絞られる...というふうに分割統治的に解ける。見ればわかるけど、自分じゃ思いつかない。

ソースコード

// DCJ templates begin
template <typename T>
void PutStruct(int target, const T &v) {
  char *p = (char *) &v;
  for (int i = 0; i < sizeof(T); i++) {
    PutChar(target, p[i]);
  }
}

template <class T>
T GetStruct(int source) {
  char buf[sizeof(T)];
  for (int i = 0; i < sizeof(T); i++) {
    buf[i] = GetChar(source);
  }
  return *((T *)buf);
}
// DCJ templates end

int calc(pair<int, int> pr) {
  int l, r;
  tie(l, r) = pr;

  if (l == r) return 0;
  if (r - l == 1) return GetValue(l);

  int sum = 0;
  for (int i = l; i < r; i++)
    sum += GetValue(i);

  int ck = 0;
  for (int i = 0; i < 50; i++)
    ck += GetValue(l);

  if (ck != 0 && ck != 50)
    return -1;
  return sum;
}

int main() {
  int rank = MyNodeId();
  int NN = NumberOfNodes();
  
  if (!rank) {
    long long L = 0;
    long long R = GetLength();
    set<int> alive;
    int sum = 0;
    
    for (int i = 1; i < NN; i++)
      alive.insert(i);
    
    for (;;) {
      bool update = false;

      vector<int> vs(ALL(alive));
      for (int i = 0; i < vs.size(); i++) {
        int l = L + i * (R - L) / vs.size();
        int r = L + (i + 1) * (R - L) / vs.size();
        PutStruct(vs[i], make_pair(l, r));
        Send(vs[i]);
      }

      for (int i = 0; i < vs.size(); i++) {
        Receive(vs[i]);
        int s = GetInt(vs[i]);
        if (s == -1) {
          update = true;
          int l = L + i * (R - L) / vs.size();
          int r = L + (i + 1) * (R - L) / vs.size();
          L = l, R = r;
          PutStruct(vs[i], make_pair(-1, -1));
          Send(vs[i]);
          alive.erase(vs[i]);
        } else {
          sum += s;
        }
      }
      if (!update)
        break;
    }
    
    for (auto &x : alive) {
      PutStruct(x, make_pair(-1, -1));
      Send(x);
    }
    
    cout << sum << endl;
  } else {
    for (;;) {
      Receive(0);
      auto pr = GetStruct<pair<int, int> >(0);
      if (pr.first == -1)
        break;
      int s = calc(pr);
      PutInt(0, s);
      Send(0);
    }
  }

  return 0;
}