Hatena::Grouptopcoder

mechairoiの日記

2009-09-12

SRM 448 Medium

| 08:25

カードを複雑な手順でシャッフルしたときに一番上にあるカードを求める問題。解き方は SRM 448 Medium - tsubosakaの日記 - TopCoder部みたいに逆から計算する。逆向きの式を考えるのが苦手でこんなコードが書ける気がしなかったけど、そこそこ早く書けそうな方法を思いついたのでメモ。

  • この問題ではシャッフルの方法が複雑
  • それをいくつかの単純なステップに分解
  • それぞれのステップ逆操作を作る
  • あとは再帰的に呼び出す

コードは以下。


#include <cstdio>

enum deck { MAIN ,RIGHT, LEFT };

class TheCardShufflingDivOne {
  public:
    int L,R;
    int shuffle(int n, int left, int right) {
      L = left; R = right;
      if(n % 2 == 0) {
        return step2(RIGHT, 0, 0, 1, 1, n-2);
      } else {
        return step4(MAIN, 0, 1, 0, 0, n-1);
      }
    }
    inline int step4(deck d, int k, int main, int left, int right, int resulting) {
      //printf("4#%d\t%d\t%d\t%d\t%d\t%d\n", d, k, main, left, right, resulting);
      if(resulting == 0) return k+1;
      if(k < main / 2)
        return step3(RIGHT, main/2 - k - 1, 0, (main+1)/2, main/2, resulting);
      else
        return step3(LEFT,  main - k - 1, 0, (main+1)/2, main/2, resulting);
    }
    inline int step3(deck d, int k, int main, int left, int right, int resulting) {
      //printf("3#%d\t%d\t%d\t%d\t%d\t%d\n", d, k, main, left, right, resulting);
      return step2(d, k+1, main, left+1, right+1, resulting - 2);
    }
    inline int step2(deck d, int k, int main, int left, int right, int resulting) {
      //printf("2#%d\t%d\t%d\t%d\t%d\t%d\n", d, k, main, left, right, resulting);
      return step1(d, (d == RIGHT) ? (k + R) % right : (k + L) % left , main, left, right, resulting);
    }
    inline int step1(deck d, int k, int main, int left, int right, int resulting) {
      //printf("1#%d\t%d\t%d\t%d\t%d\t%d\n", d, k, main, left, right, resulting);
      return step4(MAIN, (d == RIGHT) ? (right - k) * 2 - 1 : (left  - k) * 2 - 2, left + right, 0, 0, resulting);
    }
};

ごちゃごちゃしていて読みにくいように見えるが、状態が4つのデッキの枚数と、求めるべきカードがどのデッキの何枚目かだけなので、その状態を各ステップで逆変換する関数を順に呼び出しています。タイプ数は多いけど書きやすくミスも見つけやすい(気がする)。

再帰使わずにWhileとかでミスらずに書く方法はわからない。