HackerRank 101 Hack 51 : E. Testing the Game

なんか面倒な問題。
https://www.hackerrank.com/contests/101hack51/challenges/testing-the-game

問題

N,Mに対しN*(2*M-1)のグリッドを考える。
偶数列目は、最上段および最下段を除くと壁であり移動不可である。

初期状態で、いくつかのマスは敵が支配している。
ここでクエリとして値Tが与えられる。
各マスにおいて、隣接マスをT回以内でたどって到達可能な敵の数を求めよ。
(問題では得られた敵の数を重みづけして答えることになっている)

解法

とにかく累積和を多用して、1クエリO(NM)程度で解く。以下の処理はちょっと横着してO(NMlogM)である。

各マスに対し、順次到達可能な敵の数を求めることを考えよう。
この時移動経路がどうなるかを考える。
対象マスから最上段または最下段に移動した後、左右に移動してまた列内を上下移動することになる。
対象マスから左右方向にずれるほど、上下の移動可能範囲が狭まる。

これを踏まえ移動範囲の敵の数え上げを行う。
対象マスからT回以内の移動をしたとき、列全体が移動できるような列の範囲を求めよう。
これは二分探索などで各列上下に到達したときの残り移動マス数の和が(N-2)以上となる範囲の下限上限を求めればよい。

以下、マスの左側について考える。
今、対象マスから左側r列目において、列全部を到達不可だとする。
すなわち(最上段・最下段以外で)上からtマス、下からbマスだけ移動でき、かつt+b＜N-2とする。
この時、(r-i)列目は上から(t-i)マス、下から(b-i)マスだけ移動できることになる。
よって、斜め方向の累積和を事前に取っておくと、r,t,bからO(1)でr列目より左側の敵の数を列挙できる。

int N,M;
string S[1010];
int sum[2010][2010];
int LT[2010][2010];
int LD[2010][2010];
int RT[2010][2010];
int RD[2010][2010];

int Q,T;
int RS[2020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(y,N) cin>>S[y];
	
	for(x=0;x<2*M;x+=2) {
		for(y=1;y<N;y++) sum[y][x]=sum[y-1][x]+(S[y][x]=='t');
		
		RS[x]=sum[N-1][x];
		if(x) RS[x]+=RS[x-2];
		
		for(y=1;y<N-1;y++) {
			LT[y][x]=sum[y][x];
			if(y>=2&&x>=2) LT[y][x]+=LT[y-2][x-2];
			LD[y][x]=sum[N-1][x]-sum[y-1][x];
			if(y+2<=N-1&&x>=2) LD[y][x]+=LD[y+2][x-2];
		}
	}
	for(x=2*M-2;x>=0;x-=2) {
		for(y=1;y<N-1;y++) {
			RT[y][x]=sum[y][x];
			if(y>=2&&x+2<=2*M) RT[y][x]+=RT[y-2][x+2];
			RD[y][x]=sum[N-1][x]-sum[y-1][x];
			if(y+2<=N-1&&x+2<=2*M) RD[y][x]+=RD[y+2][x+2];
		}
	}
	
	
	
	cin>>Q;
	while(Q--) {
		cin>>T;
		
		ll ret=0;
		ll mo=1000000007;
		for(y=1;y<N-1;y++) for(x=0;x<=2*M-1;x+=2) {
			// same row
			ll cnt=sum[min(N-1,y+T)][x]-sum[max(0,y-T-1)][x];
			
			int lef=x;
			for(i=10;i>=0;i--) {
				int tmp=lef-(2<<i);
				int top=max(0,T-y-(x-tmp));
				int bot=max(0,T-(N-1-y)-(x-tmp));
				
				if(top+bot>=N-1) lef=tmp;
			}
			
			if(x) cnt+=RS[x-2];
			if(lef>=2) cnt-=RS[lef-2];
			lef-=2;
			if(lef>=0) {
				int top=max(0,T-y-(x-lef));
				int bot=max(0,T-(N-1-y)-(x-lef));
				cnt+=LT[top][lef]+LD[N-1-bot][lef];
			}
			
			int ri=x;
			for(i=10;i>=0;i--) {
				int tmp=ri+(2<<i);
				int top=max(0,T-y-(tmp-x));
				int bot=max(0,T-(N-1-y)-(tmp-x));
				if(top+bot>=N-1) ri=tmp;
			}
			
			cnt+=RS[min(2*M-2,ri)];
			cnt-=RS[x];
			ri+=2;
			if(ri<=2*M-1) {
				int top=max(0,T-y-(ri-x));
				int bot=max(0,T-(N-1-y)-(ri-x));
				cnt+=RT[top][ri]+RD[N-1-bot][ri];
			}
			
			(ret+=cnt*cnt%mo*((x+1)*(y+1)))%=mo;
		}
		cout<<ret<<endl;
	}
	
	
}

まとめ

面倒なだけでC,Dほど面白味はなかったな…。