SRM326 D1E-D2M PositiveID

TopCoder Statistics - Problem Statement

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

容疑者の特徴が与えられる．犯人を一意に特定しないようして挙げられる特徴の数を最大化する．犯人が一意に決まらないということは，一番絞られて$2$択の状態となっている．もし最大が$3$択以上となっていても，挙げられる特徴の最大数は変わらないので，$2$人を選べばよいことが分かる．$2$人を選んだ後に，特徴の共通集合のサイズが一意に特定出来ない最大数となるので，それのmaxを取る．

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

#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <set>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

vector<string> split(const string &str, char delim) {
  vector<string> res;
  size_t current = 0, found;
  while((found = str.find_first_of(delim, current)) != string::npos) {
      res.push_back(string(str, current, found - current));
      current = found + 1;
  }
  res.push_back(string(str, current, str.size() - current));
  return res;
}

class PositiveID {

    public:

    int maximumFacts(vector <string> suspects) {
      int n = suspects.size();

      vector<set<string> > v(n);
      rep(i, n) {
          vector<string> ret = split(suspects[i], ',');
          rep(j, ret.size()) {
              v[i].insert(ret[j]);
          }
      }

      int ans = 0;
      rep(i, n) {
          REP(j, i+1, n) {
              int cnt = 0;
              each(it, v[i]) {
                  if(v[j].find(*it) != v[j].end()) {
                      cnt++;
                  }
              }

              ans = max(ans, cnt);
          }
      }

      return ans;
    }
};
Nov 18th, 2016
srm, topcoder