torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

TopCoder SRM 569, Division 2, Level 1 : TheJediTestDiv2

概要

いくつかの部屋に別れて試験を行う。
試験に一人の教官と 0 人以上の助手によって監督される。
教官は J 人、助手は Y 人の生徒を監督することが可能であるが、異なる部屋の生徒を監督することはできない。
このとき、全ての生徒を監督するのに必要な助手の再少人数を求めよ。

解法

教官を割り当てる教室を前探索し、全ての場合についてシミュレーションをして最小値を求めると解けます。

コード

typedef vector<int> VI;

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

class TheJediTestDiv2
{
public:
	int countSupervisors( vector <int> students, int Y, int J )
	{
		const int N = students.size();

		int res = INT_MAX;

		REP( i, 0, N )
		{
			res = min( res, test( students, i, Y, J ) );
		}

		return res;
	}

	int test( VI s, int yi, int y, int j )
	{
		s[ yi ] = max( 0, s[ yi ] - y );

		int res = 0;

		REP( i, 0, s.size() )
		{
			res += s[i] / j + ( s[i] % j ? 1 : 0 );
		}

		return res;
	}
};