CS Academy Ultimate Orbs
リンク : https://csacademy.com/contest/archive/task/ultimateorbs/statement/
問題概要
N個のオーブがある。それぞれのオーブは隣のオーブが自身のコスト+D以下だと、隣のオーブの重さを吸収する。それぞれのオーブに関して、自身が最後まで残ることができるかどうか調べよ。
解説
とりあえず、重さが最大のオーブは必ず残ることができる。あるオーブiから初めて、最大のオーブを吸収することができれば最後まで残ることができる。さらにこのオーブiを吸収できれば...と続けていけば、すべて求めることできる。flag[i]を最後になれるかどうかだとする。重さが最大の場合は1に初期化しておく。ではどのように探索すればよいか考える。オーブiから見ていって、自身より重い最寄りのオーブに関して考える。手前のものをL[i]、奥のものをR[i]とする。(L[i],R[i])の和+DがL[i]、R[i]の重さより重ければL[i]、R[i]から始めることができる。そうでない場合は始められない。このように探索していくと、それぞれのオーブについて1回しか探索しないことになる。そうすることによってO(N)で解ける。
再帰的に考える発想は難しい・・・
LL n, d, L[1100000], R[1100000], flag[1100000],sum[1100000], cnt; Pll a[1100000]; bool func(int cur) { bool ret = 0; if (cur == -1 || cur == n)return 0; if (flag[cur] != -1)return flag[cur] == 1 ? 1 : 0; if (L[cur] == -1 && R[cur] == n)return flag[cur] = 1; LL num = sum[R[cur]] - sum[L[cur]+1] + d; if (num >= a[L[cur]].fir)ret |= func(L[cur]); if (num >= a[R[cur]].fir)ret |= func(R[cur]); return flag[cur] = ret; } int main() { cin >> n >> d; rep(i, n) { cin >> a[i].fir; a[i].sec = i; sum[i + 1] += sum[i] + a[i].fir; flag[i] = -1; } vector<Pll>vec; vec.push_back(Pll(INF, -1)); rep(i, n) { while (vec.back().fir <= a[i].fir)vec.pop_back(); L[i] = vec.back().sec; vec.push_back(a[i]); } vec.clear(); vec.push_back(Pll(INF, n)); Rrep(i, n) { while (vec.back().fir <= a[i].fir)vec.pop_back(); R[i] = vec.back().sec; vec.push_back(a[i]); } rep(i, n) { if (func(i)) { if (cnt)cout << " "; cout << i + 1; cnt++; } } cout << endl; return 0; }