kmjp's blog

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

TopCoder SRM 833 : Div1 Easy Div2 Hard Never3Steps

2回連続大ポカをやらかさなくてよかった。
https://community.topcoder.com/stat?c=problem_statement&pm=17697

問題

座標(X,Y)が与えられる。
2次元座標上で、1だけX座標を増やすか1だけY座標を増やすかいずれかの処理を繰り返し、原点から(X,Y)に移動する経路を考える。
同じ処理をちょうど3回だけ繰り返す手順が含まれていてはならない。
そのような経路は何通りか。

解法

以下のいずれでも解けるようだ。

  • 上または右の移動回数を1,2,3,4回以上のいずれであるか状態を保持しながらDP
  • 累積和を使い、上→右→上→右→…と交互に移動する経路を列挙する。ただし、ちょうど3回の移動分については累積和から減算しておく。
const ll mo=1000000007;
ll dp[1010][1010][8]; // 1234+ 1234+

class Never3Steps {
	public:
	int count(int X, int Y) {
		ZERO(dp);
		dp[0][0][0]=1;
		dp[1][0][0]=1;
		dp[0][1][4]=1;
		int y,x;
		FOR(y,1005) FOR(x,1005) if(y+x) {
			// up
			(dp[y+1][x][0]+=dp[y][x][4]+dp[y][x][5]+dp[y][x][7])%=mo;
			(dp[y+1][x][1]+=dp[y][x][0])%=mo;
			(dp[y+1][x][2]+=dp[y][x][1])%=mo;
			(dp[y+1][x][3]+=dp[y][x][2]+dp[y][x][3])%=mo;
			//right
			(dp[y][x+1][4]+=dp[y][x][0]+dp[y][x][1]+dp[y][x][3])%=mo;
			(dp[y][x+1][5]+=dp[y][x][4])%=mo;
			(dp[y][x+1][6]+=dp[y][x][5])%=mo;
			(dp[y][x+1][7]+=dp[y][x][6]+dp[y][x][7])%=mo;
		}
		ll ret=0;
		ret+=dp[X][Y][0]+dp[X][Y][1]+dp[X][Y][3]+dp[X][Y][4]+dp[X][Y][5]+dp[X][Y][7];
		return ret%mo;
	}
}

まとめ

250ptでも良い気がするが…。