今回は不参加のためゆっくりと復習。
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が同じなのに。