ferinの競プロ帳

競プロについてのメモ

SRM 608 div1 Easy MysticAndCandies

考えたこと

まず適当に箱を選んだ時その選び方が条件を満たしてるかの判定について考える
選んだ箱のlowの和をlsum、選んでない箱の和をhsumとする
C-lsum-hsumが正ならその分選んだ箱のキャンディーの最低数が増える
max(C-lsum-hsum, 0) + lsum >= X となる選び方なら条件を満たしている
max(C-lsum-hsum, 0) + lsum を最大にすることを考えると、lsumを最大にするかhsumを最小にすればよさそう
選択する箱の個数を決めれば値を決められるので2パターン試して選ぶ箱の数が少ない方を答えとして出力する

罠でも何でもないけどiとj一箇所書き間違えてシステス落とした。

学び

lowについて降順ソートして順番に加算していきはじめてXを越えたところとhighについて昇順ソートして順番に加算していく値C-X以下になったところを比較するだけでいいのでもっと簡単にかける。
O(N^2)で書いたけど累積和の要領で書けばO(N)で解ける。