1129.Hanadfuda Shuffle

問題

1からNの番号が書かれたN枚のカードが下から昇順になるように重ねてある。
「上からp枚目からc枚を取り出してカードの山に持ってくる」というシャッフルをR回繰り返す。
シャッフル後に一番上に来ているカードの番号を返す。

考え方

必要なのは最後に一番上に来るカードだけで、それ以外のカードの番号は必要ない。

最初に上から0,1,2,3,...とインデクスを振っておく。
インデクスxがシャッフルを繰り返して最後にyにくることを考える。
y=0となるインデクスxが知りたいが、愚直にシミュレーションすると、N回シャッフル操作が必要となる。
(この問題はここまで)

xからシャッフルによる写像fでyになるとすると、逆写像f^{-1}がわかればyからxがわかる。
言い換えれば、yからxを再現できれば、0からスタートして、xを求めることができるので、シャッフルの逆操作を考える。

1回分の逆シャッフル操作を考えると、
・現在のインデクスyがc未満なら+p-1
・現在のインデクスyがc以上でp-1+c未満なら-c
すればよいことがわかるので、シャッフルを逆から↑の操作を繰り返せばよい。(1回あたりifと加減しか必要ない)
最後にインデクスからカード番号にするために、(N-インデクスx)を返せばよい。