ARMERIA

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

Codeforces Global Round 6 E. Spaceship Solitaire

Problem - E - Codeforces

問題概要

ゲームにおいて  n 種類の資源があり、 i=1, ..., n について資源  i a_{i} 個以上所持するとクリアとなる。

プレイヤーは1ターンごとに1個好きな資源を得ることができる。さらに、以下のような形式で表されるボーナスイベントがいくつか存在する。

  • ボーナスイベント  (s, t, u):資源  s の所持数が  t 個になった瞬間に、資源  u を1個獲得する。

ある  (s, t) のペアに対し、2つ以上のボーナスイベントが存在することはない。また全てのボーナスイベント  (s, t, u) について  0 \lt t \lt a_{s} を満たす。

はじめはボーナスイベントが存在しない。以下の形式で  q 個のクエリが入力される。

  • クエリ  (s, t, u) (s, t) のペアに対するボーナスイベントが既に存在している場合、まずそれを削除する。その後、 u \gt 0 ならばボーナスイベント  (s, t, u) を追加する。

各クエリの適用後において、ゲームをクリアするまでの最小ターン数をそれぞれ答えよ。

制約

  •  1 \le n \le 2\times 10^{5}
  •  1 \le a_{i} \le 10^{9}
  •  1 \le q \le 10^{5}

解法

資源間の依存関係などがややこしそうに見えますが、実はシンプルです。

ボーナスで資源  i を獲得できる個数が  a_{i} を超えない限り、全てのボーナスを無駄なく回収する手順が存在します。つまりクエリの  (s, t) はボーナスの削除判定だけに使い、各資源を得られるボーナスの個数  b_{i} を管理していれば、答えは  \sum_{i} \max(0, a_{i} - b_{i}) として求めることができます。

この事実が成り立つためには、

ある  (s, t) のペアに対し、2つ以上のボーナスイベントが存在することはない。また全てのボーナスイベント  (s, t, u) について  0 \lt t \lt a_{s} を満たす。

という制約が効いています。証明してみましょう。

まず必要数を超えるようなボーナスは適当に無視します。またボーナスイベントは「即座に素材を獲得する」ではなく、「いつでも素材を獲得する権利を得る」と考えたほうが説明しやすいです。

以下のように各資源ごとの必要数をブロックで図示し、資源を獲得することをブロックを上から取っていくことに喩えます。「ボーナスで得られるぶん」のブロックを下から順番に赤で塗ります。また取ることでボーナスイベントが発生するブロックを記載します。

f:id:betrue12:20191219230031p:plain

このとき重要な性質として、制約より「同じブロックに2つ以上のボーナスイベントは存在しない」「各資源の一番下のブロックにはボーナスイベントが存在しない」ことが保証されます。

つまり場に未獲得の赤ブロックが1個以上存在しているならば、そのうちボーナスイベントが存在しないブロックも必ず1個以上存在します。その個数を  k とすると、少なくとも  k 個のボーナスポイントが、白ブロックに存在している(または、既に権利として持っている)ということになります。

そのため、まずはボーナスで得られない白ブロックをターンを消費して全て取ります。その時点で赤ブロックが存在しているならば、少なくとも1個以上の素材獲得権利が得られていることになります。その権利を全て使って赤ブロックを取った後は、やはり赤ブロックが残っている限り素材獲得権利を得られています。このようにして全てのブロックを取り終わるまで素材獲得権利が尽きることはないので、白ブロックを取った使ったターン数だけで必ずゲームクリアできます。

ACコード

Submission #67097482 - Codeforces