c_Comp-Prog AtC-ABC056-D No Need
黄Diffらしい 昔見た時は手も足も出なかったんだけど今見るとすぐわかる
問題
$ N枚のカードが与えられます。このとき、任意の枚数のカードを集めたときの総和が$ K以上になる場合を良い集合とします。
任意のカードの集合において、あるカードを含むの全ての良い集合において、そのカードを外したときに全ての集合が良い集合であるとき、そのカードを不必要なカードとします。
不必要なカードの総和を求めてください。
考察
不必要なカードである条件は、
$ N枚のカードを全体集合としたときの良い集合の個数 = そのカードを外した$ N-1枚のカードを全体集合とした良い集合の数
となる。(なぜなら良い集合の個数が変わるなら不必要なカードで有るはずの値に依存した良い集合が存在することになるため)
また、ある不必要なカード$ xが存在する時、$ x以下のカードは全て不必要なカードとなる。
証明
数学的帰納法で証明する。
簡単のため、カード列を$ Aとし、ソート済であるとする。
また、$ A^{(n)}は$ n番目のカードを除いたときのカード列を表す。
初めに$ A_xが不必要であるとする。
即ち、$ A_xを除いたカード列$ A^{(x)}において、任意の集合の総和が$ K-A_x以上$ K-1以下にならないとする。
次に $ A_{x-1}について考える。
証明したいこと: $ x-1番目のindexにあるカードを除いたカード列$ A^{(x-1)}において、任意の集合の総和が$ K-A_{x-1}以上$ K-1以下にならない。
以下の順番で証明する
1: $ A_xを使用しない場合
この時、$ A^{(x, x-1)}は、$ A^{(x)}の部分集合であるため、任意の集合の総和が$ K-A_x以上$ K-1以下にならないことがわかる。
また、カード列$ Aはソート済であり、$ A(x-1) \le A(x)となるため、不必要なカードにならないような集合を作成できない。
2: $ A_xを使用する場合
この時、$ A_xは不必要なカードであるため、この状況で$ A_xを使用して良い集合を作成できるとすると、前提が矛盾する。よって不必要なカードにならないような集合を作成できない。
よって、$ A_xが不必要である場合、$ A_{x-1}も不必要であることがわかるため、
数学的帰納法より上記は示された。
よって、降順にソートして、総和が$ K以上になるような値を探す動的計画法をしたあと、後ろから値が同じ要素の個数を見ることで答えがわかる。
なおこの解法だとオーバーフローするので注意。modが一致したときに死にます(今気づきました)。
実装
ちょっと雑に書いたのとオーバーフローするのが治ってないので、後でいい感じに直しておきます
code: solve.cpp
int main(){
int n,k;cin>>n>>k;
vector<long long> A(n);
long long sm = 0;
for(int i = 0; n > i; i++){
}
if(sm < k){
cout << n << endl;
return 0;
}
sort(A.begin(), A.end(), greater<long long>());
for(int i = 0; n > i; i++){
for(int j = 0; k >= j; j++){
}else if(j!=k){
}
}
}
int ans = 0;
for(int i = 1; n >= i; i++){
}
cout << n-ans << endl;
}
振り返り
ギリギリ嘘(ローリングハッシュと同レベルで死ぬ)