読者です 読者をやめる 読者になる 読者になる

足跡-sokuseki-

りかの日進月歩の記録

ABC017 C ハイスコア

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

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))



Submission #1150134 - AtCoder Beginner Contest 017 | AtCoder

ソースコードでは、さっきの表と違い、各遺跡で取ることができない点数を負数ではなく正数で計算している(ので最後に総得点から引き算している)。あと、宝石のindexに注意する。

感想


得点が0点の状態から考えて何点獲得できるか、ではなく、得点がMAXのときから考えて何点獲得できないか、に思考をシフトさせるのが面白かった。
例示は理解の試金石*3だ!!!!と再確認させられた。サンプル試すの大事。


↑悲しい……






あと、いもす法は好きです(なら間違えるな

*1:30点解法は考えてないので知らない。たぶんすべての遺跡について、探索するかしないかを全探するんじゃないかな。……と思ったけど、制約が8だしnext_permutationを使ってシミュレートするのか。

*2:いもす法知らない人はこちらを参照してください->いもす法 - いもす研 (imos laboratory)

*3:数学ガールの主人公「僕」がよく言う台詞