Official

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: