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 は成り立たない。

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

view plainprint?

1. class OneDimensionalBalls {  
2. public:  
3.   long long countValidGuesses(vector <int> F, vector <int> S)  
4.   {  
5.     vector<int> diff;  
6.     for (int i = 0; i < F.size(); ++i) {  
7.       for (int j = 0; j < S.size(); ++j) {  
8.         diff.push_back(abs(F[i] - S[j]));  
9.       }  
10.     }  
11.     sort(diff.begin(), diff.end());  
12.     diff.erase(unique(diff.begin(), diff.end()),    diff.end());  
13.     diff.erase(remove(diff.begin(), diff.end(), 0), diff.end());  
14.   
15.     sort(F.begin(), F.end());  
16.     sort(S.begin(), S.end());  
17.   
18.     lli ret = 0;  
19.     for (int d = 0; d < diff.size(); ++d) {  
20.       cout << diff[d] << endl;  
21.       vector<lli> v;  
22.       set<int> vis_F;  
23.       set<int> vis_S;  
24.       for (int i = 0; i < F.size(); ++i) {  
25.         if (vis_F.count(F[i])) continue;  
26.         int prev_F = vis_F.size();  
27.         int prev_S = vis_S.size();  
28.         vis_F.insert(F[i]);  
29.         queue<int> q;  
30.         for (q.push(F[i]); q.size(); q.pop()) {  
31.           int n = q.front();  
32.           int e[] = {n - diff[d], n + diff[d]};  
33.           int f[] = {n - 2 * diff[d], n + 2 * diff[d]};  
34.           for (int j = 0; j < 2; ++j) {  
35.             if (binary_search(S.begin(), S.end(), e[j])) {  
36.               vis_S.insert(e[j]);  
37.               if (binary_search(F.begin(), F.end(), f[j]) && !vis_F.count(f[j])) {  
38.                 q.push(f[j]);  
39.                 vis_F.insert(f[j]);  
40.               }  
41.             }  
42.           }  
43.         }  
44.         int diff_F = vis_F.size() - prev_F;  
45.         int diff_S = vis_S.size() - prev_S;  
46.         if (diff_F == diff_S) v.push_back(1);  
47.         if (diff_F + 1 == diff_S) v.push_back(diff_S);  
48.         if (diff_F == diff_S + 1) v.push_back(0);  
49.       }  
50.       ret += accumulate(v.begin(), v.end(), 1, multiplies<int>());  
51.     }  
52.   
53.     return ret;  
54.   }  
55. };  

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;
  }
};