New Year and Rainbow Roads [Good Bye 2017 F]

http://codeforces.com/contest/908/problem/F

数直線上にN点ある。
i番目の点はP[i]にあり、色はC[i]である。
色は赤R,青B,緑Gの3種類でP[i]は単調増加する。
この頂点内で辺をはり、赤の頂点のみを消したグラフ、青の頂点のみを消したグラフ、のどちらも全体が連結となる様な辺を張る。
点の距離を辺の重みとするとき、重みの総和の最小値は？

解法

http://codeforces.com/contest/908/submission/33792604

貪欲に作っていく。
緑を超えて辺を張る必要は内ので緑内での連結を考えていく。
ある緑とある緑の間では、以下のように辺を貼っていくのが最適。

|--R--R--R   R--R-|
G-B-B-B    B-B-B-G
|-------------------|

こうすると赤が消えても青が消えても連結を保てる。
しかし、場面によってはこのように繋いだ方がいい場合もある。

|--R--R--R--R--R-|
G-B-B-B--B-B-B-G

どちらの色を使っても連結なので、どちらが消えても連結を保てる。
緑と緑の間ではこの2通りを試し、最適な方を採用すればいい。
端の部分は

R--R---G
B---B---|

のようにやっていけばいい。
　
コーナーケースとして緑が一つもない場合がある。
この場合は全体で連結である必要は無いため、赤と青で最適に繋げばいい

  R--R--R
B--B--B--B

#define INF INT_MAX/2
typedef long long ll;
int N;
int P[301010]; char C[301010];
//---------------------------------------------------------------------------------------------------
vector<int> g;
ll ans = 0;
void corner() {
    int r = -1, b = -1;
    rep(i, 0, N) {
        if (C[i] == 'R') {
            if (0 < r) ans += P[i] - r;
            r = P[i];
        }
        if (C[i] == 'B') {
            if (0 < b) ans += P[i] - b;
            b = P[i];
        }
    }
}
//---------------------------------------------------------------------------------------------------
void pre() {
    int r = P[g[0]], b = P[g[0]];
    rrep(i, g[0] - 1, 0) {
        if (C[i] == 'R') {
            ans += r - P[i];
            r = P[i];
        }
        if (C[i] == 'B') {
            ans += b - P[i];
            b = P[i];
        }
    }
}
void post() {
    int n = g.size() - 1;
    int r = P[g[n]], b = P[g[n]];
    rep(i, g[n] + 1, N) {
        if (C[i] == 'R') {
            ans += P[i] - r;
            r = P[i];
        }
        if (C[i] == 'B') {
            ans += P[i] - b;
            b = P[i];
        }
    }
}
//---------------------------------------------------------------------------------------------------
void make(int gs, int gt) {
    vector<int> r, b;

    rep(i, gs + 1, gt) {
        if (C[i] == 'R') r.push_back(P[i]);
        else b.push_back(P[i]);
    }

    int rn = r.size();
    int bn = b.size();

    // line
    ll ans1 = INF;
    if (0 < rn and 0 < bn) {
        ans1 = 0;

        ans1 += r[0] - P[gs];
        rep(i, 0, rn - 1) ans1 += r[i + 1] - r[i];
        ans1 += P[gt] - r[rn - 1];

        ans1 += b[0] - P[gs];
        rep(i, 0, bn - 1) ans1 += b[i + 1] - b[i];
        ans1 += P[gt] - b[bn - 1];
    }
    
    // mountain
    ll ans2 = P[gt] - P[gs];

    if (rn) {
        ll left = 0, right = P[gt] - r[0];
        ll mi = right;
        rep(i, 0, rn - 1) {
            left = r[i] - P[gs];
            right = P[gt] - r[i + 1];
            mi = min(mi, left + right);
        }
        mi = min(mi, (ll)r[rn - 1] - P[gs]);
        ans2 += mi;
    }

    if (bn) {
        ll left = 0, right = P[gt] - b[0];
        ll mi = right;
        rep(i, 0, bn - 1) {
            left = b[i] - P[gs];
            right = P[gt] - b[i + 1];
            mi = min(mi, left + right);
        }
        mi = min(mi, (ll)b[bn - 1] - P[gs]);
        ans2 += mi;
    }

    ll an = min(ans1, ans2);
    ans += an;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> P[i] >> C[i];
    rep(i, 0, N) if (C[i] == 'G') g.push_back(i);

    if (g.size() == 0) corner();
    else {
        pre();
        int n = g.size();
        rep(i, 0, n - 1) make(g[i], g[i + 1]);
        post();
    }

    cout << ans << endl;
}