解説:#17 麻布株式会社

# 解説 目的は売る物件を最小にして、$K$億円の資金を回収することと考えると、例えば"「10億円の物件を売れば条件に達する」ならば「100億円の物件を売れば条件に達する」"と考えることができます。 ここから、売る物件を最小にするには、高い物件から順に売却し、$K$億円に達した時点で終わりにすればいいと考えることができます。 あとは、物件の価値を高い順にソートすればよいです。 余談ですが、この問題のテストケースは全てコーナーケースのつもりでおいています。思った以上にWAが出てましたので、全てのケースの問題・設置意図・回答を載せます。 ## テストケース集 ### case01 ``` 3 2 1 1 2 ``` - Ans: `1` - ソートしていない or 小さい順にソートしてしまっていないか ### case02 ``` 3 2 3 1 1 ``` - Ans: `1` - 問題趣旨を勘違いして、売る物件の総額の最小値を求めようとしていないか ### case03 ``` 3 3 1 1 1 ``` - Ans: `1` - forやソートを全ての配列に対してちゃんと実行できているか - 境界値に対処できているか ### case04 - $n\ =\ 10^5, k\ =\ 10^{18}$ - $a_i\ = 18^{18}-1\ (1 ≤ i ≤ n)$ - ans: `2` - long long で扱っているか - 過剰に足したりしていないか - 最大ケース ### case05 ``` 3 4 1 1 1 ``` - ans: `-1` - 倒産ケースを入れるのを忘れてただけ ### case06 - $n\ =\ 10^5, k\ =\ 10^{18}$ - $a_i\ = 1\ (1 ≤ i ≤ n)$ - ans: `-1` - long long で扱っているか - 最大ケース(かかる時間が最大のつもり) ### case07 ``` 4 9 7 2 100 1000 ``` - ans: 1 - なんか心配だった(別にチェックすることリストみたいなのを予め書いてからテストケースを作成した訳じゃないので) ## 反省 - 正直オーバーフローに対するチェックをしてなかった - 配列を固定の長さでとったときに事故が起きてないかもチェックしてなかった。 - コンテスト開始30分前に作問を始めたので、正直ランダムケースなんて用意する暇がなかった。 - できるだけ損失をすくなるするように…って問題にするつもりだったけど、20分じゃわからなかった。でも今考えてもわからないからわからない。なんかできそうだけれども。 - 前回のコンテストは麻布動物園ってタイトルだったのに、なぜか「FUSAI」っていうタイトルで出した。FUSAIってなんやねん。