POJ 3283 - Card Hands

http://poj.org/problem?id=3283

概要

n 人分のカードの集合をそれぞれ連結リストで管理している．

共通の tail を持っている場合，その部分を共有することでノード数を減らしてメモリを節約できるようになる．

与えられたデータを持つのに必要な最小のノード数を答える．

制約

解法

後ろからトライ木を作ってノード数を数えればいい．

真面目にトライ木を作るのが面倒だったので map でやったら 1000MS でギリギリ通った．

 1 #include <iostream>
 2 #include <vector>
 3 #include <map>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 int c2i(const string& s)
 8 {
 9   int n;
10   switch (s[s.size()-1]) {
11     case 'C': n = 0;  break;
12     case 'D': n = 1;  break;
13     case 'H': n = 2;  break;
14     case 'S': n = 3;  break;
15     default:  throw s;
16   }
17   n *= 13;
18   switch (s[0]) {
19     case 'A': n += 1; break;
20     case '2' ... '9': n += s[0]-'0';  break;
21     case '1': n += 10;  break;
22     case 'J': n += 11;  break;
23     case 'Q': n += 12;  break;
24     case 'K': n += 13;  break;
25     default: throw s;
26   }
27   return n;
28 }
29 
30 struct trie
31 {
32   map<int,trie> m;
33   typedef vector<int>::const_iterator Iterator;
34 
35   void insert(Iterator it, const Iterator& last)
36   {
37     if (it == last) {
38       return;
39     }
40     const int n = *it;
41     ++it;
42     m[n].insert(it, last);
43   }
44 
45   int size() const
46   {
47     int r = 1;
48     for (map<int,trie>::const_iterator it = m.begin(); it != m.end(); ++it) {
49       r += it->second.size();
50     }
51     return r;
52   }
53 };
54 
55 int main()
56 {
57   ios::sync_with_stdio(false);
58   int N;
59   while (cin >> N && N != 0) {
60     trie t;
61     for (int i = 0; i < N; i++) {
62       int K;
63       cin >> K;
64       vector<int> cards;
65       for (int i = 0; i < K; i++) {
66         string s;
67         cin >> s;
68         cards.push_back(c2i(s));
69       }
70       sort(cards.rbegin(), cards.rend());
71       t.insert(cards.begin(), cards.end());
72     }
73     cout << t.size()-1 << endl;
74   }
75   return 0;
76 }
poj/3283.cc