yukicoder : No.2432 Flip and Move

これはすんなり。
https://yukicoder.me/problems/no/2432

問題

H*Wのグリッドがあり、各セルはそれぞれ白黒の色を取る。初期状態はすべて白である。
初期状態はロボットが左上マスにおり、右下を向いている。
1秒毎に、ロボットは以下の手順を取る。

• 今いるセルの白黒を反転する。
• 上下方向で向いているセルに移動する。ただし移動先がグリッド外になる場合、移動はせず向きを上下反転する。
• 左右方向で向いているセルに移動する。ただし移動先がグリッド外になる場合、移動はせず向きを左右反転する。

K秒後のグリッドの状態を求めよ。

解法

O(HW)秒シミュレートすると、ロボットは初期状態と同じ位置・向きに戻る。
またそれを2周すると、セルの白黒も元に戻る。
ロボットが初めて初期状態と同じ位置・向きに戻るまでの時間をTとすると、K%(2T)時間分だけシミュレートすればよいことになる。

int H,W;
ll K;
unordered_map<int,int> M;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>K;
	int cy=0,cx=0,dy=1,dx=1;
	int step=0;
	while(step==0||(cy||cx||dy!=1||dx!=1)) {
		step++;
		if(cy+dy<0||cy+dy>=H) dy=-dy;
		else cy+=dy;
		if(cx+dx<0||cx+dx>=W) dx=-dx;
		else cx+=dx;
	}
	K%=2*step;
	while(K) {
		M[cy*W+cx]^=1;
		if(cy+dy<0||cy+dy>=H) dy=-dy;
		else cy+=dy;
		if(cx+dx<0||cx+dx>=W) dx=-dx;
		else cx+=dx;
		K--;
	}
	FOR(y,H) {
		FOR(x,W) {
			if(M[y*W+x]) cout<<"#";
			else cout<<".";
		}
		cout<<endl;
	}
	
}

まとめ

もっとH*W大きいとどうなるんだろ。