[大和証券プログラミングコンテスト2022 Spring(ARC138)] D - Differ by K bits

[Q] https://atcoder.jp/contests/arc138/tasks/arc138_d

本番抜けなかった。1時間粘って抜いた。方針はあってた。くやぢーー
1. Kbit立った基底をN個作る。
2. 0から探索。N個の基底とxorして、変更がK桁だけ異なる変更があったら採用
3. 探索が2^N回できたならYes。

Q. Kbit立った基底をどうやって作ろう？
A. 全探索して掃き出し法をするのが安全。

Q. 機械的に1をK個並べて、N回スライドさせるのはダメ？
A. だめ。永遠に3WA食らう。

N=6 K=2 のとき

000011
000110
001100
011000
110000
100001

これは、
100001が基底ではない！！！

100001をぐるぐるxorで追い詰めると、
000011と等しくなってしまう。

Q. 掃き出し法？
A. こういうふうにとるのだ

  // Kbit立っている、N個の基底を探す。
 vector<ll> candE; // Kbit立っている候補
 rep(i, (1<<N)){
   if (__builtin_popcount(i) == K){
     candE.push_back(i);
   }
 }
 
 // 掃き出し法
 vector<ll> E; // 採用する基底
 vector<ll> smallE; // 基底Eの判定に利用
 for(auto e: candE){
   ll tmp = e;
   for(auto ne: smallE){ // 基底の判定は、最小の基底でないといけない
     chmin(tmp, tmp^ne);
   }
   if (tmp > 0){
     E.emplace_back(e);
     smallE.emplace_back(tmp); // 最小の基底
   }
 }

実装

ll N, K;

// BFS? 1<<N 通り作れるか探索
bool solve(vector<ll> &E){
 queue<ll> Q, ans;
 bool seen[(1<<N)]{};
 Q.push(0);
 ans.push(0);
 seen[0] = true;

 while (!Q.empty()){
   ll q = Q.front();
   Q.pop();
   rep(j, N){
     ll nq = q^E[j];
     if (__builtin_popcount(nq^q) == K && seen[nq] == false){
       seen[nq] = true;
       Q.push(nq);
       ans.push(nq);
       break;
     }
   }
 }

 if((ll)ans.size() != (1<<N)){
   return false;
 }
 cout << "Yes" << endl;
 while (!ans.empty()){
   ll a = ans.front();
   ans.pop();
   cout << a << " \n"[ans.empty()];
 }
 return true;
}

int main(){
 cincout();
 
 cin >> N >> K;
 // Kが偶数なら不可能
 if (K%2 == 0){
   cout << "No" << endl;
   return 0;
 }

 // Kbit立っている、N個の基底を探す。
 vector<ll> candE; // Kbit立っている候補
 rep(i, (1<<N)){
   if (__builtin_popcount(i) == K){
     candE.push_back(i);
   }
 }
 
 vector<ll> E; // 採用する基底
 vector<ll> smallE; // 基底Eの判定に利用
 for(auto e: candE){
   ll tmp = e;
   for(auto ne: smallE){ // 基底の判定は、最小の基底でないといけない
     chmin(tmp, tmp^ne);
   }
   if (tmp > 0){
     E.emplace_back(e);
     smallE.emplace_back(tmp); // 最小の基底
   }
 }

 // 基底がN個作れない場合だめ。多分Kが偶数か、K==N>1のときぐらい？
 if (E.size() != N){
   cout << "No" << endl;
   return 0;
 }
 if (solve(E)){
   return 0;
 }
 cout << "No" << endl;
}

https://atcoder.jp/contests/arc138/submissions/30829271