POJ 1119 - Start Up the Startup

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

概要

まず検索クエリとして単語の集合が与えられる。 そして検索対象として、いくつかの文章(単語の集合)が与えられ、それぞれに対してスコアを計算して答える。

スコアは検索クエリ中の各単語 \(w\) に対して、\(\sqrt{(検索クエリ中の w の数) \times (文章中の w の数)}\) の和とする。

単語は空白で区切られた文字列から、英数字のみを取り出したものとする。 英数字以外のみからなる文字列の場合は空文字列が取り出されてしまうので、これをカウントしてはならない。

制約

• 文章は100行以下
• 一行は250文字以下

解法

やるだけ。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <sstream>
 4 #include <vector>
 5 #include <map>
 6 #include <cmath>
 7 #include <cctype>
 8 using namespace std;
 9 
10 string f(const string& s)
11 {
12   string t;
13   for (string::const_iterator it = s.begin(); it != s.end(); ++it) {
14     if (isalnum(*it)) {
15       t += toupper(*it);
16     }
17   }
18   return t;
19 }
20 
21 void words(map<string, int>& dict, const string& line)
22 {
23   istringstream iss(line);
24   for (string w; iss >> w;) {
25     const string v = f(w);
26     if (!v.empty()) {
27       ++dict[v];
28     }
29   }
30 }
31 
32 int main()
33 {
34   static const string TERM = "----------";
35   map<string, int> dict;
36   for (string line; getline(cin, line) && line != TERM;) {
37     words(dict, line);
38   }
39   for (string line; getline(cin, line) && line != TERM;) {
40     map<string, int> d;
41     words(d, line);
42     while (getline(cin, line) && line != TERM) {
43       words(d, line);
44     }
45     double score = 0.0;
46     for (map<string, int>::const_iterator it = dict.begin(); it != dict.end(); ++it) {
47       score += sqrt(it->second * d[it->first]);
48     }
49     printf("%.2f\n", score);
50   }
51   return 0;
52 }