水色プログラミング

競プロで解いた問題の記録,ゲーム制作の進捗など...

KEYENCE Programming Contest 2019 / キーエンス プログラミング コンテスト 2019:C - Exam and Wizard

問題

atcoder.jp

解法

まず,A_i < B_i の状況であるものは必ず A_i を B_i まで上げる必要があるのでこれらは答えの個数に加わる.

上げる必要がある準備度の総和を sum とし,準備度が十分であるものの余剰分(B_i - A_i)を降順ソートしたものを D とすると,

D_1 + D_2 + ... + D_k >= sum

となる最小の k を知れればよいとなる.この k を 1 ~ N について確かめていき求めればよい.答えは (必ず準備度を上げなければいけない試験の数) + k になる.O(NlogN).

解答

atcoder.jp

一発 AC 出来たのでよかった.比較的簡単目な 400 点問題だと感じた.

f:id:babcs2035:20190113231604p:plain