SRM496 Div1 Medium

500

2部マッチングの個数にしかみえなくて絶望。

経過した秒数 D の数はたかが知れている。
D を決め打ちしたとすれば、2部グラフが作れる。

+D 秒後と -D 秒後の 2 つしかマッチさせる候補がないので
あるマッチングの連結成分の右側と左側の頂点の個数は
R == L
R + 1 == L
R == L + 1
の3パターンしかない。

R == L のマッチングの個数は 1 通り
R + 1 == L はどこの入次数を 2 にするかで L 通り
R == L + 1 は成り立たない。

後は、連結成分ごとのパターン数の積を計算する。

class OneDimensionalBalls {
public:
  long long countValidGuesses(vector <int> F, vector <int> S)
  {
    vector<int> diff;
    for (int i = 0; i < F.size(); ++i) {
      for (int j = 0; j < S.size(); ++j) {
        diff.push_back(abs(F[i] - S[j]));
      }
    }
    sort(diff.begin(), diff.end());
    diff.erase(unique(diff.begin(), diff.end()),    diff.end());
    diff.erase(remove(diff.begin(), diff.end(), 0), diff.end());

    sort(F.begin(), F.end());
    sort(S.begin(), S.end());

    lli ret = 0;
    for (int d = 0; d < diff.size(); ++d) {
      cout << diff[d] << endl;
      vector<lli> v;
      set<int> vis_F;
      set<int> vis_S;
      for (int i = 0; i < F.size(); ++i) {
        if (vis_F.count(F[i])) continue;
        int prev_F = vis_F.size();
        int prev_S = vis_S.size();
        vis_F.insert(F[i]);
        queue<int> q;
        for (q.push(F[i]); q.size(); q.pop()) {
          int n = q.front();
          int e[] = {n - diff[d], n + diff[d]};
          int f[] = {n - 2 * diff[d], n + 2 * diff[d]};
          for (int j = 0; j < 2; ++j) {
            if (binary_search(S.begin(), S.end(), e[j])) {
              vis_S.insert(e[j]);
              if (binary_search(F.begin(), F.end(), f[j]) && !vis_F.count(f[j])) {
                q.push(f[j]);
                vis_F.insert(f[j]);
              }
            }
          }
        }
        int diff_F = vis_F.size() - prev_F;
        int diff_S = vis_S.size() - prev_S;
        if (diff_F == diff_S) v.push_back(1);
        if (diff_F + 1 == diff_S) v.push_back(diff_S);
        if (diff_F == diff_S + 1) v.push_back(0);
      }
      ret += accumulate(v.begin(), v.end(), 1, multiplies<int>());
    }

    return ret;
  }
};