問題はこちら
No.142 単なる配列の操作に関する実装問題 - yukicoder
普通にやったんじゃ全然間に合わない
必要なのは偶奇の情報だけなのでbitに押し込めてどうにかする
インラインアセンブラまで頑張らなくても間に合う
unsigned long a[32000],temp[1600]; n,p,s,x,y,z,i,j; long t; int main(){ scanf("%d%d%d%d%d%*d",&n,&s,&x,&y,&z); //初期値の設定 a[0]=s&1<<1; t=s; for(i=2;i<=n;i++){ t=(t*x+y)%z; a[i>>6]|=(t&1)<<(i&63); } //a[i]のjbit目が問題文中のA[i*64+j]の偶奇に対応する //Aは1-basedであることに注意 for(;~scanf("%d%d%d%*d",&s,&x,&y);){ x-=s-1; //書き換える要素の個数 //加算元をtempに持ってくる処理 p=s&63; z=64-p; for(i=0,j=s>>6;i<<6<x;i++,j++){ //A[S](S=j*64+p)からの偶奇をtemp[0]の0bit目から順に保存していく temp[i]=a[j]>>p; if(p)temp[i]|=a[j+1]<<z; } z=64-(x&63); if(z!=64)temp[i-1]=temp[i-1]<<z>>z; //tempにはceil(x/64)*64個分の値が保存されたので //はみ出した部分はshiftによるオーバーフローで消す //tempを指定位置に加算する処理 p=y&63; z=64-p; for(i=0,j=y>>6;i<<6<x;i++,j++){ a[j]^=temp[i]<<p; if(p)a[j+1]^=temp[i]>>z; } } for(i=1;i<=n;i++)putchar((a[i>>6]>>(i&63))&1?'O':'E'); return 0; }
これを元に縮めていく
64という定数が何度も出るのでこれをmという変数でおく
配列名tempも長いのでbに変える
初期値の設定 //いったんsに読む込む必要はないので for(scanf("%d%d%d%d%d%*d",&n,&t,&x,&y,&z);i++<n;t=(t*x+y)%z)a[i/m]|=t%2<<i%m; //とまとめる事ができる(iが1のときもうまくいっている) メイン部分 //sを消したので読み込みに使う変数をsからzに変更 for(;~scanf("%d%d%d%*d",&z,&x,&y);){ 加算元のtempへのコピー //わざわざjという変数をおかずにz/mをそのまま使う //pの代わりに手隙のtを使う //iのincをうまく噛みあわせるためにiの初期値を-1とする for(i=-1,x-=z-1,t=z%m;++i*m<=x;b[i]|=a[i+z/m]>>t)b[i]=t?a[z/m-~i]<<m-t:0; //※さきほどと全く同じ動作のためにはループ継続条件には等号が入らず++i*m<xとするべきだが //あとの処理の都合で変えている 端数処理 temp[i-1]=temp[i-1]<<z>>z; //としていた箇所ではzが64のとき未定義であり //yukicoder環境ではa<<64は0でなくaとなり期待する動作にならないのでif文が必要だった。これを b[i-1]&=(1L<<x%m)-1; //と書き換えたい //そのためにはx%mが0の時にb[i-1]が0になっていいように、indexがずれるように等号を入れた 指定位置への加算 //端数処理もfor文の頭に押し込んで、コピーの時と同様に for(b[i-1]&=(1L<<x%m)-1,t=y%m;i--;a[y/m+i]^=b[i]<<t)t?a[y/m-~i]^=b[i]>>m-t:0; 出力 for(i=0;i++<n;)putchar(a[i/m]>>i%m&1?79:69);
以上をまとめて次が得られる
unsigned long a['~~'],b[1600],t; x,y,z,i,m=64; main(n){ for(scanf("%d%d%d%d%d%*d",&n,&t,&x,&y,&z);i++<n;t=(t*x+y)%z)a[i/m]|=t%2<<i%m; for(;~scanf("%d%d%d%*d",&z,&x,&y);){ for(i=-1,x-=z-1,t=z%m;++i*m<=x;b[i]|=a[i+z/m]>>t)b[i]=t?a[z/m-~i]<<m-t:0; for(b[i-1]&=(1L<<x%m)-1,t=y%m;i--;a[y/m+i]^=b[i]<<t)t?a[y/m-~i]^=b[i]>>m-t:0; } for(i=0;i++<n;)putchar(a[i/m]>>i%m&1?79:69); }
メイン部分でのiの初期化を工夫してもう少しだけ短縮できる
unsigned long a['~~'],b[1600],t; x,y,z,i,m=64; main(n){ for(scanf("%d%d%d%d%d%*d",&n,&t,&x,&y,&z);i++<n;t=(t*x+y)%z)a[i/m]|=t%2<<i%m; for(;i=~scanf("%d%d%d%*d",&z,&x,&y)/4;){ for(x-=z-1,t=z%m;++i*m<=x;b[i]|=a[i+z/m]>>t)b[i]=t?a[z/m-~i]<<m-t:0; for(b[i-1]&=(1L<<x%m)-1,t=y%m;i--;a[y/m+i]^=b[i]<<t)t?a[y/m-~i]^=b[i]>>m-t:0; } for(;i++<n;)putchar(a[i/m]>>i%m&1?79:69); }
358B
2016年5月ごろのアプデにより実行速度が早くなったのでlongでなくintでも通るようになった
unsigned a[70000],b[3200]; t,x,y,z,i,m=32; main(n){ for(scanf("%d%d%d%d%d%*d",&n,&t,&x,&y,&z);i++<n;t=(1L*t*x+y)%z)a[i/m]|=t%2<<i%m; for(;i=~scanf("%d%d%d%*d",&z,&x,&y)/4;){ for(x-=z-1,t=z%m;++i*m<=x;b[i]|=a[i+z/m]>>t)b[i]=t?a[z/m-~i]<<m-t:0; for(b[i-1]&=(1<<x%m)-1,t=y%m;i--;a[y/m+i]^=b[i]<<t)t?a[y/m-~i]^=b[i]>>m-t:0; } for(;i++<n;)putchar(a[i/m]>>i%m&1?79:69); }
356B
signedにするとbitshiftが怪しくなるのでそれは無理っぽい
1bitのフラグを複数まとめて1Byteに押し込めて、まとめてコピーしたり比較したりというのはゲームでよく見る処理
(2016/06/02追記)
b[i-1]&=(1<<x%m)-1; b[i-1]%=1<<x%m;
と書き換えて352B