E - Traveler

問題

個のボールが与えられる。ボールは、座標軸上に位置し、その色はである。
座標軸を移動しながらボールの色が広義単調増加となるように回収する時、移動するコストを最小化せよ。
atcoder.jp

考察

色ごとにDPしたくなるが、各色と次の色の間ですべての推移を試すのは容易ではない。これは実際に推移する辺を貼ってみると、辺の数が非常に大きくなることからわかる。

そこで、同じ色のボールを回収する方法について試してみる。同じ色のボールを回収する始点と終点をうまく決めることができれば、推移の数を減らせるだろう。

となる同じ色のボールを考える
　とおく。また、をAからBまでの距離を表すものとする。

まずは始点、終点がともに端点である場合を考えると、　である。

つまり、同じ色のボールについて、端点(最小の座標軸にある点）から端点までボールを回収する場合は、途中で戻る必要がないため上記の式のようになる。

では、端点以外の点(例えば, )の場合を考えてみよう。を始点して、最初にのボールを回収すると
となる。このような感じで、端点以外の頂点を始点とすると、端点から端点に移動する場合に比べてコストがかかることがわかる。

言い換えると、ボールを回収する最も効率的な動き方端点から端点で、そのコストはである

これより、各色のボールについて、端点から次のボールの色の端点に移動する場合を動的計画法で探索すれば良い。
色として、各端点をとするとを試して最小値を取れば良い。

解法

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using Int = long long;
using namespace std;

int main()
{
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    
    int N; cin >> N;
    map<Int,vector<Int>>mp;
    
    for(int i = 0; i < N; ++i)
    {
        Int x,c;
        cin >> x >> c;
        mp[c].push_back(x);
    }

    map<Int,Int>cnt;
    for(auto& itr : mp)
    {
        sort(itr.second.begin(),itr.second.end());
        Int prev = itr.second.front();
        for (const auto e : itr.second)
        {
            cnt[itr.first] += abs(e - prev);
            prev = e;
        }
    }
    vector<vector<Int>>dp(2, vector<Int>(mp.size(), 0LL));
    
    Int l = 0,r = 0;
    int i = 0;
    
    for(auto& itr : mp)
    {
        Int nl = itr.second.front();
        Int nr = itr.second.back();
        
        if(i)
        {
            dp[1][i] = min(dp[0][i - 1] + abs(nl - l), dp[1][i - 1] + abs(nl - r)) + cnt[itr.first];
            dp[0][i] = min(dp[1][i - 1] + abs(nr - r), dp[0][i - 1] + abs(nr - l)) + cnt[itr.first];
        }
        else
        {
            dp[1][i] = min(abs(nl - l), abs(nl - r)) + cnt[itr.first];
            dp[0][i] = min(abs(nr - r), abs(nr - l)) + cnt[itr.first];
        }
        
        l = nl;
        r = nr;
        
        if(i + 1 == mp.size())
        {
            dp[1][i] += abs(itr.second.back());
            dp[0][i] += abs(itr.second.front());
        }
        ++i;
    }
    
    cout << min(dp[0].back(), dp[1].back()) << endl;
}