No Caffeine, No Life

プログラミング(主にPython)

ABC 056 D:No Need

問題:

D: No Need - AtCoder Beginner Contest 056 | AtCoder

解説:

ちょっと考えにくいと思う。Atcoderの解説では動的計画法を提案していたけれど、下記はもっとシンプルに考えている。

よい集合の中から「不要な数」を見つけるには、実際にそういう「よい集合」を作ってみたらよい。

与えられた数列{\displaystyle a }を昇順にソートする(それを改めて{\displaystyle a }としよう)。この時、大きい要素から足していき、{\displaystyle K }を超えるまで何個必要かカウントする。ここで得られた数列の部分集合({\displaystyle B = (b_{i}, b_{i+1} \ \dots b_{n} }と呼ぼう)に対し、残りの要素はあってもなくてもよい「不要な数」である。なぜなら、{\displaystyle B }の和がすでに{\displaystyle K }以上であるため、{\displaystyle a }の他の要素があってもなくても{\displaystyle K }以上を満たすので。

 また、{\displaystyle K }以上の要素に対しては考慮しなくてよい。なぜなら、そのカード1枚からなる部分集合(これは「よい集合」)に対し、それを除いてしまえば空集合となり、「よい集合」ではなくなってしまうから。

解答例: