ARC 121

Wed, May 14, 2025

A. 2nd Greatest Distance

https://atcoder.jp/contests/arc121/tasks/arc121_a

B. RGB Matching

https://atcoder.jp/contests/arc121/tasks/arc121_b

赤の個数を $N_R$、緑の個数を $N_G$、緑の個数を $N_B$ とする。 $N_R + N_G + N_B \equiv 0 \mod 2$ より、3つの数の組み合わせは偶数3つ、または、奇数2つと偶数1つである。全て偶数のときは同じ色同士で組を作れば良いから不満の総和は 0 である。

以降、赤と緑の個数が奇数となり、青の個数が偶数とする。

このとき、以下の2パターンが考えられる。

赤と緑で1つ組を作り、それ以外は同じ色同士で組を作る
赤と青で1つ、緑と青で1つ組を作り、それ以外は同じ色同士で組を作る

2パターンのうちの不満の総和が最小のほうが答え。

(1) のとき、差が一番小さいようなものを調べればよい。

(2) のとき、$r_i$ を $i$ 番目の青と組を作ったときに一番不満が小さくなるように赤を選んだときの不満の値とする。同様に緑に対して $g_i$ を定義する。 $dp(i, state)$ を青を $i$ 番目まで見て $state$ 状態になったときの不満の総和の最小値とする。ここで $state$ は以下のように定義する。

$state=1$: 赤とペアを組む青が決まっている
$state=2$: 緑とペアを組む青が決まっている
$state=3$: 赤と緑とペアを組む青が決まっている

\begin{align*} dp(i, 1) &= \min(dp(i-1, 1), r_i) \\ dp(i, 2) &= \min(dp(i-1, 2), g_i) \\ dp(i, 3) &= \min(r_i + dp(i-1, 2), g_i + dp(i-1, 1), dp(i-1, 3)) \end{align*}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    N *= 2;
    vector<pair<ll, char>> ps;
    rep(i, N) {
        ll a;
        char c;
        cin >> a >> c;
        ps.emplace_back(a, c);
    }

    int numr = 0, numg = 0, numb = 0;
    vll R, G, B;
    for (auto [a, c] : ps) {
        if (c == 'R') {
            numr++;
            R.push_back(a);
        }
        if (c == 'G') {
            numg++;
            G.push_back(a);
        }
        if (c == 'B') {
            numb++;
            B.push_back(a);
        }
    }
    if (numr % 2 == 0 && numg % 2 == 0 && numb % 2 == 0) {
        cout << 0 << endl;
        return;
    }

    // B の個数が偶数となるように編集
    if (numr % 2 == 0) {
        swap(numr, numb);
        swap(R, B);
    }
    if (numg % 2 == 0) {
        swap(numg, numb);
        swap(G, B);
    }

    sort(all(R));
    sort(all(G));

    auto closest = [](vll& v, ll x) -> ll {
        ll ans = INF;
        auto it = lower_bound(all(v), x);
        if (it != v.end())
            chmin(ans, abs(x - *it));
        if (it != v.begin()) {
            chmin(ans, abs(x - *prev(it)));
        }
        return ans;
    };

    ll ans = INF;
    // R, G 間で 1 pair 作ったときの最小値
    for (ll x : R) {
        chmin(ans, closest(G, x));
    }
    if ((int)B.size() == 0) {
        cout << ans << endl;
        return;
    }

    // (R, B), (G, B) で 2  pair 作ったときの最小値
    int m = B.size();
    vll r(m), g(m);
    rep(i, m) {
        ll x = B[i];
        r[i] = closest(R, x);
        g[i] = closest(G, x);
    }

    // dp[i][state]: 青を i 番目まで見て、
    // state=1 赤とペアを組む青が決まっている
    // state=2 緑とペアを組む青が決まっている
    // state=3 赤と緑とペアを組む青が決まっている
    vvll dp(m, vll(4, INF));
    dp[0][1] = r[0];
    dp[0][2] = g[0];
    rep2(i, 1, m) {
        // i 番目の青を赤とペアを組ませる
        dp[i][1] = min(dp[i - 1][1], r[i]);

        // i 番目の青を緑とペアを組ませる
        dp[i][2] = min(dp[i - 1][2], g[i]);

        // "青緑のペアが決まっている状態で i 番目の青を赤とペアを組ませる"
        // または
        // "青赤のペアが決まっている状態で i 番目の青を赤とペアを組ませる"
        dp[i][3] = min(r[i] + dp[i - 1][2], g[i] + dp[i - 1][1]);
        chmin(dp[i][3], dp[i - 1][3]);
    }
    chmin(ans, dp[m - 1][3]);
    cout << ans << endl;
}

解説に書いてあったやり方

(2) のとき、青と赤の組の不満が最小になるものと、青と緑の不満が最小になる組を調べればよい。このとき、青と赤の組で使われた青が、青と緑の組でも使われるかもしれないが、その組み合わせが最小になるときは (1) のときの不満より小さくなることはない。例えば、$R_i = B_j$, $G_k = B_j+1$ のときは結局不満は(1), (2) のどちらでも 1 だし、$B_j-1=R_i = B_j = G_k = B_j+1$ のときの不満度は(1), (2) のどちらでも 2 である。

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    N *= 2;
    vector<pair<ll, char>> ps;
    rep(i, N) {
        ll a;
        char c;
        cin >> a >> c;
        ps.emplace_back(a, c);
    }

    int numr = 0, numg = 0, numb = 0;
    vll R, G, B;
    for (auto [a, c] : ps) {
        if (c == 'R') {
            numr++;
            R.push_back(a);
        }
        if (c == 'G') {
            numg++;
            G.push_back(a);
        }
        if (c == 'B') {
            numb++;
            B.push_back(a);
        }
    }
    if (numr % 2 == 0 && numg % 2 == 0 && numb % 2 == 0) {
        cout << 0 << endl;
        return;
    }

    // B の個数が偶数となるように swap
    if (numr % 2 == 0) {
        swap(numr, numb);
        swap(R, B);
    }
    if (numg % 2 == 0) {
        swap(numg, numb);
        swap(G, B);
    }

    sort(all(R));
    sort(all(G));

    auto closest = [](vll& v, ll x) -> ll {
        ll ans = INF;
        auto it = lower_bound(all(v), x);
        if (it != v.end())
            chmin(ans, abs(x - *it));
        if (it != v.begin()) {
            chmin(ans, abs(x - *prev(it)));
        }
        return ans;
    };

    ll ans = INF;
    // R, G 間で 1 pair 作ったときの最小値
    for (ll x : R) {
        chmin(ans, closest(G, x));
    }

    // (R, B), (G, B) で 2  pair 作ったときの最小値
    int m = B.size();
    ll rmin = INF, gmin = INF;
    rep(i, m) {
        ll x = B[i];
        chmin(rmin, closest(R, x));
        chmin(gmin, closest(G, x));
    }
    chmin(ans, rmin + gmin);

    cout << ans << endl;
}