kmjp's blog

競技プログラミング参加記です

TopCoder SRM 641 Div2 Hard ShufflingCardsDiv2

先にDiv1 Mediumを見ていると簡単。
http://community.topcoder.com/stat?c=problem_statement&pm=13549

問題

偶数であるN枚のカードの山があり、初期状態でカードは1,2,3,...,Nと数字順に並んでいる。
ここで以下のようなシャッフルを行う。

  • 山の前半半分をAとする。Aを好きな順にシャッフルする。
  • 山の後半半分をBとする。Bを好きな順にシャッフルする。
  • Aの1枚目、Bの1枚目、Aの2枚目、Bの2枚目…と順に積み重ねてシャッフル完了。

現在のカードの並び順Pが与えられる。
上記シャッフルを2回行い、初期状態からPを生成できるか答えよ。

解法

初回のシャッフル後、以下のようになる。

  • 奇数番目のカードは、1~N/2のいずれか
  • 偶数番目のカードは、N/2+1~Nのいずれか

2回目のシャッフルで奇数番目に来るカードには、初回奇数番目に来たN/2枚のうち前半分、((N/2)+1)/2枚が来るはずである。
よって、Pの奇数番目にN/2以下のカードがちょうど((N/2)+1)/2枚来るかチェックすればよい。

class ShufflingCardsDiv2 {
	public:
	string shuffle(vector <int> P) {
		int i,N=P.size(),r=0;
		FOR(i,N/2) if(P[i*2]<=N/2) r++;
		if(r==((N/2)+1)/2) return "Possible";
		return "Impossible";
	}
}

まとめ

900ptとはいえずいぶんあっさり。