NoiminのNoise

競技プログラミング (多め) とWeb (たまに) ,自然言語処理 (ブログではまだ)。数式の書き方を一気に KaTeX に変えようとして記事を全削除してインポートし直すなどしたので,過去にブックマークされた記事は URL が変わってしまっている可能性があります…….

Educational Codeforces Round 42 (Rated for Div. 2) E. Byteland, Berland and Disputed Cities

問題: https://codeforces.com/contest/962/problem/E

公式解説: https://codeforces.com/blog/entry/58869

問題概要

1次元の座標軸の上に n 個の街が並んでいる.街の座標は整数で,昇順に与えられる.街は 3 つの種類があり,それぞれ

  • Byteland の街 (B)
  • Berland の街 (R)
  • 紛争中の街 (P)

である.

これらの街をネットワークで結びたい.ただし,2 つの街を結ぶにはそれらの街の間の距離だけコストがかかる.以下の 2 つの条件を両方満たすように街を結ぶとき,最小コストを求めよ.

  • B の街と P の街の集合について,集合内の街だけを辿って任意の街から任意の街に行ける.
  • R の街と P の街の集合について,集合内の街だけを辿って任意の街から任意の街に行ける.

解法概要

まず,比較的簡単なのが P がない場合.ただ R の街たちと B の街たちを順番に繋げばOK.

以下,P がある場合を考える.毎度のごとく考察ノートの抜粋で恐縮だが, P を軸に以下の 2 パターンの結び方を考えてコストの小さい方を取れば良い.

f:id:noimin:20190404215322j:plain

type 1 は隣り合う P 同士を結んで,その間に入っている R と B も R 同士や B 同士で結ぶ結び方である.ただし, R と B それぞれについて最も間が空いているところだけは結ばないことで,コストを最小に抑える.

type 2 は P 同士を直接は結ばず, R を通るルートと B を通るルートの 2 つを作る結び方である.ただしこの結び方は P 同士の間に R と B の両方がある場合しかできない.片方しかない場合にこの結び方をやろうとすると,与えられた 2 つの条件のうち片方しか満たせなくなってしまう.

また,両端の P よりも端に出てくる B と R を考慮するのを忘れないように注意する.

ちなみに私が引っかかった点の 1 つに,「R か B のどちらかがあり,もう片方がない場合」に満たすべき条件が挙げられる.例えば, R と P だけがあり, Bがない場合に満たすべき条件は

  • R の街と P の街の集合について,集合内の街だけを辿って任意の街から任意の街に行ける.
  • P の街の集合について,集合内の街だけを辿って任意の街から任意の街に行ける.

の 2 つである.

B がない場合について,ずっと 2 番目の条件を考慮しないまま考察を進めていた.

ソースコード

#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>

#define debug(x) cerr << #x << ": " << x << endl

using namespace std;

typedef long long ll;
typedef pair<ll, ll> Pll;

const int MAX_N = 200000;
const ll INF = (1LL << 60);

int main() {
    int n;
    cin >> n;

    vector<Pll> cities;
    ll x, y;
    char c;
    bool exists_P = false;
    for(int i=0;i<n;++i) {
        cin >> x >> c;
        y = (c == 'R')?2:((c == 'B')?1:0);
        if(y == 0) exists_P = true;
        cities.emplace_back(x, y);
    }

    ll ans = 0LL;

    // P がないので R 同士 B 同士を繋ぐ
    if(!exists_P) {
        ll prev[3] = {-1, -1, -1};
        for(int i=0;i<n;++i) {
            if(prev[cities[i].second] != -1) {
                ans += cities[i].first - cities[prev[cities[i].second]].first;
            }
            prev[cities[i].second] = i;
        }
        cout << ans << endl;
        return 0;
    }

    // Pがある
    vector<Pll> prev(3, {-1, -1});
    ll max_gap[3] = {0, 0, 0};
    for(int i=0;i<n;++i) {
        // 見ている街が P のときだけ答えを増やすようにしたら見通しが良くなった気がする
        if(cities[i].second == 0) {
            if(prev[0].first == -1) {
                for(int j=1;j<=2;++j) {
                    if(prev[j].first != -1) ans += cities[i].first - cities[prev[j].first].first;
                }
            } else {
                // 繋ぎ方パターン 1 (P同士を繋ぐ)
                ll tmp1 = cities[i].first - cities[prev[0].first].first;
                for(int j=1;j<=2;++j) {
                    if(prev[1].first != -1) {
                        max_gap[1] = max(max_gap[1], cities[i].first - cities[prev[1].second].first);
                        tmp1 += cities[i].first - cities[prev[0].first].first - max_gap[1];
                    }
                }
                // 繋ぎ方パターン 2 (P同士を繋がない)
                // この繋ぎ方は P と P の間に R と B の両方がないとやっちゃダメ
                ll tmp2 = INF;
                if(prev[1].first != -1 && prev[2].first != -1) {
                    tmp2 = 2 * (cities[i].first - cities[prev[0].first].first);
                }
                // 小さい方を採用
                ans += min(tmp1, tmp2);
            }
            for(int j=0;j<=2;++j) {
                prev[j] = {-1, -1};
                max_gap[j] = 0;
            }
            prev[0].first = i;
        } else {
            if(max(prev[0].first, prev[cities[i].second].second) != -1) {
                max_gap[cities[i].second] = max(
                    max_gap[cities[i].second], 
                    cities[i].first - cities[max(prev[0].first, prev[cities[i].second].second)].first
                );
            }
            if(prev[cities[i].second].first == -1) prev[cities[i].second].first = i;
            prev[cities[i].second].second = i;
        }
    }
    for(int j=1;j<=2;++j) {
        if(prev[0].first < prev[j].first) ans += cities[prev[j].second].first - cities[prev[0].first].first;
    }

    cout << ans << endl;
}

所感

WA と RE を計 23 回出しながら頑張りました.