kmjp's blog

競技プログラミング参加記です

Autumn Fest 2012 : J - Ninja of Train

その他コンテスト

10問目に突入、ぼちぼち終盤。
http://autumn_fest.contest.atcoder.jp/tasks/autumn_fest_10


スクロールしていく窓の範囲で忍者が移動するので、窓から外れないような移動順の組み合わせを答える問題。
本番はsmallしか解けなかったので復習。

small

まずは本番も解けたsmallから。
H<=22、T<=22222と窓が小さく、１回のジャンプでの移動距離DはD-√D<=Hを満たさないといけないので最大D=27。
時刻Tの各タイミングで、距離1～27のジャンプを行う組み合わせをDPで足していく。
これはO(TH^2)なので、medium以降は無理。

int H,T;
int RT[101];
int MO=1000003;
int dp[22230][28];

void solve() {
	int x,y,i,j,p,rr,TM,TTC,dep,res,t;
	
	for(i=j=1;i<=100;i++) {
		if(j*j<=i) j++;
		RT[i]=j-1;
	}
	
	GET2(&H,&T);
	if(H>22 || T>22222) return;
	ZERO(dp);
	dp[0][0]=1;
	res=0;
	H--;
	FOR(t,T+1) {
		FOR(x,H+1) {
			if(dp[t][x]==0) continue;
			res = (res + dp[t][x]) % MO;
			for(y=1;y<=30;y++) {
				int nx = x+y-RT[y];
				if(nx>H) break;
				if(t+RT[y]>T) break;
				dp[t+RT[y]][nx] = (dp[t+RT[y]][nx] + dp[t][x]) % MO;
			}
		}
		
	}
	
	_P("%d\n",res);
}

large

Medium以降はTが大きいので、O(T)以上の処理は行えない。
幸いH<=77とTは小さいので、こちらを利用する。
この問題では、消えない限りは毎回最低距離１をジャンプしなければいけないので、位置が戻ることはない。
よって、距離２以上をジャンプ（√D分窓がスクロールするので、実質移動距離はD=2の時1）するのは高々77回しか行えない。

そこで、距離２以上のジャンプのパターンをまずはDPで列挙する。
状態としては、経過時間・ジャンプ回数・位置の３通りで、経過時間がTを超えず、位置がHを超えない範囲でDPを行う。
このDPはO(T^3)時間かかるが、Tが小さいので問題ない。

次に、各経過時間・ジャンプ回数ごとに、途中で消えたり距離１のジャンプが入る場合の組み合わせを考える。
距離２以上のジャンプについて、経過時間がX、ジャンプ回数がYとなる組み合わせ数をZすると、距離１のジャンプは0～T-X回可能であり、その間にY回距離２以上のジャンプをするので、その数はZ \times \sum_{i=0}^{T-X} {}_{i+Y} C_{Y}回になる。

Combinationの計算は、Yが小さいのと答えがmodを取った値を出せばよいので、1～Yの逆元を求めておけばO(Y)で行えるが、それでもO(TY)かかってしまう。
ここで少し考えてみたのだが、\sum_{i=M}^{N} {}_N C_M={}_{N+1} C_{M+1}と置けることに気づいた。
よってこのCombinationはO(Y)で計算できる。

int H,T;
int RT[101];
ll MO=1000003;
ll mod=MO;
ll dp[101][101][101];
ll dp2[101][101];

ll combi(ll N_, ll C_) {
	int i;
	const int num=100;
	static ll rev[num+1],revt[num+1];
	
	if(rev[1]==0) {
		rev[1]=1; for(i=2;i<=num;i++) rev[i]=rev[MO%i]*(MO-MO/i)%MO;
		revt[0]=1; for(i=1;i<=num;i++) revt[i]=revt[i-1]*rev[i]%MO;
	}
	ll ret=revt[C_];
	FOR(i,C_) ret = (ret * (N_-i))%MO;
	return ret;
}

void solve() {
	int x,y,z,i,j,p,rr,TM,TTC,dep,res,t;
	ll ret;
	
	for(i=j=1;i<=100;i++) {
		if(j*j<=i) j++;
		RT[i]=j-1;
	}
	
	GET2(&H,&T);
	ZERO(dp);
	dp[0][0][0]=1;
	
	// x:経過時間 y:ステップ数 z:位置
	FOR(x,90) FOR(y,90) FOR(z,H+1) {
		if(dp[x][y][z]==0) continue;
		for(j=2;j<100;j++) {
			if(x + RT[j] > T) break;
			if(z + j - RT[j] >= H) break;
			dp[x+RT[j]][y+1][z + j - RT[j]] = (dp[x+RT[j]][y+1][z + j - RT[j]] + dp[x][y][z]) % MO;
		}
	}
	
	//位置はどこでもいいので畳み込み
	ZERO(dp2);
	ret = 0;
	FOR(x,90) FOR(y,90) FOR(z,90) dp2[x][y] = (dp2[x][y]+dp[x][y][z])%MO;
	FOR(x,90) FOR(y,90) if(dp2[x][y]) ret = (ret + combi(T-x+y+1,y+1)*dp2[x][y]) %MO;
	
	_P("%lld\n",ret);
}

まとめ

解説はやけに難しいけど、DPをちゃんと行うとそこまで難しくない問題。
最後のCombinationの\sum_{i=M}^{N} {}_N C_M={}_{N+1} C_{M+1}という特性、一般的なのかな？
自分はこれ知らなくて自分で考え付いたけど、上位の人はさらっとこれ書いてるんだよな…。