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"; } }