babcs2035 https://blog.hatena.ne.jp/babcs2035/ きろく https://babcs2035.hateblo.jp/ 競技プログラミング AtCoder 400 点問題 問題 解法 解答 問題 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… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fbabcs2035.hateblo.jp%2Fentry%2F2019%2F01%2F13%2F231611" title="KEYENCE Programming Contest 2019 / キーエンス プログラミング コンテスト 2019：C - Exam and Wizard - きろく" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/b/babcs2035/20190113/20190113231604.png Hatena Blog https://hatena.blog 2019-01-13 23:16:11 rich https://babcs2035.hateblo.jp/entry/2019/01/13/231611 1.0 100%