けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

JOIG 春合宿 2022 day1-1 Relay (難易度 6)

面白かった!

問題概要

 N 人の走者がいる。 N 人の中から  3 人を選んで、100m 走る × 3 の 300m リレーを行う。

 i 人目の 100m 走のタイムは  A_i 秒、バトンパスタイムは  B_i 秒で与えられる。リレーの走者として、 i, j, k 3 人を選んでこの順に走るときの総合タイムは

 A_{i} + \max(B_{i}, B_{j}) + A_{j} + \max(B_{j}, B_{k}) + A_{k}

で与えられる。この総合タイムの最小値を求めてください。

制約

  •  3 \le N \le 2 \times 10^{5}

考えたこと:走者メンバーを固定して考える

まず一目見て複雑な数式だと思った。経験上こういう時は、少しでも簡単な式に置き換えることを考えるとよい!!

その際の方針として、走者メンバーを固定したときに、 A_{i} + \max(B_{i}, B_{j}) + A_{j} + \max(B_{j}, B_{k}) + A_{k} の値が最大になるような走順を考察しよう。

一般に、最適化問題を解く際には、ある値を固定した場合の問題を先に解くことで、活路を見出せることがとても多い!!

走者メンバーを固定すると、 A_{i} + A_{j} + A_{k} の部分は一定なので、 \max(B_{i}, B_{j}) + \max(B_{j}, B_{k}) の部分だけが問題になる!!

直感的には、二度も絡んでくる真ん中の走者が、バトンパスタイム  B が最小のメンバーを選ぶとよさそうだ。そして実際にその場合が最適になる。このことを確かめてみよう。

メンバー  a, b, c を選んで、 B_{a} \le B_{b} \le B_{c} であるとしよう。

  •  i = a, j = b, k = c のとき: \max(B_{i}, B_{j}) + \max(B_{j}, B_{k}) = B_{b} + B_{c}
  •  i = a, j = c, k = b のとき: \max(B_{i}, B_{j}) + \max(B_{j}, B_{k}) = 2 B_{c}
  •  i = b, j = a, k = c のとき: \max(B_{i}, B_{j}) + \max(B_{j}, B_{k}) = B_{b} + B_{c}
  •  i = b, j = c, k = a のとき: \max(B_{i}, B_{j}) + \max(B_{j}, B_{k}) = 2 B_{c}
  •  i = c, j = a, k = b のとき: \max(B_{i}, B_{j}) + \max(B_{j}, B_{k}) = B_{b} + B_{c}
  •  i = c, j = b, k = a のとき: \max(B_{i}, B_{j}) + \max(B_{j}, B_{k}) = B_{b} + B_{c}

このうち最小のものは  B_{b} + B_{c} である。よって、 B_{a} \le B_{b} \le B_{c} であるような走者  a, b, c をメンバーにしたときには、適宜メンバーを入れ替えることにより、最終スコアは

 A_{a} + A_{b} + A_{c} + B_{b} + B_{c} = A_{a} + (A_{b} + B_{b}) + (A_{c} + B_{c})

になるものと考えて良いことがわかった。

簡単のため、 N 人の走者を、 B が小さい順に並び替えることにしよう!!!

そうして、 B_{0} \le B_{1} \le \dots \le B_{N-1} であるものと考えることにしよう。こうすることで問題が考えやすくなるのだ。

走者  a を固定して考える

 B_{0} \le B_{1} \le \dots \le B_{N-1} という前提のもとでは、 3 人の走者  a, b, c ( a \lt b \lt c) を選ぶと、最終スコアは

 A_{a} + (A_{b} + B_{b}) + (A_{c} + B_{c})

と簡単な式で表せる。これを最適にする方法を考えるにあたって、再び、ある量を固定して考えることにしよう。具体的には、走者  a を固定して考えることにする。

 a を固定すると、残りの問題は次のように考えられる。


番号が  a より大きい走者  i = a+1, a+2, \dots, N-1 のうち、 A_{i} + B_{i} が大きい順に  2 人とればよい


残りの問題の難しいところは、 a の値によって、 A_{i} + B_{i} が大きい順の  2 人が入れ替わってしまうところだ。

ひとまず、次の値を求めることにしよう。

  • vmin1[a] i = a+1, a+2, \dots, N-1 に対する  A_{i} + B_{i} の最小値
  • vmin2[a] i = a+1, a+2, \dots, N-1 に対する  A_{i} + B_{i} 2 番目に小さな値 (最小値が複数ある場合は最大値)

これらは、添字 iN-1 から 0 へと逆順に回していくような for 文によって求めることができる。そしてこれらの値が求められていれば、

A[a] + vmin1[a] + vmin2[a]

の最小値が答えになる。

計算量

  •  B を小さい順に並び替える: O(N \log N)
  • A[a] + vmin1[a] + vmin2[a] の最小値を求める: O(N)

よって全体の計算量は  O(N \log N) となる。

コード例

実装上は、vmin1[a]vmin2[a] は配列として持つのではなく、動的に求めることにした。

#include <bits/stdc++.h>
using namespace std;
const long long INF = 1LL << 55;

int main() {
    // 入力
    int N;
    cin >> N;
    vector<long long> A(N), B(N);
    for (int i = 0; i < N; ++i) cin >> A[i] >> B[i];

    // B が小さい順に添字をソートする
    vector<int> ids(N);
    for (int i = 0; i < N; ++i) ids[i] = i;
    sort(ids.begin(), ids.end(), [&](int i, int j) {
        return B[i] < B[j];
    });

    // A[a] を固定して最適化する
    long long res = INF;
    long long vmin1 = INF;
    long long vmin2 = INF;
    for (int a = N-1; a >= 0; --a) {
        // 答えを更新
        res = min(res, A[ids[a]] + vmin1 + vmin2);

        // best, second を更新する
        long long val = A[ids[a]] + B[ids[a]];
        if (val < vmin1) {
            vmin2 = vmin1;  // ベストをナンバー 2 に譲る
            vmin1 = val;  // ベストを更新する
        } else if (val < vmin2) {
            vmin2 = val;
        }
    }
    cout << res << endl;
}