読者です 読者をやめる 読者になる 読者になる

メモ

yukicoderで遊んでいる競プロゆるふわ勢

yukicoder No.142 単なる配列の操作に関する実装問題

問題はこちら
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