# [CSP-S 2026] 迁徙 / migrate 题解 – 孤独的Bochi

アイデア

まず暴力的なdpを検討し、検討してください \(f_i\) 出発点として \（私\） 正しい地点への最短経路、\(\演算子名{距離}(i,j)\) ポイントとして \（私\） 要点まで \(j\) 最短距離は、列挙の左端点です。 \(l\)：

\[\Large{f_i=\sum_{x_j + d \ge x_i且\operatorname{dist}(l,j) + 1 = \operatorname{dist}(l,i)}f_j}
\]

時間の複雑さ \(\シータ(n^3)\)

最適化する方法を検討します。

\(\演算子名{距離}(l,i)\) シーケンス全体は多くのレイヤーに分割されます。最短パスはさらに右へ進むために貪欲でなければならないため、1 つのレイヤーの転送は前のレイヤーの最後の 3 つの数字にのみ関連します。現在のレイヤーの最後の 3 つの数値のオプションの数を次のように考慮します。 \(x,y,z\) 。メモ化された検索を検討しますが、州が多すぎて覚えられません

転送プロセスを検討してください。いつ \(z = 2\) いつ、からのみ\(z\) 転送、それ以外の場合 \(z = 1,y = 1\) から入手できます\(x, y\) 転送します。そうでない場合は転送できません。

それで、できます \(z > 2,y>1,x>0\) 一つの状態にプレスされると、取り付けることができます。

答えは \(\sum_{i = 1}^n \演算子名{dfs}(i,0,0,1)\)

時間の複雑さ \(\シータ(n)\)。

コード：

\(\text{C++コード:}\)

#include
#define int long long
using namespace std;
constexpr int MAXN = 2e6 + 5;
int f[MAXN][2][3][4];
int x[MAXN];
int nxt[MAXN];
int n, d;
int dfs(int cur, int x, int y, int z) {
	if (cur == n || !z || z > 2) return 0 ;
	if (~f[cur][x][y][z]) return f[cur][x][y][z];  
	int res = 0;
	int pos_x = x ? nxt[cur - 2] : cur,
		pos_y = y ? nxt[cur - 1] : cur,
		pos_z = z ? nxt[cur] : cur;
	int nxt_pos = nxt[cur];
	int nxt_x = 0, nxt_y = 0, nxt_z = 0;
	if (nxt_pos > cur) {
		nxt_z = z;
		if (pos_y >= nxt_pos) nxt_z += y;
		if (pos_x >= nxt_pos) nxt_z += x;
	}
	if (nxt_pos - 1 > cur) {
		nxt_y = z;
		if (pos_y >= nxt_pos - 1) nxt_y += y;
		if (pos_x >= nxt_pos - 1) nxt_y += x;
	}
	if (nxt_pos - 2 > cur) {
		nxt_x = z;
		if (pos_y >= nxt_pos - 2) nxt_x += y;
		if (pos_x >= nxt_pos - 2) nxt_x += x;
	} 
	if (z == 2) 
		res += pos_z - pos_y;
	else if (y == 1)
		res += pos_y - pos_x;
  
	res += dfs(nxt_pos, min(1ll, nxt_x), min(2ll, nxt_y), min(3ll, nxt_z));
	return f[cur][x][y][z] = res;
}
void solve() {
	cin >> n >> d;
	for (int i = 1; i <= n; ++i) 
		cin >> x[i];
	for (int l = 1, r = 1; l <= n; ++l) {
		while (r < n && x[l] + d >= x[r + 1]) ++r;
		nxt[l] = r;
	}
//	for (int i = 1; i <= n; ++i)
//		cerr << nxt[i] << ' ';
//	cerr << '\n';
	int ans = 0;
	for (int i = 1; i <= n; ++i)
		for (int j = 0; j < 2; ++j)
			for (int k = 0; k < 3; ++k)
				for (int l = 0; l < 4; ++l)
					f[i][j][k][l] = -1;
	for (int i = 1; i <= n; ++i)
		ans += dfs(i, 0, 0, 1);
	cout << ans << '\n';
}
signed main() {
#ifndef DEBUG
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	freopen("migrate.in", "r", stdin);
	freopen("migrate.out", "w", stdout);
#else
#endif
	int c, T;
	cin >> c >> T;
	while(T--) solve();
	return 0;
}