square869120Contest #1 : D - square1001の通学経路

最後は時間切れ。
http://s8pc-1.contest.atcoder.jp/tasks/s8pc_1_d

問題

2次元座標上において、隣接する格子点同士が辺で結ばれている。
点(1,1)から、右または上の隣接する格子点への移動を繰り返し、点(W,H)に移動したい。

その際、K個のマスを全て経由したい。
各マス(X[i],Y[i])は、(X[i],Y[i]),(X[i]+1,Y[i]),(X[i],Y[i]+1),(X[i]+1,Y[i]+1)の格子点のいずれか１つ以上を経由すると訪問したとみなされる。

全マスを経由して点(W,H)に移動する移動経路は何通りあるか。

解法

色々な方法があるようだが、概ね共通して各マスに対応して(X[i]+1,Y[i]),(X[i],Y[i]+1)のどちらか片方を通らなければいけないという特徴を利用するようだ。
また、この２点は同時に通ることはできない。

例えば以下の方法がある。

• これらの２格子点に得点を１点追加し、DPで点(W,H)に到達するまでに取得する最大ポイント数とその組み合わせを求めていく。
  • 最終的にK点得点を得られるなら、その時の組み合わせが解。
• (X[i]+1,Y[i])と(X[i],Y[i]+1)のどちらかを通らなければいけないということは、逆にx+y=X[i]+Y[i]+1を満たす各頂点(x,y)について、左記２点以外は通ってはいけないことになる。
  • ここから通ってはいけない頂点を列挙したうえでDPする。

以下のコードは後者。

int H,W,K;

int NG[2020][2020];
ll dp[2020][2020];
ll mo=1000000007;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>K;
	H--,W--;
	FOR(i,K) {
		cin>>x>>y;
		x--,y--;
		r=x+y+1;
		FOR(j,r+1) if(j!=x&&j!=x+1) NG[j][r-j]=1;
	}
	
	dp[0][0]=1;
	FOR(y,H+1) FOR(x,W+1) if((x||y) && NG[x][y]==0) {
		if(x) dp[x][y]+=dp[x-1][y];
		if(y) dp[x][y]+=dp[x][y-1];
		dp[x][y]%=mo;
	}
	cout<<dp[W][H]<<endl;
}

まとめ

本番もっと面倒なコードを書いたが、整理したらずいぶん単純になった。