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  ;
  }
}

WilliamTagWilliamTag2019/02/02 11:26cialis without a rx
kjop cialis online
<a href=https://kellyannehulme.com>buy Cialis 20 mg</a>
acheter cialis france
cialis tyskland
https://greatwinesgrandhouses.com
low cost cialis 2.5mg daily
expired cialis side effects
<a href=https://kellyannehulme.com>20 mg cialis buy</a>
generic cialis in germany drug store
buy cialis us pharmacy
https://kellyannehulme.com

ArnoldNizArnoldNiz2019/02/05 20:50order female cialis side effects
buying cialis in malaysia
<a href="http://xcialisxx.com">Cheap Cialis buy</a>
cialis back pain
cialis review recreational
<a href="http://xcialisxx.com">Buy Cheap Cialis</a>
cialis strips online
about cialis
<a href="http://xcialisxx.com">Buy Cheap Cialis Online</a>