POJ 1761 - Easy Task

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

概要

あるコンテストにおける N 回の提出の記録が時系列順に与えられるので，各問題に対して

• その問題を AC したチームの数
• その問題を AC したチームの，その問題を AC するまでに提出した回数の平均
• その問題を AC したチームの，その問題を AC した時刻の平均

を答える．

既に AC した問題に対する提出は単に無視する．

問題は A から I まである．

制約

• 1 <= n <= 2000

解法

数えるものが若干ややこしいが，単に言われた通りに数えるだけ．

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <map>
 4 using namespace std;
 5 
 6 int main()
 7 {
 8   int N;
 9   cin >> N;
10   map<char, map<string, int> > accepted;
11   map<char, map<string, int> > submits;
12   for (int i = 0; i < N; i++) {
13     int t;
14     string s;
15     char p, r;
16     cin >> t >> s >> p >> r;
17     if (!accepted[p].count(s)) {
18       ++submits[p][s];
19       if (r == 'A') {
20         accepted[p].insert(make_pair(s, t));
21       }
22     }
23   }
24 
25   for (char p = 'A'; p <= 'I'; p++) {
26     const map<string, int>& ac = accepted[p];
27     const map<string, int>& s = submits[p];
28     const int n = ac.size();
29     printf("%c %d", p, n);
30     if (n == 0) {
31       putchar('\n');
32     } else {
33       int elapsed = 0;
34       int subs = 0;
35       for (map<string, int>::const_iterator it = ac.begin(); it != ac.end(); ++it) {
36         elapsed += it->second;
37         subs += s.find(it->first)->second;
38       }
39       printf(" %.2f %.2f\n", double(subs)/n, double(elapsed)/n);
40     }
41   }
42   return 0;
43 }