ABC479 D - Back and Forth Distance
- サイト
- AtCoder
- コンテスト
- ABC479
- 問題
- D - Back and Forth Distance
- 難易度
- -
個のマスが一列に並んでいます。マス からは、左側の好きなマスへコスト で、右側の好きなマスへコスト で移動できます。 個のクエリ について、マス からマス へ移動するときのコストの合計の最小値を求める問題です(、、、)。
の場合を考えます( の場合は左右を入れ替えるだけです)。
最初の移動で場合分けします。
- 最初に右へ移動する場合:コストは少なくとも かかります。一方、マス からマス へ直接移動すればコスト で着くので、この場合の最小値は です。
- 最初に左へ移動する場合:まずコスト がかかります。その後マス に行くには、どこかで右へ移動する必要があります。最初に右へ移動するまでは左にしか動いていないので、そのときにいるマス は を満たし、コスト がかかります。逆に、マス からマス へ移動し、マス からマス へ移動すれば、コスト で着きます。したがって、この場合の最小値は です。
まとめると、答えは
です( のときは )。 のときは同様に です。
は の先頭からの最小値(累積 min)、 は の末尾からの最小値なので、前計算しておけば各クエリに で答えられます。計算量は です。セグメント木で区間の最小値を求めても、 で間に合います。
Python
N, Q = map(int, input().split())L = [0, 0] + list(map(int, input().split()))R = [0] + list(map(int, input().split())) + [0]INF = 1 << 60pre = [INF] * Nfor i in range(1, N): pre[i] = min(pre[i - 1], R[i])suf = [INF] * (N + 2)for i in range(N, 1, -1): suf[i] = min(suf[i + 1], L[i])for _ in range(Q): s, t = map(int, input().split()) if s < t: print(min(R[s], L[s] + pre[s - 1])) else: print(min(L[s], R[s] + suf[s + 1]))L[i] が 、R[i] が になるように、先頭と末尾に を詰めています。pre[i] は 、suf[i] は で、範囲が空のときは INF です。 のときは pre[0] が INF なので、自動的に が答えになります( のときも同様です)。
C++
#include "shogo-library/algebra/monoid.hpp"#include "shogo-library/base/all"#include "shogo-library/data_structures/segtree.hpp"
void solve() { LL(N, Q); VL(L, N - 1); VL(R, N - 1); RMinQ<ll> segl(L), segr(R); rep(Q) { LL(s, t); s--, t--; ll ans = 1e18; if (s < t) { chmin(ans, R[s]); if (s > 0) { chmin(ans, segr.prod(0, s) + L[s - 1]); } } else { chmin(ans, L[s - 1]); if (s < N - 1) { chmin(ans, segl.prod(s, N - 1) + R[s]); } } print(ans); }}
int main() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); solve();}RMinQ は区間の最小値を求めるセグメント木で、prod(l, r) は半開区間 の最小値を返します。コードでは s を 0 始まりに直しているので、問題文のマス に対して L[s - 1] が 、R[s] が です。segr.prod(0, s) が 、segl.prod(s, N - 1) が にあたります。
使用ライブラリ:cpp_include@402f0cf