Codeforces Round #608 (Div. 2) - D. Portals - Senの競技プログラミング備忘録

概要

城がNつある。あなたははじめ、K人の戦士を従えて、これを攻略していく。
城には戦力a_i, 補充兵士b_i, 戦略的価値c_iがそれぞれある。城を攻略するには、現在の従えてる戦士がa_i以上である必要がある。城の攻略に成功すると、戦士の数を減ることはなく、さらにb_iだけ補充される。また、それぞれの城iにいる時点で、1人の戦士を城iの守りにつかせることができる。この時、スコアがc_iだけ上がる。
もし、城を攻略できなかったら、その時点でゲームオーバーである。

また、ポータルが計m個あり、普通それぞれの城iでは城iを守らせることしかできないが、ポータルで城u->城v(v < u)が行き来可能ならば、城vも守らせることができる。

あなたは城を1, 2, 3, ...の順番で攻略しないといけない。
あなたはこのゲームをクリアしたうえで、スコアを最大化したい。最大化されたスコアを答えよ。クリアできないなら-1を答えよ。

制約：
1 <= n, k <= 5000, 0 <= a_i, b_i, c_i <= 5000, 1 <= m <= 3 * 10^5, すべての戦士の数はたかだか5000が保証されている。

ACするまで

1. 制約が5000だから二乗しても間に合いそう。
2. DPっぽいなぁ。dp[i][j] := 城i攻略済みでj人を守らせてる時のスコアの最大値　でやってみる。
3. でもポータルが存在してるからどこを守らせてるのかをメモするのは意外に面倒である。
4. 価値が大きい順に守らせればよくね？でもなぁ・・・（ここでコンテスト終了）

5. 条件をよく整理すると、u -> vにポータルがある＝uの時点で2種類の城を守れると同義。vを始めて通りかかったときに守らせなくてよい。
6. ひとまずそれぞれの城の時点で、出せる最大の余裕の戦士数を求める。あとは例えば城iに守らせるのなら、城i+1から最後までに戦士一人離脱と同じなので余裕の戦士数を引く。
7. うんと、どんな順番で出せばいいんだろう。ひとまず戦略的価値が大きい順に選べるだけ選んでみるか。
8. 証明してみるとそれが正解だとわかる。->AC!

考察

貪欲でやりましたがたぶんDPでもできます。

このような複雑な問題では、考えを整理しながら解かないといけない。
ポータルがないならば、それぞれの城を通り過ぎたら守らせることができない。これを次のように言い換える。

何も守らせない場合の戦士数から必要戦力を城ごとに算出して、「あと何人抜けてもこの城を攻略できる」(これをX[i]とでもする)を求める。そして、城iで抜けたのならば、城i + 1以降のすべての城で戦士数が1減るので、X[i +1]以降のすべてのXの値を1ずつ減らす。
ちなみに、X[i + 1]以降の城のいずれかでXが0になってる城があるのなら(つまりもう戦力は分散できない)は、守らせることができないことである。

これで、複雑な要素などを簡単にモデリングできた。いい感じに守らせる城を選んで、スコアを最大化する。

この際、ポータルを考えに入れてみる。ポータルはu->vならば、

城uは城uにいるときにしか守れないが、城vは城vとuの両方にいるとき守れる。
とわかる。このゲームでは戦力はできるだけ多く保持したほうがいいので、城vを守らせるなら城uに到達してから守らせた方がいい。よって、実質的に城vは城uと同じ場所に立ってると考えてよい。こう考えればさきほどのモデリングしたものに簡単に落とし込める。

さて、肝心の選択アルゴリズムであるが、ひとまず思いつくのがc_iが大きい順に選ぶことである。これが正しいとして証明してみる。

c_i > c_jの城iと城jがあるとする。ここで、城jを先に選び、城iを後にすると、それを逆にした時に比べてスコアを損することがあることを示せればよい。

iとjのうち、前にある方をa、後ろにある方をbとする。
aを先に選ぶと、bが選べなくなるのは、aを選んだ時にX[b + 1, n]に0があるときである。この時aの場所にある城のスコアしか得られない。
bを先に選ぶと、aが選べなくなるのは、bを選んだ時にX[b + 1, n]に0があるときである。この時bの城のスコアしか得られない。
どちらも最悪を考えると、先に選んだ一方のスコアしか手に入らない場合である。この時、適切な行動はスコアが大きい城iを先に選ぶことである。
a==bの時も、実は同じことになる。

これから、安直すぎるとも思える貪欲な解法は正解であるとわかる。

Submission #67016172 - Codeforces