ABC197-E 解説

E - Traveler

各色ごとに回収する順番を考えます。色 $i$ に対して、最も座標が小さいものを $Min_i$ 、最も座標が大きいものを $Max_i$ とすると、簡単に言えば $Max_i$ までまっすぐ行ってから $Min_i$ に行く、または $Min_i$ までまっすぐ行ってから $Max_i$ に行くのが最適です。

よって、DPできます。具体的には、各色に対して最も座標が小さいもの、最も座標が大きいもののそれぞれに到達するまでにかかる最小の時間を持ちます。

inf = 1500000000
N = int(input())
Min, Max = [inf] * N, [-inf] * N
for _ in range(N):
    X, C = map(int, input().split())
    C -= 1
    Min[C] = min(Min[C], X)
    Max[C] = max(Max[C], X)
dp0, dp1, pre_min, pre_max = 0, 0, 0, 0
for i in range(N):
    if Min[i] == inf:
        continue
    m = abs(Max[i] - Min[i])
    dp0, dp1 = min(dp0 + abs(Max[i] - pre_min), dp1 + abs(Max[i] - pre_max)) + m, min(dp0 + abs(Min[i] - pre_min), dp1 + abs(Min[i] - pre_max)) + m
    pre_min = Min[i]
    pre_max = Max[i]
print(min(dp0 + abs(pre_min), dp1 + abs(pre_max)))

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = 1500000000;

int main() {
    int N;
    cin >> N;
    vector<int> Min(N, inf), Max(N, -inf);
    for (int i = 0; i < N; i++) {
        int X, C;
        cin >> X >> C;
        C--;
        Min[C] = min(Min[C], X);
        Max[C] = max(Max[C], X);
    }
    ll dp0 = 0, dp1 = 0, pre_min = 0, pre_max = 0;
    for (int i = 0; i < N; i++) {
        if (Min[i] == inf) {
            continue;
        }
        int m = abs(Max[i] - Min[i]);
        ll ndp0 = min(dp0 + abs(Max[i] - pre_min), dp1 + abs(Max[i] - pre_max)) + m;
        ll ndp1 = min(dp0 + abs(Min[i] - pre_min), dp1 + abs(Min[i] - pre_max)) + m;
        dp0 = ndp0;
        dp1 = ndp1;
        pre_min = Min[i];
        pre_max = Max[i];
    }
    cout << min(dp0 + abs(pre_min), dp1 + abs(pre_max)) << '\n';
}