概要
いくつかの部屋に別れて試験を行う。
試験に一人の教官と 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; } };