abc056 D - No Need (400点)
久しぶりに自力で黄 diff を AC 出来たので嬉しい
解説
カード $ iが必要$ \Leftrightarrowカード$ iを除いたカードの集合で$ K - A_i以上$ K - 1以下の数が作れる部分集合が存在する
が一番重要な考察。これはカード$ iが不必要の条件の対偶を取ると分かる。
この考察から、dp[i][j] = 1 番目から i 番目までで、和が j になるようにカードを選べるか、dp2[i][j] = i 番目から N 番目までで、和が j になるようにカードを選べるかという 2 つの dp テーブルを持っておくといいことが分かる。これはどちらも $ O(NK)で構築出来る。
後は、全てのカード$ iについて、dp[i - 1][j]とdp2[i + 1][j]を見て、上の条件を満たせるかを確かめればよい。これはセグ木を使うと$ O(NK \log K)で出来る。他にも方法はありそう。