yukicoder No.123 カードシャッフル

愚直にシミュレーション

int main(){
	int m=51,a[51],t;
	while(m--)a[m]=m;
	//1-based
	scanf("%*d%d",&m);
	while(m--){
	    scanf("%d",&t);
	    a[0]=a[t];
	    //t番目の札が一番上にいく
	    while(t--)a[t+1]=a[t];
	    //t番目より上にある札を1つずらす
	}
	printf("%d",a[0]);
	return 0;
}

ところで後ろから処理すれば全体を保存する必要はない
いわゆる「逆シミュレーション」と呼ばれるものらしい

つまり、すべての操作が終了した時点で一番上にあるカードが、操作が始まる前にどこにあったのか、を調べる
「上からa[i]番目のカードを一番上に移す」という操作が行われた後で上からt番目にあるカードは、その操作が行われる前の時点では
・t==1ならa[i]番目
・t>a[i]ならt番目
・さもなくばt-1番目
にあったことが少し考えれば分かる

i;
a[1<<17];
main(t){
	for(;~scanf("%d",a+i++););
	for(;--i>1;t=t>a[i]?t:--t?:a[i]);
	//N,Mも配列に読み込まれているので終了条件に注意
	i=!printf("%d",t);
}

これを圧縮して完成

i;a[1<<17];main(t){for(;~scanf("%d",a+i)?++i:--i>1?t=t-(a[i]>=t)?:a[i]:0;);i=!printf("%d",t);}

と言いたいところだけど、逆シミュレーションは再帰関数と相性が良い（スタックを積みやすい）

t;
f(i){t=~scanf("%d",&i)?f(),t-(i>=t)?:i:1;}
//読み込みが終わったらt=1とし、後ろから順に処理
main(){
	f(gets(&t));
	//引数はどうでもいいのでgetsを食わせて1B短縮
	t=!printf("%d",t);
}

82B

メモ

yukicoderでゆるふわgolf

yukicoder No.123 カードシャッフル