ABC017 C ハイスコア - 足跡-sokuseki-

自力で満点解法思いついたの嬉しかったのでその記念。

C: ハイスコア - AtCoder Beginner Contest 017 | AtCoder

問題概要

$N$ 個の遺跡があり、遺跡を探索すると宝石と得点が得られる。
$i$ 番目の遺跡を探索したときに、得点 $s_i$ 点を獲得し、 $M$ 種類ある宝石のうち $l_i$ 番目から $r_i$ 番目までの宝石を得られる。
すべての種類の宝石を1つ以上獲得すると魔王が復活してしまうので、魔王が復活しないように遺跡を探索したときの得点の合計の最大値を求める。

制約

$1 \le N \le 10^5$
$1 \le M \le 10^5$
$1 \le l_i \le r_i \le M$
$1 \le s_i \le 5000$

部分点

30点…… $N \le 8$ , $M \le 8$ を満たすテストケース
100点…… $N \le 5000$ , $M \le 5000$ を満たすテストケース
101点……すべてのテストケース

TLE解法

100点解法*1。
魔王が復活しないとき、少なくともどれか1つの宝石は獲得していない。獲得してはいけない宝石を1つ決めると、各遺跡について、その宝石を獲得できるかどうかで、その遺跡で得点を獲得できるかがわかる(最大の得点について考えているので、獲得してはいけない宝石をその遺跡で取ることができないならば、その遺跡を探索して得点を得た方がよい)。
つまり、獲得してはいけない宝石を1つ決めたとき、そのときに取りうる最大の得点は一意に決まる。

獲得してはいけない宝石を順番に試すのに $O(M)$ 。獲得してはいけない宝石を決めた後、各遺跡でその宝石を獲得できるかを調べるのに $O(N)$ かかる。よって、全体の計算量は $O(NM)$ 。

Submission #948966 - AtCoder Beginner Contest 017 | AtCoder

満点解法

(私が解法を考えていたときの脳内をだいぶ忠実に再現してみる)

「すべての宝石を獲得してはいけない」というのが最大の制約なので、獲得してはいけない宝石を一つ定めるという方針はそのままでよさそう。……TLE解法のとおり、獲得してはいけない宝石を決めたときに、その宝石を獲得してしまう遺跡の得点は得られない。……「得られない」ということは、「獲得してはいけない宝石を決めたときに、各遺跡で何点得られないか」というふうに全体からの引き算で考えることができる。もちろん、得られない点数が一番小さくなる宝石を、獲得してはいけない宝石として選べば良い。

試しに、サンプル1を表に書いてみる。

f:id:wk1080id:20170308022800p:plain

はじめに各遺跡について、獲得してはいけない宝石の欄にその遺跡で得られる得点をマイナス表記する。
その後、獲得してはいけない宝石を1つ決めると、その宝石の列さえ見れば最終的な得点が求まることがわかる。
そこまでわかって、いもす法*2を使えばこの表を圧縮して、計算量も落とすことができる！と気付いた。やったね！たえちゃ(ry

いもす法を使うことで、獲得してはいけない宝石を1つ決めると、そのときの最大の得点は $O(1)$ で求まる。
よって計算量は、いもす法の前処理(記録＋シミュレート)に $O(N+M)$ 、各宝石を獲得しない場合について計算するのに $O(M)$ かかるので、全体で $O(max(N,M))$ 。