AOJ2445: MinimumCostPath

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2445

N<400の時は愚直に求めることにします。
N>=400の時は、
左下、右上の100x100領域に注目します。
(0,0)->(左下の領域)->(真ん中の領域)->(右上の領域)->(N-1,N-1)と移動していくことになりますが、
真ん中の領域では必ず右または上のみの移動になります。

これを証明するためには、任意の経路を経路長を伸ばすことなく、真ん中の領域で右または上のみ移動する経路に変換できることを示せばよいです。
左下の領域から初めて出た場所を(x,100)とします。対称性より(100,y)の時も同様です。
0<=y<100において、障害物がない行が必ず存在します。その行を通って左下の領域から出ると、右または上のみの移動で、右上の領域に入ることが出来ます。
このとき経路長は伸びません。

この事実により、左下の領域から出た座標と右上の領域に入った座標について、最短経路の本数を求めれば良くなり、これは
https://atcoder.jp/contests/dp/tasks/dp_y
です。最後に通った障害物で包除する感じです。

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int N, M;
int X[110], Y[110];
int B[510][510];
ll D[510][510];

void pre(int l, int r, int x, int y) {
	int n = r - l;
	rep(i, 0, n) {
		rep(j, 0, n) {
			B[i][j] = inf;
		}
	}
	rep(i, 0, M) {
		if(l <= X[i] && X[i] < r && l <= Y[i] && Y[i] < r) {
			B[X[i] - l][Y[i] - l] = -1;
		}
	}
	memset(D, 0, sizeof(D));
	x -= l;
	y -= l;
	queue<pi> que;
	que.push(pi(x, y)); 
	B[x][y] = 0;
	D[x][y] = 1;
	while(!que.empty()) {
		pi p = que.front(); que.pop();
		rep(i, 0, 4) {
			int nx = p.fst + dx[i], ny = p.sec + dy[i];
			if(0 <= nx && nx < n && 0 <= ny && ny < n && B[nx][ny] != -1) {
				if(B[nx][ny] >= B[p.fst][p.sec] + 1) {
					ADD(D[nx][ny], D[p.fst][p.sec]);
					if(B[nx][ny] > B[p.fst][p.sec] + 1) {
						B[nx][ny] = B[p.fst][p.sec] + 1;
						que.push(pi(nx, ny));
					}
				}
			}
		}
	}
}

ll qre(int x1, int y1, int x2, int y2) {
	vector<pi> vec;
	// debug(x1, y1, x2, y2);
	rep(i, 0, M) {
		if(x1 == X[i] && y1 == Y[i]) return 0;
		if(x2 == X[i] && y2 == Y[i]) return 0;
		if(x1 <= X[i] && X[i] <= x2 && y1 <= Y[i] && Y[i] <= y2) vec.pb(pi(X[i], Y[i]));
	}
	vec.pb(pi(x1, y1));
	vector<ll> dp(sz(vec), 0);
	sort(all(vec));
	rer(i, sz(vec), 0) {
		int a = vec[i].fst, b = vec[i].sec;
		dp[i] = C(x2 - a + y2 - b, x2 - a);
		rep(j, i + 1, sz(vec)) {
			int c = vec[j].fst, d = vec[j].sec;
			ADD(dp[i], mod - dp[j] * C(c - a + d - b, d - b) % mod);
		}
	}
	return dp[0];
}

void solve() {
	int bound = 100;
	cin >> N >> M;
	C_init(2 * N);
	rep(i, 0, M) {
		cin >> X[i] >> Y[i];
		X[i]--; Y[i]--;
	}
	if(N < 400) {
		pre(0, N, 0, 0);
		cout << D[N - 1][N - 1] << "\n";
	}
	else {
		vector<pair<pi, pl>> vl, vr;
		pre(0, bound, 0, 0);
		rep(i, 0, bound) {
			if(B[i][bound - 1] != -1)
			vl.pb(make_pair(pi(i, bound), pl(B[i][bound - 1] + 1, D[i][bound - 1])));
			if(B[bound - 1][i] != -1)
			vl.pb(make_pair(pi(bound, i), pl(B[bound - 1][i] + 1, D[bound - 1][i])));
		}
		pre(N - bound, N, N - 1, N - 1);
		rep(i, 0, bound) {
			if(B[i][0] != -1)
			vr.pb(make_pair(pi(N - bound + i, N - bound - 1), pl(B[i][0] + 1, D[i][0])));
			if(B[0][i] != -1)
			vr.pb(make_pair(pi(N - bound - 1, N - bound + i), pl(B[0][i] + 1, D[0][i])));
		}
		ll md = inf;
		rep(i, 0, sz(vl)) {
			rep(j, 0, sz(vr)) {
				ll v = vl[i].sec.fst + vr[j].sec.fst + (vr[j].fst.sec - vl[i].fst.sec) + (vr[j].fst.fst - vl[i].fst.fst);
				MIN(md, v);
				// debug(v, vl[i], vr[j]);
			}
		}
		// debug(md, vl, vr);
		ll res = 0;
		rep(i, 0, sz(vl)) {
			rep(j, 0, sz(vr)) {
				if(md == vl[i].sec.fst + vr[j].sec.fst + (vr[j].fst.sec - vl[i].fst.sec) + (vr[j].fst.fst - vl[i].fst.fst)) {
					ADD(res, vl[i].sec.sec * vr[j].sec.sec % mod 
							* qre(vl[i].fst.fst, vl[i].fst.sec, vr[j].fst.fst, vr[j].fst.sec) % mod);
				}
			}
		}
		cout << res << "\n";
	}
}

2パートあるだけで実装辛くなる…