No need

ブログもNo needでしょうが自分のために書いているので許して＞＜

問題
D: No Need - AtCoder Beginner Contest 056 | AtCoder

解答
Submission #1631478 - AtCoder Beginner Contest 056 | AtCoder

この問題、難しかった。
嘘解法ばかり思いついて、自分には少し早すぎたのではないか、と思っています。（自分の忍耐力で何とかAC出来て嬉しい）

解説

まず、kより小さい状態からkより大きくなる、という遷移が起こっている状態を考えます。（ギリギリ集合、と呼ばせていただきます）
この時、制約とかを見るとわかる通り、何を使ったか、という情報は記憶することが不可能なことが分かります。
なので、それを使わない方法を探しました。
→既に使った数も、まだ使っていない数も同じようになる共通の性質を探しました。
ここでギリギリ集合を入れ替えることを考えます。
ギリギリ集合を入れ替えるとき、ギリギリ集合の中のどのような数を抜いてもkより小さくなることが前提となります。
このためには、大きいものから順に選んでいけば、ギリギリ集合を作ることが可能となります。
ギリギリ集合の最も小さい数をメモり、それより大きい数は入れ替えることができるため、必要な数となります。このとき、ギリギリ集合の中にもともと含まれていた数は最小値以上の物だけなので、これが共通点となり、成り立ちます。

まとめると

DPでギリギリ集合を作る（逆順ソートして）
ギリギリ集合の最小値をメモり、更新していく。
それより小さいものは、必要ない数字なので、countしておく。

分かりにくくてすみません（自分のことしか考えていない人の例