Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-09-10

TheCardShufflingDivTwo

| 22:38

問題文, SRM 448

カードを並べ替えたときに、一番に上にくるのは何か。変換テーブルを作って求めた。もう少し考えて、法則性があるかどうかを検討した方が、提出までの時間を短縮できたと思う。

266.46/500

class TheCardShufflingDivTwo {
public:
    int shuffle(int n, int m) {
        vector<int> L((int)ceil((double)n/2));
        vector<int> R(n/2);
        for (int i = 0; i < n/2; i++) {
            L[i] = 2*i+1;
            R[i] = 2*i+2;
        }
        if (n%2 == 1) L[n/2] = n;
        vector<int> table(n+1);
        for (int i = L.size()-1; i >= 0; i--)
            table[R.size()+i+1] = L[i];
        for (int i = R.size()-1; i >= 0; i--)
            table[i+1] = R[i];

        int top = 1;
        for (int i = 0; i < m; i++)
            top = table[top];
        return top;
    }
};