SRM580 Div2 Easy 「ShoutterDiv2」
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12578
訳
新入生であるウサギ達はウナギクラブに入ろうとしていた。このグループには誰一人、知り合いはいなかった。今日、初めてウサギ達はクラブに参加する。あなたはint[]のsとtが与えられる。s[i]はi番目のウサギがクラブに顔を出した時間であり、t[i]はi番目のウサギがクラブを立ち去った時間である。
それぞれのウサギのペアは、同じ時間にクラブにいれば、お互いを知る事になり、彼らは"Shoutter"というソーシャルネットワークサービスで友達登録をする。瞬間に一緒にいることになったケースでもこれは当てはまる。(例えば、一匹がクラブに入り、一匹がその瞬間クラブを出た場合でも)
何ペアが友達登録するのかを返せ。
制約
1 <= ウサギの数 <= 50
1 <= s[i], t[i] <= 100
考えた事
時間が100までと少ないので、ある時間で何ペアできるのか数えていく。
ソースコード
class ShoutterDiv2 { public: int count(vector <int> s, vector <int> t){ int n = s.size(); int res = 0; int num = 0; for( int time = 0; time <= 100; time++ ){ int add = 0; int rem = 0; for( int i = 0; i < n; i++ ){ if( s[i] == time ){ add++; } if( t[i] == time ){ rem++; } } res += num * add; res += add * (add - 1) / 2; num += add - rem; } return res; } };