TopCoder SRM 535 Div1 Medium FoxAndBusiness

想定解と異なる解法でも通ってしまった。
http://community.topcoder.com/stat?c=problem_statement&pm=11454

問題

N人の従業員がいる。
各従業員について、１時間にこなせる仕事量a[i]と仕事１に対し支払う報酬p[i]が与えられる。
ここで、N人中K人を使いtotalWork分の仕事をこなしたい。

K人は総仕事量がtotalWorkに到達するまで、全員同じ時間仕事を行う。
また、かかった時間に対し、１秒あたり１のコストがかかる。

totalWork分の仕事を終えるのにかかるコストを最小化せよ。

解法

こういう「誰から順に利用してよいかよくわからない問題」は何らかの基準でソートするのが定石であり、何度かSRMでもそういう問題が出ている。
Editorialでは機械の動作時間をKとしたときの全員の平均単価Mを仮定し、M*(a[x]+a[y]+...) ≥ a[x]*p[x] + a[y]*p[y] + ... + 3600*Kとなるような条件において、M*a[x]-a[x]*p[x]でソートする手法を紹介している。

ただ、自分は適当に「総コストが小さくなる限り、N人中K人選ぶ従業員を入れ替える」をたくさん繰り返したらそれで通ってしまった。
上記の通り実際は何らかのソート基準があるのだろうと予測し、その基準がわからないが適当に入れ替えれば最適解に行くだろうと思ってやったが、本当にうまくいくとは思わなかった。

class FoxAndBusiness {
	public:
	int W;
	vector<int> A,P;
	double dodo(vector<int> C) {
		double tp=0;
		int i;
		FOR(i,C.size()) tp+=A[C[i]];
		double tim=W/tp;
		double co=tim*3600*C.size();
		FOR(i,C.size()) co+=tim*A[C[i]]*P[C[i]];
		return co;
	}
	
	double minimumCost(int K, int totalWork, vector <int> a, vector <int> p) {
		A=a;
		P=p;
		W=totalWork;
		int N=a.size();
		int i,x,y;
		
		vector<int> C;
		FOR(i,K) C.push_back(i);
		double mi=dodo(C);
		FOR(i,5000) {
			FOR(x,N) {
				if(count(C.begin(),C.end(),x)==1) continue;
				FOR(y,K){
					int h=C[y];
					C[y]=x;
					double nn=dodo(C);
					if(nn<mi) {
						mi=nn;
						break;
					}
					else {
						C[y]=h;
					}
				}
			}
		}
		return mi;
	}
}

まとめ

適当解法でここまでうまく通るとは思わなかった。