面白かった！
問題概要
人の走者がいる。
人の中から
人を選んで、100m 走る × 3 の 300m リレーを行う。
人目の 100m 走のタイムは
秒、バトンパスタイムは
秒で与えられる。リレーの走者として、
の
人を選んでこの順に走るときの総合タイムは
で与えられる。この総合タイムの最小値を求めてください。
制約
考えたこと：走者メンバーを固定して考える
まず一目見て複雑な数式だと思った。経験上こういう時は、少しでも簡単な式に置き換えることを考えるとよい！！
その際の方針として、走者メンバーを固定したときに、 の値が最大になるような走順を考察しよう。
一般に、最適化問題を解く際には、ある値を固定した場合の問題を先に解くことで、活路を見出せることがとても多い！！
走者メンバーを固定すると、 の部分は一定なので、
の部分だけが問題になる！！
直感的には、二度も絡んでくる真ん中の走者が、バトンパスタイム が最小のメンバーを選ぶとよさそうだ。そして実際にその場合が最適になる。このことを確かめてみよう。
メンバー を選んで、
であるとしよう。
のとき：
のとき：
のとき：
のとき：
のとき：
のとき：
このうち最小のものは である。よって、
であるような走者
をメンバーにしたときには、適宜メンバーを入れ替えることにより、最終スコアは
になるものと考えて良いことがわかった。
簡単のため、 人の走者を、
が小さい順に並び替えることにしよう！！！
そうして、 であるものと考えることにしよう。こうすることで問題が考えやすくなるのだ。
走者 
を固定して考える
という前提のもとでは、
人の走者
(
) を選ぶと、最終スコアは
と簡単な式で表せる。これを最適にする方法を考えるにあたって、再び、ある量を固定して考えることにしよう。具体的には、走者 を固定して考えることにする。
を固定すると、残りの問題は次のように考えられる。
番号が より大きい走者
のうち、
が大きい順に
人とればよい
残りの問題の難しいところは、 の値によって、
が大きい順の
人が入れ替わってしまうところだ。
ひとまず、次の値を求めることにしよう。
vmin1[a]：に対する
の最小値
vmin2[a]：番目に小さな値 (最小値が複数ある場合は最大値)
これらは、添字 i を N-1 から 0 へと逆順に回していくような for 文によって求めることができる。そしてこれらの値が求められていれば、
A[a] + vmin1[a] + vmin2[a]
の最小値が答えになる。
計算量
を小さい順に並び替える：
A[a] + vmin1[a] + vmin2[a]の最小値を求める：
よって全体の計算量は となる。
コード例
実装上は、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; }
