WARush

SRMの結果とか、解けた問題のコードを書いていきます

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;
    }
};