Hatena::Grouptopcoder

tsubosakaの日記

2009-09-11SRM 448

SRM 448 Medium

| 00:03

1からnまでのカードが順番に並んでいる。これを複雑な手順でシャッフルを繰り返すことによって最終的に一番上にあるカードを求めよという問題。

nは10^6まであるのでシミュレーションを愚直にするとn^2で間に合わない。

着目点は

  • 各手順において手札からは2枚ずつ減っていく
  • n-2枚目をシャッフルし終わったときに一番上にあるカードがk番目のカードであれば、n番目をシャッフルし終わったときに一番上にあるカードは1回のシャッフル手順を繰り返した時の状態でのk番目のカードである

よって1枚or2枚のときの状態から逆算してn枚目の状態を求めればよい。

コードは以下のようになる

public class TheCardShufflingDivOne {
  int rotate(int idx , int len , int move){
    return (idx + len - (move % len)) % len;
  }
  int shuffle_once(int n , int idx , int left , int right){
    int lnum = (n + 1) / 2;
    int rnum = n / 2;
    if(idx < rnum - 1){
      int i = rotate(idx, rnum, right);
      return i * 2 + 1;
    }else{
      idx -= rnum - 1;
      int i = rotate(idx, lnum, left);
      return i * 2;
    }
  }
  public int shuffle(int n, int left, int right) {
    boolean iseven = n % 2 == 0;
    int mdeck = iseven ? 2 : 1;
    int k = iseven ? 1 : 0;
    while(mdeck < n){
      mdeck += 2;
      k = shuffle_once(mdeck , k, left, right);
    }
    return k + 1  ;
  }
}