http://arc072.contest.atcoder.jp/tasks/arc072_c
類題解いていたのでイケた。
i回目から行動を始めてたどり着くことが出来なかった座標の集合を考えて、その集合のうち目的地からの距離が最も小さいものだけを持っておけばよい。
これは行動を逆から見ることで簡単に各iについて求めることができる。
int N, S, Q; int A[MAX_N]; ll B[MAX_N], C[MAX_N]; bool ans[MAX_N]; void solve() { cin >> N >> S; rep(i, 0, N) cin >> A[i]; B[N] = 1; for(int i = N - 1; i >= 0; i--) { if(A[i] / 2 < B[i + 1]) B[i] = A[i] + B[i + 1]; else B[i] = B[i + 1]; } C[0] = S; for(int i = 1; i <= N; i++) { if(C[i - 1] - A[i - 1] >= 0) C[i] = min(C[i - 1], C[i - 1] - A[i - 1]); else C[i] = min(C[i - 1], A[i - 1] - C[i - 1]); } for(int i = 0; i < N; i++) { if(B[i + 1] <= C[i]) ans[i] = true; else ans[i] = false; } cin >> Q; while(Q--) { int a; cin >> a; a--; if(ans[a]) cout << "YES\n"; else cout << "NO\n"; } }
最大値最小値に注目するのは
AtCoder Regular Contest 075 E: Meaningful Mean - omochan's diary
でも使った。