No Need

よい集合全体を列挙することは到底できないから，その必要がない形に言い換えたい． よい集合全体を$G$, 必要なカードの集合を$Need$とする．以下カード$i$を書かれている値$a[i]$と同一視する．

部分点解法(editorial+α)

問題文より：

$$\newcommand\st{\text{ s.t. }} i \notin Need \iff i \in \forall s \in G \text{ s.t. } s \setminus \{i\} \in G$$

である．先の要請から$\forall$を消すために対偶を取ると：

$$i \in Need \iff i \in \exists s \in G \text{ s.t. } s \setminus \{i\} \notin G.$$

ところで$s \in G$とは$\sum s \ge K$のことであった．このようにカードの数に関する形に言い換えてみると：

$$i \in Need \iff i \in \exists s, \sum s \ge K \text{ s.t. } \sum s - i \lt K$$

すなわち$K \le \sum s \lt K + i$かつ$i$を含む集合$s$が存在すれば$i$が必要であることが分かる．

このような集合$s$が存在するか知りたい．「総和が範囲内であるような集合が存在するか」は$dp[v] = ($総和が$v$の集合が存在するか$)$のようなdp配列を更新する過程で求まる．すなわち行うdpは初期値$dp[i] = \text{true}$，状態$O(K)$（$\because K+i$以上は考えなくてよい），遷移$O(N)$（$\because i$枚目以外の任意のカード$j$に対し，dp配列の値がある箇所$dp[v]$について$dp[v+j] \gets \text{true}$とする）となる．これをすべての$i$に対して繰り返すから，計算量は$O(N^2 K)$となって部分点解法が得られる．

このdpができることはeditorialを見るまで気付けなかったのだが，集合（の構成過程）を状態と見れば，総和が等しい状態を纏めて考えることができる，というような考え方でよいのだろうか．

追記(2019/03/09): DPの資料を漁っていたら部分和問題と言うものが載っていた．これは総和がある値であるかの判定問題だが，今回のように範囲内か否かも同様のDPで可能．ちなみに$K$が大きかったら半分全列挙をすれば$O(2^{N/2})$らしい．

満点解法: 二分探索(editorial)

カード$i \le j$について$i$が必要ならば$j$も必要であることを示す：再掲するが，

$$i \in Need \iff i \in \exists s \ \text{ s.t. } K \le \sum s \lt K + i$$

であった．いま$i$が必要とするとこのような$s$が存在するはずである．$s$の候補は(1)$j$を含むか(2)$j$を含まないかに二分される． (1)の場合$\sum s \lt K + i$から$\sum s - j \le \sum s - i \lt K$．よって$K \le \sum s \lt K + j$であるから$j$も必要であることが言える． (2)の場合では$s$から$i$を除いて$j$を加えた集合$t$を考えてみると，$K \le K - i + j \le \sum s - i + j \lt K + j$であるから$t$は$K \le \sum t \lt K+j$を満たす（$\because$ $\sum t = \sum s - i + j$）．従って$j$を必要たらしめる集合$t$が構成できるから$j$も必要．

よって必要である最小のカードを見付ければ，それ以上のカードはすべて必要であり，それ未満のカードはすべて不要となる（対偶）．従って単調性から二分探索が可能． 解答例

嘘解法と別解

数か月前に解こうと思ったときに参照したところ嘘解法（テストケースの不足から提出すればACとなるが，実際には誤りである解法という意味の競プロ用語）だった記事があり，そこから正解法にできないかと考えた記録．

嘘解法の概略：書いてある数字の大きいほうからカードを読んで和$u$を記録する．$u \ge K$になれば$u$を構成する数は必要最小限でよい集合を為すから，それ以外の数はそこまでの過程では不要になる．よってそこの番地$ans$を記録しておけば，最終的に$ans$から右がすべて不要な数と分かる．$u \lt K$であれば$u$にカードの数を加算する．

これはすなわち「その構成要素だけでは良い集合たりえないが，加える$a[i]$によっては良い集合になるような候補」のうち最適，すなわち$K$との差が最も小さいものを$u$が表せているという信念に基づいている．

ところが例えばK=26, a={18,10,9,7}を考える．3番目まで見たとき$u=a[1]=18$であるが，このとき実際に最も$K$に近い候補は集合$V=\{a[2],a[3]\}=\{10,9\}$の総和$19$であって$u$ではない．ここで$a[4]$を採用するとき，元の$u$だと$u+7=25 \lt K$となり$7$は不必要なカードとなってしまう一方，$V$の場合では集合$\{a[2],a[3],a[4]\}=\{10,9,7\}$の総和は$19+7=26=K$となり正しく$7$が必要なカードと判定される．このような理由からこれは誤った解法である．

さて実際に$u$として持っておきたいのは，$K$との差が最も小さい候補であった．反例で見たように逆転が起こるから実際にこれだけを持つことは無理そう．よって先の部分点解にあるdp配列（=すべての候補）を更新することになるが，これでも各$i$に相当する処理が不要なので$O(NK)$で済む． 解答例

解法の正当性を言いたい．以下$w$としたときは$dp[w]=true$である，すなわち$w \lt K$が総和となる数の集合$S _w$が存在するものに限るとする． いま新たにカード$v$を考える．ある$w$に対して$w+v \ge K$となる場合，カードを降順に見ていったことから，$S _{w+v}$（$S _ {w+v}$自体は複数あり得るがそのうち$v$を含むものとする）は「必要最小限なよい集合」，すなわちこれに含まれるどの数字を除いてもよい集合ではなくなる（$\because$ 降順より$\forall i \in S_w$について$v \le i$であり，また$v$の必要性から$K \le \sum S _ {w+v} \lt K + v$であるから，$\sum S _ {w+v} - i \lt K + v - i \le K$．ゆえに集合$S' := S _ {w+v} \setminus \{i\}$は$\sum S' \lt K$であるからよい集合に属さない）．したがって$S _ {w+v}$に含まれるすべてのカードは必要である．一方で$w$が存在しない場合は$v$は（現時点では）不要である．

いま$v$が必要になったとする．$v$の前に不必要と判定されたカード$u$があるとき，$u$は必要となるかを考えたい（満点解法の説明にもあるが現在の記法で再度説明する）．ここで$v$を必要たらしめた$S_ w$を考える．ここに$u$が含まれていれば$S _ w$の最小性から$u$も必要となる．一方でそうでない場合を考えたいが，このとき降順から$\sum S_ {w+u} = \sum S_ w + u \ge \sum S_ w + v \ge K$であり，また$\sum S _ w \lt K$であったから$\sum S _ {w+u} \lt K + u$．これらから$K \le \sum S _ {w+u} \lt K + u$，すなわち$u$についても$S_ w$で必要とできることが分かるから，これはあり得ない．

従って$v$が必要と判明したとき，それまでの全カードが必要であることが分かる．よって$v$が$i$番目のカードのとき$ans \gets i$とし，最終的に$ans$番目より右側のカード，すなわち$n-ans$枚が不要とすればよい．

テストケースを様々な範囲で計5000個ほど生成して先のeditorial解と出力を比較してみたところすべて等しかったので，きっと正しい解法になったはず．