D - Happy Birthday! 2 Editorial by physics0523
実は、数列 \(B\) (または \(C\) )の候補を \(201\) 通り探索すれば、その中で必ず条件を満たす数列の組を見つけることができます。
\(X+1\) 羽の鳩を \(X\) 個の鳥かごに入れるとき、 \(2\) 羽以上の鳩が入った鳥かごが少なくとも \(1\) つ以上存在する
これは、「鳩ノ巣原理」と呼ばれます。今回の問題では、
\(201\) 個の数列を、含まれる要素の総和を \(200\) で割った余りという \(200\) 個のグループに分けるとき、 \(2\) 個以上の数列を含んだグループが少なくとも \(1\) つ以上存在する
と言い換えられます。
数列の候補は全部で \(2^N-1\) 通りあるので、 \(N \ge 8\) のケースについては、必ず答えが存在することが分かります。
では、どのようにして数列を \(201\) 通り探索すればよいでしょうか。
例えば、数列のうち先頭の \(\min(N,8)\) 要素を取り出して、その中で数列の候補をbit全探索するという方法があります。
\(N \le 8\) の場合は通常の全探索と変わらないので正しく動作します。\(N \ge 9\) の場合でも、 \(8\) 要素の中での数列の候補は \(255\) 通りあるので、答えを \(1\) 組見つけるには十分です。
このbit全探索は、定数時間で動作します。
C++による実装例:
#include<bits/stdc++.h>
using namespace std;
void output(vector<int> &a){
cout << a.size();
for(auto &nx : a){
cout << ' ' << nx;
}
cout << '\n';
}
int main(){
int n;
cin >> n;
vector<int> a(n);
for(auto &nx : a){cin >> nx;}
vector<vector<int>> bk(200,vector<int>(0));
int cnt=min(n,8);
for(int i=1;i<(1<<cnt);i++){
int sig=0;
vector<int> s;
for(int j=0;j<cnt;j++){
if(i&(1<<j)){
s.push_back(j+1);
sig+=a[j];sig%=200;
}
}
if(bk[sig].size()!=0){
cout << "Yes\n";
output(bk[sig]);
output(s);
return 0;
}
else{bk[sig]=s;}
}
cout << "No\n";
return 0;
}
BONUS! \(N=7\) の場合に、答えが
No
となるケースをひとつ構築してください。(折り畳みを開くと答えのうちひとつが表示されます)
例えば、以下のケースで、答えが No
となります。
7
1 2 4 8 16 32 64
posted:
last update: