Senの競技プログラミング備忘録

こけた問題を自分用の解説で載せる。けんちょんさんのブログを目指したい。質的にも量的にも。こけた問題だけに限定するけど

一つ戻す

いくつかの要素を抜くDP No Needから考える

atcoder.jpこの問題から、次のような一般化された問題を考える。 問題文 N個のものを考える。高速でそのうちの1つを抜いた時の計算結果を求める。

ARC056-D No Need

atcoder.jp 概要 長さN(N 入力されるある整数K(1 ある数Xを含む部分集合のうちのすべての「良い集合」で、X自身を除いても「良い集合」となるとき、Xは「「良い集合」を作るのに不必要」と言います。 さて、「不必要」な要素はいくつあるでしょう?ちなみに…