面白かった!
問題概要
人の走者がいる。 人の中から 人を選んで、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; }