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>

LukeEvifeLukeEvife2019/06/05 08:55Luke Bryan is my favourite US contry singer. His strong voice takes me away from all issues of this planet so I can enjoy my life and listen songs created by his voice. Now the singer is going on a tour in 2019. The concerts scheduled for this year, up to the 12th of October. Ticket prices are moderate and available for all men and women with different income. If you love contry music, then you must visit at least one of his concert. All tour dates are available at the <a href=https://lukebryantourdates.com>Luke Bryan concert list</a>. Visit the website and make yourself familiar with all Luke Bryan concerts in 2020!

LukeEvifeLukeEvife2019/06/08 00:46Luke Bryan is my favourite country singer. His strong voice takes me away from all problems of this planet so I start enjoy my life and listen songs created by his. Now the singer is going on a tour in 2020. The concerts scheduled for the whole 2019, up to the mid-October. Tickets are available for everyone. If you are a country music lover as me, then you must visit at least one Luke's concert. All tour dates are available at the <a href=https://lukebryantourdates.com>Luke Bryan concert list</a>. Open the website and make yourself familiar with all powerful Luke Bryan concerts in 2020!

FlorluptFlorlupt2019/06/10 12:34Florida Georgia Line is my favourite country music band. Headliners Brian Kelley and Tyler Hubbard are those people that could make anyone sing along with them. That's why I like to visit their shows. And - that's surprisingly wonderful - in 2019 they have CAN'T SAY IT AIN'T COUNTRY TOUR which covers all the US towns and cities. For concert dates list visit <a href=https://fgltour.com>Florida Georgia Line Concert Tour</a>.