# ARC121-B RGB Matching

1159diff
https://atcoder.jp/contests/arc181/tasks/arc181_b

## 解法

最適解において異なる色の犬とマッチングした犬の色の組の(多重)集合を $S$ とする。

$S$ に同じ色の組が含まれている場合、その2つの組を組み替えて同じ色の犬どうしをマッチングさせたとしても不満度は悪化しない。 (1)

赤、緑、青の犬の集合をそれぞれ$R, G, B$とする。$|R|, |G|, |B|$が全て偶数のときは明らかに不満度0を達成できる。

そうでないとき、$|R| + |G| + |B|$が偶数であることから、$|R|, |G|, |B|$のちょうど２つが偶数である。一般性を失わず$|R|, |G|$が偶数であると仮定する。

(1)より$S$として以下の2通りを調べれば良い
- $S = \{ (r, g) \}$
- $S = \{ (r, b), (g, b) \}$

前者に関しては片方固定して二分探索で良い。 $O(N\log N)$

後者に関しては、$G$が空なら不可能である。そうでなければbitDP(耳dp?)で$O(N\log N)$で不満度の最小が求まる
- $\text{dp}[i][j][k] :=$ $B$の昇順$i$要素のみを考慮した / $R$とマッチングした / $G$とマッチングした

## 提出コード

#include <bits/stdc++.h>

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int N;
    std::cin >> N;
    std::vector<long long> R, G, B;
    for (int i{} ; i < 2 * N ; i++) {
        long long a;
        char c;
        std::cin >> a >> c;
        if (c == 'R') R.push_back(a);
        if (c == 'G') G.push_back(a);
        if (c == 'B') B.push_back(a);
    }
    std::sort(R.begin(), R.end());
    std::sort(G.begin(), G.end());
    std::sort(B.begin(), B.end());
    if (R.size() % 2 == 0 and G.size() % 2 == 0 and B.size() % 2 == 0) {
        std::cout << 0 << '\n';
        return 0;
    }
    if (R.size() % 2 == 0) {
        std::swap(R, B);
    }
    else if (G.size() % 2 == 0) {
        std::swap(G, B);
    }
    assert(R.size() % 2);
    assert(G.size() % 2);
    const long long INF{(long long)1e18};
    auto f{[&](std::vector<long long>& tar, long long v) -> long long {
        auto it{std::lower_bound(tar.begin(), tar.end(), v)};
        long long res{INF};
        if (it != tar.end()) res = std::min(res, std::abs(v - *it));
        if (it != tar.begin()) res = std::min(res, std::abs(v - *std::prev(it)));
        return res;
    }};
    long long ans{(long long)1e18};
    for (int i{}, j{} ; i < (int)R.size() and j < (int)G.size() ; ) {
        if (j == (int)G.size()) {
            ans = std::min(ans, f(G, R[i]));
            i++;
        }
        else if (i == (int)G.size()) {
            ans = std::min(ans, f(R, G[j]));
            j++;
        }
        else if (R[i] < G[j]) {
            ans = std::min(ans, f(G, R[i]));
            i++;
        }
        else if (R[i] > G[j]) {
            ans = std::min(ans, f(R, G[j]));
            j++;
        }
        else {
            ans = 0;
            i++;
            j++;
        }
    }
    std::vector<long long> dp(4, INF);
    dp[0] = 0;
    for (auto x : B) {
        std::vector<long long> next{dp};
        for (int i{} ; i < 4 ; i++) {
            if (!(i & 1)) {
                next[i | 1] = std::min(next[i | 1], dp[i] + f(R, x));
            }
            if (!(i & (1 << 1))) {
                next[i | 2] = std::min(next[i | 2], dp[i] + f(G, x));
            }
        }
        dp = std::move(next);
    }
    ans = std::min(ans, dp[3]);
    std::cout << ans << '\n';
}

行数が多くなってしまったが、難しい処理は無くすんなり書けた気がする。

## 感想

数分でぱっと見えたけど、まぐれな気がする。

もうこの程度の難易度の問題がARC-Bに出ることはないのかな。