Codeforces #235, B : Sereja and Contests

問題文

http://codeforces.com/contest/401/problem/B

問題概要

　あるプログラミングコンテストは、参加者のレベル帯によって二つの Division 、{ Div1, Div2 } に分かれて開催されている。コンテストは、Div1, Div2 が同時に開催されるか、Div2 のみが開催されるかのいずれかである。コンテストにはユニークな ID が振られ、同時に開催された場合の両 Division の ID は隣接する整数である。
　今、次回開催されるコンテストの ID と、過去に参加したコンテスト及びそれと同時に開催されたコンテストの ID が与えられる。Div2 に割り当てられているコンテスタントが参加を逃したコンテストの数の最小値と最大値をそれぞれ求めよ。

解法

　どの Division が開催されたか既知であるような ID を昇順に並べて ys としたとき、 の区間内の ID はどの Division が開催されたか不明です。そのような ID の数は と求まります。この内、全てのコンテストが Div2 だった場合が、参加を逃した回数が最大となるケースであり、できるだけ多い回数 Div1 と同時開催された場合が最小となる場合です。前者の値は自明に d であり、後者は ( d + 1 ) / 2 で求まります。有効な i についてこれらの値それぞれの総和を取ったものが、問題全体でのそれぞれの答えとなります。

コード

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()

#define PB( n ) push_back( n )

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int x, k;
	cin >> x >> k;

	VI as;
	REP( iteration, 0, k )
	{
		int n;
		cin >> n;

		REP( i, 0, 3 - n )
		{
			int a;
			cin >> a;
			as.PB( a );
		}
	}
	as.PB( 0 );
	as.PB( x );
	sort( ALL( as ) );

	int rmin = 0, rmax = 0;
	REP( i, 0, as.size() - 1 )
	{
		const int d = as[ i + 1 ] - as[i] - 1;
		rmin += ( d + 1 ) / 2;
		rmax += d;
	}

	cout << rmin << ' ' << rmax << endl;

	return 0;
}