きままにものづくり

日々の気付いたことなんかを書いてます。

SRM608Div1Easy

問題

N個のキャンディが入った箱が与えられる。箱の中のキャンディの合計はC個である。箱の中のキャンディの数は正確には分からず、lowからhighの間という情報だけが与えられる。X個のキャンディを必ずとるのに必要な箱の数の最小値を求めよ。

解法

X個を集める方法としては、以下の2つがある。

  • lowがX個を超える。
  • 選択しないhighの総和がC-X個を下回る。

一つ目は、箱の中には少なくともlow以上のキャンディが入っているので、必ずlow以上のキャンディが手に入る。
二つ目は、選択しない箱に注目する。選択した箱のキャンディの合計がX以下になるためには、選択していない箱の方ではC-X以上のキャンディが存在しないといけない。選択していな箱のキャンディの合計の最大値は、選択していない箱のhighの総和である。この値がC-Xを下回ると、選択した箱にはX個以上のキャンディが存在することになる。

計算量

ソート:  O(N log N)
探索:  O(N)

コード