kmjp's blog

競技プログラミング参加記です

TopCoder SRM 569 Div2 Easy TheJediTestDiv2

今回は不参加のためゆっくりと復習。
Div1はEasyもHardも1発Correct出来ず、複数回でCorrectしたので、今回不参加で良かった…。
ではDiv2 Easyから。
http://community.topcoder.com/stat?c=problem_statement&pm=12404

問題

色々ストーリー仕立てしてありわかりにくいので要点のみ。
最大50個の整数値配列と、2つの整数値Y>Jが与えられる。
配列中の各数値を超えるよう、YとJを何度か足し算し、Jを利用した最小回数を答える問題。
Jは何度でも使えるが、Yは全部で1回しか使えない。

解法

配列が高々50個なので、どこか1か所にYを使った場合に、残りの数値にJを使った回数をカウントして最小値を求めればよい。
O(N^2)なので時間は余裕。

class TheJediTestDiv2 {
	public:
	int countSupervisors(vector <int> students, int Y, int J) {
		int ma=99999999,i,j;
		sort(students.begin(),students.end());
		
		FOR(i,students.size()) {
			int to=0;
			FOR(j,students.size()) {
				int s = students[j];
				if(i==j) s -= Y;
				if(s>0) to+=(s+(J-1))/J;
			}
			ma=min(ma,to);
		}
		return ma;
	}

};

まとめ

Div2 Easyのアレンジ版がDiv1 Mediumで出るのって珍しいな。
普段はDiv2 MediumとDiv1 Easyが同じなのに。

広告を非表示にする