問題
http://topcoder.bgcoder.com/print.php?id=2702
クイックソートは、配列をサブ集合に分けるときのピボットの選び方によりソートまでのスワップ回数が異なる。
ある配列が与えられた時、その配列をソートするまでに必要なスワップ回数の期待値を求める。
解き方
すべてのサブ集合のコストを洗い出す、と考えると計算量はオーバーしてしまう。
ソート済みの配列を考え、その配列の各長さのサブ集合を考える。
そのサブ集合については、元の配列の要素の順番を守った配列をソートしたスワップ回数と等しくなる。
これを利用して、サブ集合の長さを２～ｎまでｄｐによって求めればよい。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class QuickSort {
public: double getEval(vector<int> L) {
int n=L.size();
double dp[n+1][n+1];
memset(dp,0,sizeof(dp));
vector<int> sorted=L;
sort(all(sorted));
FORE(len,2,n+1){
for(int s=0;s+len<=n;s++){
int e=s+len;
vector<int> tmp;
FORE(i,0,n)if(sorted[s]<=L[i]&&L[i]<=sorted[e-1])tmp.push_back(L[i]);
FORE(p,0,len){
int cost=0,small=0;
FORE(i,0,len){
if(tmp[i]<tmp[p]){
small++;
if(p<i)cost++;
}
else if(tmp[i]>tmp[p]){
if(p>i)cost++;
}
}
dp[s][e]+=cost+dp[s][s+small]+dp[s+small+1][e];
}
dp[s][e]/=(double)len;
}
}
return dp[0][n];
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class QuickSort {
public: double getEval(vector<int> L) {
int n=L.size();
double dp[n+1][n+1];
memset(dp,0,sizeof(dp));
vector<int> sorted=L;
sort(all(sorted));
FORE(len,2,n+1){
for(int s=0;s+len<=n;s++){
int e=s+len;
vector<int> tmp;
FORE(i,0,n)if(sorted[s]<=L[i]&&L[i]<=sorted[e-1])tmp.push_back(L[i]);
FORE(p,0,len){
int cost=0,small=0;
FORE(i,0,len){
if(tmp[i]<tmp[p]){
small++;
if(p<i)cost++;
}
else if(tmp[i]>tmp[p]){
if(p>i)cost++;
}
}
dp[s][e]+=cost+dp[s][s+small]+dp[s+small+1][e];
}
dp[s][e]/=(double)len;
}
}
return dp[0][n];
}
};