TopCoder SRM 641 Div1 Medium ShufflingCardsDiv1

こちらはちょっとややこしい。
http://community.topcoder.com/stat?c=problem_statement&pm=13541

問題

カードのシャッフル条件はDiv2 Hardと同一である。
TopCoder SRM 641 Div2 Hard ShufflingCardsDiv2 - kmjp's blog

シャッフル後の山の状態Pが与えられる。
初期状態からPを生成するのに必要な最低シャッフル回数を求めよ。

解法

まずコーナーケースを片付ける。
Pが初期状態と同じなら0回である。
PにおいてN/2以下のカードが奇数番目に来ているなら、1回である。

あとは１回シャッフルするごとに、N/2以下のカードが奇数番目に何枚来ることができるかをDFSで求めていけば良い。
初回のシャッフルで1～N/2及びN/2+1～Nの間は自由に入れ替えることができるので、N/2以下のカード枚数さえPと一致するシャッフルが存在するなら、全体がPと一致するシャッフルも可能である。

int memo[2001];
class ShufflingCardsDiv1 {
	public:
	int N,zm;
	
	void dfs(int zen,int d) {
		memo[zen]=d;
		int zen2=N/2-zm;
		int mi=max(0,zen-(N/2-zm))+max(0,zen2-zm);
		int ma=min(zen,zm)+min(zen2,N/2-zm);
		for(int i=mi;i<=ma;i++) if(memo[i]>d+1) dfs(i,d+1);
	}
	
	
	int shuffle(vector <int> P) {
		int i,ret;
		N=P.size();
		
		int ok=1,ok2=1;
		FOR(i,N) if(P[i]!=i+1) ok=0;
		if(ok==1) return 0;
		FOR(i,N) if((P[i]<=N/2) ^ (i%2==0)) ok2=0;
		if(ok2==1) return 1;
		
		FOR(i,2000) memo[i]=2000;
		
		zm=((N/2)+1)/2;
		dfs(zm,1);
		
		int zen=0;
		FOR(i,N/2) if(P[i*2]<=N/2) zen++;
		return memo[zen]+1;
	}
}

まとめ

前回といい今回といい、実装より発想よりの問題だな。