ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

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

お題箱より。

Problem - F1 - Codeforces

問題概要

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 とこなしたときの評価値の推移と受諾できる条件は、

  1. 依頼  i を受ける。その受諾条件は  r \ge a_{i} であり、完了後に評価は  r-|b_{i}| となる。
  2. 依頼  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要素を交換することで必ず良く(条件を緩く)できるので、最適解になり得ない」というロジックを使います。バブルソートのように違反箇所を交換していって、結果としてソートされた状態が一番いい状態だ…というロジックです。

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

  • 隣り合う2要素の交換は、「それらの2依頼を受ける直前の評価」以外の条件に影響を与えないこと。
  • 違反箇所の交換する操作が有限回で終わること。
  •  a_{i} + b_{i} が同じ要素はどのように並んでいても条件に影響しないこと。

最後に

これを思いつくポイントですが…要素を順番に処理していく際に何らかのソート条件でソートすると最適な順序になるという問題では、

  1.  a_{i} が同じだとすると、 b_{i} をどうなっている順に取っていくのが良いか」あるいはその逆を考えてみる
  2. 隣り合う2要素を並び替えたときに得する/損する条件を考える

というのが糸口になり得ます。ただ今回の問題では場合分けが入ってストレートに不等式が出てこないので少し難しいですね。

2の考察をした時に直接不等式が出てきて、それがソート条件としてそのまま使えるような問題もあります。例えばこの回のC問題などはそうですね。

ACコード

Submission #58737114 - Codeforces