先に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とはいえずいぶんあっさり。