C - 最短の登山ルート / Shortest Mountain Climbing Route Editorial
by 
MMNMM
すべての \((l,r)\) について、\(\displaystyle\sum _ {i=l} ^ {r-1}|A _ {i+1}-A _ i|=\sum _ {i=l} ^ {r-1}\left|\overline A _ {i+1}-\overline A _ i\right|\) が成り立つことを、\(A\) と \(\overline A\) が等価であるということとします。 等価な列どうしはどのルートについても総高低差が等しいので、\(A\) を等価である列と入れ替えてもこの問題の答えは等しいです。
\(A\) と \(\overline A\) が等価であることの必要十分条件は、すべての \(i=1,2,\ldots,N-1\) に対して \(|A _ {i+1}-A _ i|=\left|\overline A _ {i+1}-\overline A _ i\right|\) が成り立つことです。
証明
\(A\) と \(\overline A\) が等価なら、\(l+1=r\) のときを考えることですべての \(i=1,2,\ldots,N-1\) に対して \(|A _ {i+1}-A _ i|=\left|\overline A _ {i+1}-\overline A _ i\right|\) が成り立つことがわかります。
また、すべての \(i=1,2,\ldots,N-1\) に対して \(|A _ {i+1}-A _ i|=\left|\overline A _ {i+1}-\overline A _ i\right|\) が成り立つなら、これを \(i=l,l+1,\ldots,r-1\) について足し合わせることで、\(A\) と \(\overline A\) が等価であることがわかります。
\(A\) と等価な広義単調増加列 \(\overline A\)があったとします。 単調増加性から \(\left|\overline A _ {i+1}-\overline A _ i\right|=\overline A _ {i+1}-\overline A _ i\) となるので、\(\displaystyle\sum _ {i=l} ^ {r-1}\left|\overline A _ {i+1}-\overline A _ i\right|=\overline A _ r-\overline A _ l\) が成り立ちます。 つまり、この問題は次のように言い換えることができます。
\(\overline A _ x-\overline A _ y\ge K\) となるような \((x,y)\) における、\(x-y+1\) の最小値を求めよ。
これは、\(\overline A\) が広義単調増加なので尺取り法や二分探索などを用いて解くことができます。
\(\overline A\) として \(|A _ {i+1}-A _ i|\) の先頭からの累積和を用いることで、この問題を解くことができました。
実装例は以下のようになります。 尺取り法と二種類の二分探索による実装例をそれぞれ示します。
C++
尺取り法
#include <iostream>
#include <vector>
using namespace std;
int main() {
int N;
long K;
cin >> N >> K;
// 等価な単調増加列を作る
vector<long> equiv_A{0};
int prev_A;
cin >> prev_A;
for (int i = 1; i < N; ++i) {
int A;
cin >> A;
equiv_A.emplace_back(equiv_A.back() + abs(A - prev_A));
prev_A = A;
}
// 尺取り法
int ans = N + 1;
for (int i = 0, j = 0; i < N; ++i) {
while (j < N && equiv_A[i] + K > equiv_A[j]) ++j; // 差が K 未満であるかぎり右端を進めて
if (j < N) { // K 以上になったら
ans = min(ans, j - i + 1); // 地点数を更新
}
}
if (ans > N) {
cout << -1 << endl;
} else {
cout << ans << endl;
}
return 0;
}
要素ごとに二分探索
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int N;
long K;
cin >> N >> K;
// 等価な単調増加列を作る
vector<long> equiv_A{0};
int prev_A;
cin >> prev_A;
for (int i = 1; i < N; ++i) {
int A;
cin >> A;
equiv_A.emplace_back(equiv_A.back() + abs(A - prev_A));
prev_A = A;
}
int ans = N + 1;
for (int i = 0; i < N; ++i) {
// 二分探索で差が K 以上になるところを見つける
int j = ranges::lower_bound(equiv_A, equiv_A[i] + K) - equiv_A.begin();
if (j < N) { // 存在すれば
ans = min(ans, j - i + 1); // 地点数を更新
}
}
if (ans > N) {
cout << -1 << endl;
} else {
cout << ans << endl;
}
return 0;
}
答えで二分探索
#include <iostream>
#include <vector>
#include <algorithm>
#include <ranges>
using namespace std;
int main() {
int N;
long K;
cin >> N >> K;
// 等価な単調増加列を作る
vector<long> equiv_A{0};
int prev_A;
cin >> prev_A;
for (int i = 1; i < N; ++i) {
int A;
cin >> A;
equiv_A.emplace_back(equiv_A.back() + abs(A - prev_A));
prev_A = A;
}
// 答えで二分探索
int ans = *ranges::partition_point(views::iota(1, N + 1), [N, K, &equiv_A](int X) {
for (int i = 0; i + X - 1 < N; ++i) {
if (equiv_A[i + X - 1] - equiv_A[i] >= K) { // 地点数が X で差が K 以上のペアがあれば
return false; // 答えは X 以下
}
}
return true; // 無ければ答えは X より大きい
});
if (ans > N) {
cout << -1 << endl;
} else {
cout << ans << endl;
}
return 0;
}
Python
尺取り法
N, K = map(int, input().split())
A = list(map(int, input().split()))
# 等価な単調増加列を作る
equiv_A = [0] + [abs(a - b) for a, b in zip(A, A[1:])]
for i in range(1, N):
equiv_A[i] += equiv_A[i - 1]
# 尺取り法
j = 0
ans = N + 1
for i in range(N):
while j < N and equiv_A[i] + K > equiv_A[j]: # 差が K 未満であるかぎり
j += 1 # 右端を進めて
if j < N: # K 以上になったら
ans = min(ans, j - i + 1) # 地点数を更新
if ans > N:
print(-1)
else:
print(ans)
要素ごとに二分探索
from bisect import bisect_right
N, K = map(int, input().split())
A = list(map(int, input().split()))
# 等価な単調増加列を作る
equiv_A = [0] + [abs(a - b) for a, b in zip(A, A[1:])]
for i in range(1, N):
equiv_A[i] += equiv_A[i - 1]
# 尺取り法
ans = N + 1
for i in range(N):
# 二分探索で差が K 以上になるところを見つける
j = bisect_right(equiv_A, equiv_A[i] + K)
if j < N: # K 以上になったら
ans = min(ans, j - i + 1) # 地点数を更新
if ans > N:
print(-1)
else:
print(ans)
答えで二分探索
N, K = map(int, input().split())
A = list(map(int, input().split()))
# 等価な単調増加列を作る
equiv_A = [0] + [abs(a - b) for a, b in zip(A, A[1:])]
for i in range(1, N):
equiv_A[i] += equiv_A[i - 1]
# 二分探索の判定関数
def check(X):
for l, r in zip(equiv_A, equiv_A[X - 1:]):
if r - l >= K: # 地点数が X で差が K 以上のペアがあれば
return False # 答えは X 以下
return True # なければ X より大きい
l = 1
r = N + 1
while l + 1 < r:
m = (l + r) // 2
if check(m):
l = m
else:
r = m
if r > N:
print(-1)
else:
print(r)
posted:
last update: