AtCoder Grand Contest 012E: Camel and Oases

https://agc012.contest.atcoder.jp/tasks/agc012_e

アイディア自体はすんなりいけたけどいろいろ勘違い+バグで無限に時間がかかった…。

とり方を見てみると、容量Vでジャンプしないで取るオアシスの区間,V/2で取る区間、(V/2)/2で取る区間…があって、それぞれの区間が互いに独立であることがわかります。つまり、スタート地点を含むVの区間でstrip,V/2でstrip...としていき、全オアシスが取れればPossible、そうでなければImpossibleとなります。この操作を逆に見ると、端から区間を好きな順番で取っていく操作になります。なので、
dp[bit]:=i番目のbitが立っている時、容量i番目の区間をすでにとっているとする。その時端から最大どこまで取れるか
として左端右端についてdpをしてあげればどの範囲がスタート地点として適しているか求めることができます。
doublingとかして高速化すればO(N(logN)^2)となり、低数倍も軽いので余裕で通ります。

といえば簡単だけど、意外と範囲がややこしくて結構苦戦しました。

さらに-1で初期化をしないと行けないところを0で初期化してバグらせました…。考察実装ともにパフォーマンスがひどいですねこれは…。

int N, V;
int M, SM;

int T[22][MAX_N];
int nex[22][MAX_N];

int dp[(1 << 22)], rdp[(1 << 22)];
int ok[MAX_N];

vector<ll> v;
ll A[MAX_N];

void pre(int dp[MAX_N]) {
	rep(i, 0, M) {
		rep(j, 0, N - 1) {
			T[0][j] = (abs(A[j + 1] - A[j]) > v[i]) ? j : (j + 1);
		}
		T[0][N - 1] = N - 1;
		rep(q, 0, 20) {
			rep(j, 0, N) {
				T[q + 1][j] = T[q][T[q][j]];
			}
		}
		rep(j, 0, N) {
			nex[i][j] = T[20][j];
		}
	}
	fill(dp, dp + (1 << SM), -1);
	rep(bit, 0, (1 << SM)) {
		if(dp[bit] == N - 1) continue;
		rep(i, 0, SM) {
			if(bit & (1 << i)) continue;
			MAX(dp[bit | (1 << i)], nex[i][dp[bit] + 1]);
		}
	}
	rep(bit, 0, (1 << SM)) {
		if(dp[bit] == N - 1) continue;
		dp[bit] = nex[SM][dp[bit] + 1];
	}
}

void solve() {
	cin >> N >> V;
	rep(i, 0, N) cin >> A[i];
	while(V >= 1) {
		v.pb(V);
		V /= 2;
	}
	v.pb(0);
	M = sz(v);
	SM = M - 1;

	reverse(all(v));
	
	pre(dp);

	reverse(A, A + N);
	pre(rdp);

	rep(bit, 0, (1 << SM)) rdp[bit] = N - 1 - rdp[bit];

	rep(bit, 0, (1 << SM)) {
		int rbit = (1 << SM) - 1 - bit;
		int l = dp[bit], r = rdp[rbit];
		l++;
		if(l > r) {
			ok[l]--;
			ok[r]++;
		}
	}
	rep(i, 0, N) {
		ok[i + 1] += ok[i];
		if(ok[i]) cout << "Possible\n";
		else cout << "Impossible\n";
	}
}