問題はこちら
No.123 カードシャッフル - yukicoder
愚直にシミュレーション
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