TopCoder SRM 580, Division 2, Level 1 : ShoutterDiv2

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12578&rd=15500

概要

N 匹のうさぎについて、部屋に入ってくる時刻と退出する時刻の情報が与えられる。
一瞬でも同時に部屋にいたうさぎ同士は友達同士になる。
友達同士のペアがいくつできるか求めよ。

解法

二匹のうさぎの取り方について全探索し、それぞれについて時刻の区間がオーバーラップするかどうか判定をします。
初見では区間交差の判定が面倒だったのでいもす法にしましたが、もっと楽にできるのでそっちのコードも載せます。

コード（いもす法）

typedef vector<int> VI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define ALL( c ) (c).begin(), (c).end()

class ShoutterDiv2
{
public:
	int count( vector <int> s, vector <int> t )
	{
		const int N = s.size();
		int res = 0;

		REP( i, 0, N )
		{
			REP( j, i + 1, N )
			{
				VI ary( 101 );
				ary[ s[i] ] ++;
				ary[ t[i] + 1 ] --;
				ary[ s[j] ] ++;
				ary[ t[j] + 1 ] --;

				VI csum;
				partial_sum( ALL( ary ), back_inserter( csum ) );

				res += find( ALL( csum ), 2 ) == csum.end() ? 0 : 1;
			}
		}

		return res;
	}
};

コード（楽なの）

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

class ShoutterDiv2
{
public:
	int count( vector <int> s, vector <int> t )
	{
		const int N = s.size();
		int res = 0;
		REP( i, 0, N )
		{
			REP( j, i + 1, N )
			{
				res += !( t[j] < s[i] || t[i] < s[j] );
			}
		}
		return res;
	}
};