コンテンツにスキップ

ABC479 D - Back and Forth Distance

サイト
AtCoder
コンテスト
ABC479
問題
D - Back and Forth Distance
難易度
-

NN 個のマスが一列に並んでいます。マス ii からは、左側の好きなマスへコスト LiL_i で、右側の好きなマスへコスト RiR_i で移動できます。QQ 個のクエリ (s,t)(s, t) について、マス ss からマス tt へ移動するときのコストの合計の最小値を求める問題です(2≤N≤3×1052 \le N \le 3 \times 10^5、1≤Q≤3×1051 \le Q \le 3 \times 10^5、1≤Li,Ri≤1091 \le L_i, R_i \le 10^9、s≠ts \ne t)。

s<ts < t の場合を考えます(s>ts > t の場合は左右を入れ替えるだけです)。

最初の移動で場合分けします。

  • 最初に右へ移動する場合:コストは少なくとも RsR_s かかります。一方、マス ss からマス tt へ直接移動すればコスト RsR_s で着くので、この場合の最小値は RsR_s です。
  • 最初に左へ移動する場合:まずコスト LsL_s がかかります。その後マス tt に行くには、どこかで右へ移動する必要があります。最初に右へ移動するまでは左にしか動いていないので、そのときにいるマス jj は j<sj < s を満たし、コスト RjR_j がかかります。逆に、マス ss からマス jj へ移動し、マス jj からマス tt へ移動すれば、コスト Ls+RjL_s + R_j で着きます。したがって、この場合の最小値は Ls+min⁡j<sRjL_s + \min_{j < s} R_j です。

まとめると、答えは

min⁡(Rs, Ls+min⁡1≤j<sRj)\min\left(R_s,\ L_s + \min_{1 \le j < s} R_j\right)

です(s=1s = 1 のときは RsR_s)。s>ts > t のときは同様に min⁡(Ls, Rs+min⁡s<j≤NLj)\min\left(L_s,\ R_s + \min_{s < j \le N} L_j\right) です。

min⁡j<sRj\min_{j < s} R_j は RR の先頭からの最小値(累積 min)、min⁡j>sLj\min_{j > s} L_j は LL の末尾からの最小値なので、前計算しておけば各クエリに O(1)O(1) で答えられます。計算量は O(N+Q)O(N + Q) です。セグメント木で区間の最小値を求めても、O((N+Q)log⁡N)O((N + Q) \log N) で間に合います。

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 << 60
pre = [INF] * N
for 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] が LiL_i、R[i] が RiR_i になるように、先頭と末尾に 00 を詰めています。pre[i] は min⁡(R1,…,Ri)\min(R_1, \dots, R_i)、suf[i] は min⁡(Li,…,LN)\min(L_i, \dots, L_N) で、範囲が空のときは INF です。s=1s = 1 のときは pre[0] が INF なので、自動的に RsR_s が答えになります(s=Ns = N のときも同様です)。

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) は半開区間 [l,r)[l, r) の最小値を返します。コードでは s を 0 始まりに直しているので、問題文のマス ss に対して L[s - 1] が LsL_s、R[s] が RsR_s です。segr.prod(0, s) が min⁡j<sRj\min_{j < s} R_j、segl.prod(s, N - 1) が min⁡j>sLj\min_{j > s} L_j にあたります。

使用ライブラリ:cpp_include@402f0cf