Paiza一日限定問題でうんち💩したお話
解きながら問題整理するために書いてるやつです見苦しいところもあると思いますが、ご容赦ください。
まず、問題はこれ
↑ログインしないとみられないっぽい
類問をあっとこで見たことある気がするけど覚えてない。
Pが大きいのでPがオーダーに絡まないように解くのがポイントかなぁ
問題の読み替えが重要だよなぁ
O(P^2)なら浮かんだ(は？)
O(NP)が通らないから難しいって話だよねこれ
ん？にぶたんかませばO(PlogN)になるか？
変数名定義
vector<pair<int,int>> single_atack,all_atack //pair<消費魔力,攻撃力>
- 全体攻撃と単体攻撃を魔力iで出せる最大値を求める(1<=i<=P)
- 全体攻撃でj、単体攻撃でP-jの魔力を使ったときの倒せる敵の数を求める(1<=j<=P)
1が例えば単体攻撃、魔力iででる攻撃力の最大値をsingle_damage[i]とすると
single_damage[1]=魔力が1の攻撃のうち攻撃力最大のやつ
single_damage[i]=max(single_atack[i-1], single_atackの各要素prのsingle_damage[i-pr.first]+pr.second)
いや、O(NP)やでこれ
確実にTLEやん
ちなみにTLEは3[sec]です。
わからんから、これで提出する
…
…
え、通った。
実行時間0.01[sec]って書いてあるけど
・1 ≦ N, M ≦ 100
・1 ≦ P ≦ 10,000
・O(NP)
あああああああああああああああああああああああああああああああ！！！！！！！！！！！（ﾌﾞﾘﾌﾞﾘﾌﾞﾘﾌﾞﾘｭﾘｭﾘｭﾘｭﾘｭﾘｭ！！！！！！ﾌﾞﾂﾁﾁﾌﾞﾌﾞﾌﾞﾁﾁﾁﾁﾌﾞﾘﾘｲﾘﾌﾞﾌﾞﾌﾞﾌﾞｩｩｩｩｯｯｯ！！！！！！！）
通るよ！！（怒）
はい、一桁見間違えてて、一桁勘違いして覚えてました。
まぁ、これを教訓にすればいいか（泣）
はぁ
教訓
【以下解法解説】
上記ステップ２について
各jについてまず、敵の体力をall_damage[P-j]ずつ引いて、それが0以下なら死んでる
1以上なら敵を倒すのに必要な魔力をsingle_damageから求める。lower_boundを使って求める。はじめてにぶたんSTL使ったから勉強になった。
てかこれオーダーO(NPlogN)だよな。関係ないけど。
では、ネタバレ禁止法に基づいて明日の15:00付けで投稿します。てか、今見てる問題のURLが明日404してるかもだしURLだけ張りに来なきゃだな
張りに来た
解説と解法一緒だったなぁ
これもDPの一種なのか
