D - Happy Birthday! 2

・問題URL

https://atcoder.jp/contests/abc200/tasks/abc200_d

・思考

・Aは200で割った余りにしといてよさそう(あんま意味ない)
・Aからいくつかとってできたある数列201種類を持ってくるとその中に200で割った余りが等しいものが存在する
・Nがでかいときも、Aのうち初めの数個全探索すればいいのでは

・キーワード

・鳩ノ巣の原理
・bit全探索

・解法

・N≤8の場合、2⁸=256だから、Aの各要素をB(あるいはC)に入れる/入れないの2⁸通りbit全探索を二重ループにして条件を満たすものを探しても間に合う。B,Cが空の場合とB=Cの場合continue。
・N>8の場合、N=1~8までで数列は2⁸-1=255個出来るから、鳩ノ巣の原理よりこの中で総和を200で割った余りが等しいものが必ず一組は存在する(つまり必ずYES)。よってN=8としてN≤8の時と同じことをすればよい。

・コード

int main() {

   int N;
   cin >> N;
   vector<ll>A(N);
   rep(i, N)cin >> A[i];

   if (N > 8) N = 8;

   bool Q = false;
   for (int bit1 = 0; bit1 < (1 << N); bit1++) {
       for (int bit2 = 0; bit2 < (1 << N); bit2++) {

           vector<int>B, C;
           ll b = 0, c = 0;

           for (int i = 0; i < N; i++) {
               if (bit1 & (1 << i)) {
                   B.push_back(i);
                   b += A[i];
               }
           }
           for (int i = 0; i < N; i++) {
               if (bit2 & (1 << i)) {
                   C.push_back(i);
                   c += A[i];
               }
           }

           if (B.size() == 0 || C.size() == 0)continue;
           if (B == C)continue;
           
           if (b % 200 == c % 200) {
               cout << "Yes" << endl;
               cout << B.size() << " ";
               for (auto v : B)cout << v + 1 << " ";
               cout << endl;
               cout << C.size() << " ";
               for (auto v : C)cout << v + 1 << " ";
               cout << endl;
               Q = true;
               break;
           }
           
       }

       if (Q)break;
   }

   if (!Q)cout << "No" << endl;
   
}