SRM 402 250pt: RandomSort

TopCoder

問題概要

長さN(<=8)の配列(重複無し)が与えられる。i>jかつA[i]

考えたこと

  • 長さ短いしvectorをキーにしたメモ化再帰で行ける？
  • 状態はループしないだろうか。
  • 転倒数が単調減少なのでDAGになる。行ける。
  • 後は書くだけ。無事通った。

practiceで通ったコード

#include <vector>
#include <map>
using namespace std;

map<vector<int>, double> memo;

struct RandomSort {

	double getExpected(vector <int> permutation) {
		return rec(permutation);
	}

	double rec(vector<int> perm){
		if(memo.find(perm) != memo.end()){
			return memo[perm];
		}

		double ret = 0;

		int swp = 0;
		for(int i=0; i<(int)perm.size(); i++){
			for(int j=i+1; j<(int)perm.size(); j++){
				if(perm[i] > perm[j]){
					swp++;
				}
			}
		}

		if(swp == 0){
			return 0.0;
		}

		for(int i=0; i<(int)perm.size(); i++){
			for(int j=i+1; j<(int)perm.size(); j++){
				if(perm[i] > perm[j]){
					swap(perm[i], perm[j]);
					ret += (1.0 + rec(perm)) / swp;
					swap(perm[i], perm[j]);
				}
			}
		}

		return memo[perm] = ret;
	}

};