TopCoderOpen 2020 Round3B : Medium ShortBugPaths

変わった制約。
https://community.topcoder.com/stat?c=problem_statement&pm=16348&rd=18145

問題

N*Nのグリッドがある。
また、非負整数集合Dが与えられる。
任意のセルから開始し、そこからユークリッド距離がDに含まれ、かつグリッド内に収まるセルへのジャンプをJ回行う。
そのような移動経路は何通りか。

解法

J回のジャンプで通るセルを囲う矩形のサイズがH*Wなら、そのような矩形を成す移動経路の組み合わせは(N+1-H)*(N+1-W)となる。
よって、J回のジャンプで通るセルを囲う矩形のサイズに対し、そのような移動経路の組み合わせを数え上げよう。

状態としては、矩形のサイズと最後のジャンプにおける矩形内の相対位置を持てばよい。
愚直にやると定数倍が怖いので、移動経路の組み合わせは点対称・線対称を成すのでH≧Wとなるよう適宜縦横入れ替えたり、相対的な位置は矩形の左上に来るよう上下・左右を入れ替えたりするとよい。

ll from[102][52][52][27];
ll to[102][52][52][27];
int ok[31];
const ll mo=1000000007;

class ShortBugPaths {
	public:
	int count(int N, vector <int> D, int J) {
		ZERO(ok);
		ZERO(from);
		FORR(d,D) ok[d]=1;
		from[1][1][0][0]=1;
		int h,w,y,x,i,dy,dx;
		
		while(J--) {
			ZERO(to);
			for(h=1;h<=101;h++) for(w=1;w<=51;w++) {
				for(y=0;y*2<=h;y++) for(x=0;x*2<=w;x++) if(from[h][w][y][x]) {
					for(dy=-10;dy<=10;dy++) {
						for(dx=-10;dx<=10;dx++) if(ok[abs(dy)+abs(dx)]) {
							int th=h,tw=w;
							int ty=y+dy;
							int tx=x+dx;
							if(ty<0) th+=-ty, ty=0;
							if(ty>=th) th=ty+1;
							if(tx<0) tw+=-tx, tx=0;
							if(tx>=tw) tw=tx+1;
							if(th-1-ty<ty) ty=th-1-ty;
							if(tw-1-tx<tx) tx=tw-1-tx;
							if(tw>th) swap(th,tw),swap(ty,tx);
							
							(to[th][tw][ty][tx]+=from[h][w][y][x])%=mo;
							
							
						}
					}
					
				}
			}
			swap(from,to);
		}
		
		ll ret=0;
		for(h=1;h<=101;h++) for(w=1;w<=51;w++) {
			ll sum=0;
			for(y=0;y*2<=h;y++) for(x=0;x*2<=w;x++) sum+=from[h][w][y][x];
			sum%=mo;
			if(h>N) continue;
			if(w>N) continue;
			(ret+=1LL*(N+1-h)*(N+1-w)%mo*sum)%=mo;
		}
		return ret;
		
	}
}

まとめ

何がしたかったんだろう…。