事前知識

この問題では、ビット列で表現された集合について扱います。以下の記事のうち基本的な内容を理解することが、この問題の解説の理解の助けになるかもしれません。

• APG4b-AC 3.05.ビット演算
• ビット列による部分集合表現 【ビット演算テクニック Advent Calendar 2016 1日目】

まず、薬をひとつも混ぜていない状態を状態 \(0\) とし、これを安全な状態として定義しておくと便利です。
つまり、あらかじめ文字列 \(S\) を “0”+\(S\) に変更しておくと、 (多くの言語では文字列の始まりが \(0\) 文字目であるという点からも) 後の実装が楽です。

この問題で要求されていることは、状態 \(0\) から薬品を \(1\) 種類ずつ追加して状態 \(2^N-1\) に到達できるか判定することです。

当然ながら状態 \(0\) には到達可能であり、あとは各状態から次に到達できる状態がどのようなものかを調べていけば良いです。

ある状態 \(x\) から次に到達できる状態を調べる方法は次の通りです。

• 状態 \(x\) に到達できない場合は、状態 \(x\) から先に進むことを考える必要はない。
• そうでなければ \(k=1,2,\dots,N\) について以下を繰り返す。
  • もし \(x\) の下から \(k\) ビット目が立っていなければ薬品 \(k\) はまだ混ぜられておらず、薬品 \(k\) を加えることで状態 \(y=x+2^{k-1}\) となる。
  • この状態 \(y\) が安全であれば、状態 \(y\) に到達できることが分かる。

以上の判定を状態の番号の昇順に行い、各状態に到達できるかどうかを求めていけば良いです。

時間計算量はケース当たり \(O(2^N N)\) です。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int t;
  cin >> t;
  while(t>0){
    t--;
    int n;
    cin >> n;
    string s;
    cin >> s;
    s="0"+s;
    vector<int> ok(1<<n,0);
    ok[0]=1;
    for(int i=0;i<(1<<n);i++){
      if(ok[i]==0){continue;}
      for(int j=0;j<n;j++){
        if(i&(1<<j)){continue;}
        int next=(i|(1<<j));
        if(s[next]=='0'){ ok[next]=1; }
      }
    }
    if(ok[(1<<n)-1]){cout << "Yes\n";}
    else{cout << "No\n";}
  }
  return 0;
}