Codeforces Round #579 (Div. 3) F1. Complete the Projects (easy version)

お題箱より。

問題概要

Polycarpは初期評価 $r$ のフリーランスである。

依頼が $n$ 個ある。 $i$ 番目の依頼は受諾時点で $a_{i}$ 以上の評価が必要であり、完了後に評価が $b_{i}$ 変化する（これは負であることもあり得る）。依頼の順序は好きに選んで良いが、依頼を複数同時に持つことはできない。

全ての依頼を完了し、かつ完了時点での評価が非負であるような依頼の処理順序が存在するかどうか判定せよ。

制約

$1 \le n \le 300$
$1 \le r \le 30000$
$1 \le a_{i} \le 30000$
$-300 \le b_{i} \le 300$

解法

まずは $b_{i} \ge 0$ であるような依頼を処理します。このときの順序は気にする必要がなく、できるようになったものから処理して良いです。ここで $b_{i} \ge 0$ の依頼を全て処理できなかった場合、答えは NO です。

この後は $b_{i} \lt 0$ の依頼を処理します。ここでの順序には気を配る必要があります。どのように依頼をこなしていくのが最適でしょうか？

簡単のため、まずは $a_{i}$ または $b_{i}$ のいずれかが同じようなケースを考えてみます。もし $a_{i}$ が同じならば、依頼を完了して評価が下がるほど次の依頼が受けにくくなるので、完了後の評価減少が少ない（ $b_{i}$ が数として大きい）ほうからこなしていくべきです。逆に $b_{i}$ が同じならば、受諾条件が厳しい、つまり $a_{i}$ が大きいものからこなしていくべきです。

ここからなんとなく、 $a_{i}$ が大きいものや $b_{i}$ が大きいものを先にこなしたほうが良さそうな気がしてきます。では $a_{i}$ と $b_{i}$ のどちらも異なる場合どのようにするべきかと言うと、なんと $a_{i} + b_{i}$ が大きいほうを先に処理するのが常に最適になります。

これは考え方のテクニックとして、証明手順と一緒に覚えてしまったほうが良いです。証明していきましょう。

証明

まずは依頼が $(a_{i}, b_{i}), (a_{j}, b_{j})$ の2つだけだとして、どっちを先に処理したほうが得なのかを具体的に計算します。今回の問題における「得」とは何なのか…という点ですが、両方の依頼をこなせるかどうかが重要なので、「得」とは両方の依頼を完了できるための条件が緩いことです。この条件は、具体的には依頼を受ける前の評価値が○○以上である、というものになります。

$b_{i}$ が負であるせいで数式の大小が若干分かりにくくなるので、 $|b_{i}|$ を使うことにしましょう。依頼を受ける前の評価値を $r$ とします。依頼を $i \to j$ とこなしたときの評価値の推移と受諾できる条件は、

依頼 $i$ を受ける。その受諾条件は $r \ge a_{i}$ であり、完了後に評価は $r-|b_{i}|$ となる。
依頼 $j$ を受ける。その受諾条件は $r-|b_{i}| \ge a_{j}$ であり、完了後に評価は $r - |b_{i}| - |b_{j}|$ となる。

という流れになるため、この依頼をともに完了できる条件は $r \ge \max(a_{i}, a_{j} + |b_{i}|)$ となります。

もし依頼を $j \to i$ とこなした場合、同様に考えて条件は $r \ge \max(a_{j}, a_{i} + |b_{j}|)$ となります。

$R_{1} = \max(a_{i}, a_{j} + |b_{i}|), R_{2} = \max(a_{j}, a_{i} + |b_{j}|)$ として、この値が小さいほど「緩い」条件になります。それぞれの $\max$ の中身のうちどっちが大きいかで場合分けします。

$a_{i} \gt a_{j} + |b_{i}|$ のとき

$R_{1}$ の $\max$ の中身について見ています。このときは $R_{1} = a_{i}$ となり、さらに $R_{2} = a_{i} + |b_{j}|$ となります。このことから $R_{1} \lt R_{2}$ であり、依頼 $i$ を先にやるべきです。

$a_{j} \gt a_{i} + |b_{j}|$ のとき

次は $R_{2}$ の $\max$ の中身について。この場合は逆に $R_{1} \gt R_{2}$ になり、依頼 $j$ を先にやるべきです。

上2つでない場合

このときは $R_{1} = a_{j} + |b_{i}|, R_{2} = a_{i} + |b_{j}|$ となります。このとき $R_{1} \le R_{2}$ となる条件は、移項して

（★） $a_{i} - |b_{i}| \ge a_{j} - |b_{j}|$

という条件になります。これが依頼 $i$ を先にやるべき条件であり、冒頭に書いた「 $a_{i} + b_{i}$ が大きいほうを先に」という条件がここで出てきます。

このように3つの場合分けをしてきましたが、実際には $a_{i} - |b_{i}| \ge a_{j} - |b_{j}|$ の式だけで判定をすることができます。なぜなら、

$a_{i} \gt a_{j} + |b_{i}|$ のときは、★の不等式は必ず真となり、結果として「依頼 $i$ を先にやるべき」と判定される。
$a_{j} \gt a_{i} + |b_{j}|$ のときは、★の不等式は必ず偽となり、結果として「依頼 $j$ を先にやるべき」と判定される。

と、★の不等式を使って判定すると全てのケースについて正しい結果になるからです。

証明の続き

これで依頼が2つだけの時は証明できたので、一般のケースについて考えます。これは「先ほどのソート順を破っているような並べ方は、隣り合ってソート順に違反している2要素を交換することで必ず良く（条件を緩く）できるので、最適解になり得ない」というロジックを使います。バブルソートのように違反箇所を交換していって、結果としてソートされた状態が一番いい状態だ…というロジックです。

厳密には以下の点を全てチェックして証明完了となります。