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

メモ

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

yukicoder No.351 市松スライドパズル

問題はこちら
No.351 市松スライドパズル - yukicoder

盤面が大きいので、盤面全体を愚直にシミュレーションするとTLEする。
ということで、逆シミュレーションする。
つまり、「最後に(x,y)にいるタイルは、最初にどこにいたか」を調べる
ある時点で(x,y)にいるタイルが1手前にどこにいたかを考えると
直前の操作が「R y」だったなら(x-1,y)
直前の操作が「C x」だったなら(x,y-1)
どちらでもないなら(x,y)
となるのでこれで求められる
(x-1,y-1が負になる時は適切に処理する)

int main(){
	char a[1000010];
	int  b[1000010];
	int x,y,w,h,n,i;
	scanf("%d%d%d ",&h,&w,&n);
	for(i=0;i<n;++i){
		scanf("%c%d ",a+i,b+i);
	}
	for(i=n-1;i>=0;i--){
		if(a[i]=='R'&&y==b[i])x=(x+w-1)%w;
		if(a[i]=='C'&&x==b[i])y=(y+h-1)%h;
	}
	printf((x+y)%2?"black":"white");
	//この時点での(x,y)が初期座標になるので、これにより白黒つく
	return 0;
}

そういえば逆シミュレーションの問題って以前解いたなあ
yukicoder No.123 カードシャッフル - メモ
ということで再帰で書こう

x,y,h,w;
f(c,d){
~scanf("%c%d ",&c,&d)?
	 f(),
	 c&=127,
	 c=='R'&&y==d?x=(x+w-1)%w:0,
	 c=='C'&&x==d?y=(y+h-1)%h:0
	:0;
}
main(){
	scanf("%d%d%*d ",&h,&w);
	f();
	y=!puts(x+y&1?"black":"white");
}

2つに分かれてる書き換え処理をまとめてしまいたいから配列にしてみよう
'R'が82、'C'が67なので、読み込んだ文字は&1で識別できる

h[2],x[2],q;
f(c,d){
	~scanf(" %c%d",&c,&d)?
		 f(),
		 x[q=c&1]==d?x[1-q]=(x[1-q]-1+h[q])%h[q]:0
		:0;
}
main(){q=f(scanf("%d%d%*d",h+1,h))>puts(*x+x[1]&1?"black":"white");}

最後に計算を縮めて

h[2],x[2],q;
f(c,d){
	~scanf(" %c%d",&c,&d)?
		 f(),
		 x[q=c&1]-d?:!x[1-q]--?x[1-q]+=h[q]:0
		:0;
}
main(){q=f(scanf("%d%d%*d",h+1,h))>puts(*x+x[1]&1?"black":"white");}

153B

16/06/16追記

h[2],a[2],q;
f(c,d){
	~scanf(" %c%d",&c,&d)&&f();
	a[q=c&1]-d?:!a[1-q]--?a[1-q]+=h[q]:0;
}
main(){q=f(scanf("%d%d%*d",h+1,h))>puts(*a+a[1]&1?"black":"white");}

152B
読み込みが終わった時のdの値が0でないならこれでうまくいく。
関数を呼び出したときに省略した引数を評価するちょっと怪しいコード
(そういうとき何の値が入っているのかは、アセンブリの知識が無いのでわからない)