TopCoderOpen 2017 Round2C Easy CanidsSeesaw

Easyに手間取ったけど、何とか２完してRound3に進出を決めました。
https://community.topcoder.com/stat?c=problem_statement&pm=14651

問題

N匹のオオカミとN匹の狐がおり、互いの重さW[i],F[i]が判明している。
ここで１つのシーソーがあり、互いに１匹ずつ両端に追加で乗せていく。
その際、両者の大きさはシーソーの長さに比べ十分小さく、実質総重量の大きい側にシーソーが傾く。

１匹乗せるたびに総重量が重い側が１ポイント得るとする。
オオカミがシーソーに乗る順番はすでに決まっている。
狐の乗る順番を任意に選択できるとき、狐側がKポイント取る並び方はあるか。
あるならその一例を示せ。

解法

隣接する狐の順番を入れ替える、すなわちF[i]とF[i+1]をスワップすることを考える。
(i+1)匹乗せた時点の重さは変わらず、変わるのはi匹乗せた時点の重さだけである。
よって、スワップによるポイントの入れ替わりは高々1である。

ポイントが最小となるのはFを昇順、最大となるは降順にすればよいのは明らかである。
Kがこの両者のポイントの範囲に含まれるのならば解があり、そうでなければ解はない。
解がある場合、バブルソートの要領でswapを繰り返していけばいずれKポイントの状態を経由する。

また、自分はよくある辞書順最小を求める手順を取った。
i匹めにこの狐を選んだ時、以後得られる最大最小ポイントを求め、Kポイントがその範囲に含まれるならその狐で確定する、という手順を手前から繰り返した。

class CanidsSeesaw {
	public:
	vector <int> construct(vector <int> wolf, vector <int> fox, int k) {
		int N=wolf.size();
		int i,j,x;
		for(i=1;i<N;i++) wolf[i]+=wolf[i-1];
		vector<pair<int,int>> P;
		FOR(i,N) P.push_back({fox[i],i});
		sort(ALL(P));
		vector<int> R;
		
		FOR(i,N) {
			for(j=i;j<N;j++) {
				swap(P[j],P[i]);
				int tot=0,mi=0,ma=0;
				
				sort(P.begin()+i+1,P.end());
				FOR(x,N) tot+=P[x].first, mi+=(tot>wolf[x]);
				
				reverse(P.begin()+i+1,P.end());
				tot=0;
				FOR(x,N) tot+=P[x].first, ma+=(tot>wolf[x]);
				
				if(mi<=k && k<=ma) break;
				
				swap(P[j],P[i]);
			}
			if(j==N) return R;
			
		}
		
		FOR(i,N) R.push_back(P[i].second);
		return R;
		
	}
}

まとめ

かなり手間取ったので最終的に解けて良かった。