TopCoder, Single Round Match 641, Division 2, Level 3 : ShufflingCardsDiv2

問題文

　http://community.topcoder.com/stat?c=problem_statement&pm=13549&rd=16084

問題概要

　 枚のカードがあり，各カードには の番号が重複無く 1 つずつ書かれている．カードは初期状態では番号の昇順に積まれている．
　このカードの山に対して以下の手順を 2 回適用して並べ替える．

1. カードを半分に分ける．山の前半を ，後半を とする
2. の並び順を任意に並べ替える
3. の並び順を任意に並べ替える
4. から交互に 1 枚ずつとっていってマージする．形式的には，マージ後の山が という並び順になるようにする．

　2 回の適用の結果， で与えられる並び順を達成できるか否か，求めよ．

解法

　操作回数が少ないので，操作を逆順に考えることにより，各段階で満たしていなければならない条件を洗い出すことができます．具体的には，

• 最終状態で偶数番目にあるカードは，2 回目の操作では として分割された
• すなわち，1 回目の操作の完了時には山の前半にあった
• 1 回目の操作完了時に山の前半にくるカードは，1 回目の分割に於ける の半分程度ずつ

というようなことが言えます．このことから，最終状態で偶数番目にあるカードが，1 回目の分割で に半分程度ずつ割り振られれば，目標を達成できることが分かります．「半分程度」と濁している部分は，マージのプロセスを観察することにより， への振り分けは 枚， への振り分けは 枚であることが分かります．
　従って，目標状態で偶数番目にあるカードの内， 以下のものの枚数が 枚かつ， を超えるものが 枚であれば，目標状態を作ることができます．

コード

class ShufflingCardsDiv2
{
public:
	string shuffle( vector <int> permutation )
	{
		const int N = permutation.size() / 2;
		int a = ( N + 1 ) / 2, b = N / 2;

		for ( int i = 0; i < 2 * N; i += 2 )
		{
			--( permutation[i] <= N ? a : b );
		}

		return 0 == a && 0 == b ? "Possible" : "Impossible";
	}
};