TopCoder Statistics - Problem Statement
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

$Y$を$1$，$N$を$0$として見た時，その部分和で表せることができる数の個数を答える．

考え方の方針としてビット列になったので，それを$10$進に直してみた．sample0では

$$ 110\\ 001\\ 111\\ 000 $$

となるので$[0, 1, 6, 7]$の数列の部分和で表すことができる数の個数とすることができる．基本的に部分和が重複することを考えなければ，$2 ^n$通りある．よって，重複する数が分かれば答えが分かる．例えば$7 = 6 + 1$とできるので，これはいらない．$0$は全てを選ばなければ和は$0$なのでこれもいらない．結局いるのは$[1, 6]$のみでこれの部分和で$[0, 1, 6, 7]$を表すことができ，$2 ^2 = 4$が答えとなる．
つまり自分の数を他の数を用いて表せるか，ということが分かれば良いのでいわゆる部分和問題を解ければ良いとなる．しかし，この方針では数が非常に大きいため$dp[i][j]$を取ることが出来ないし，計算量も間に合わない．
この考え方がいけないのかと他の方針もあるか考えてみたがよく分からない．粘りが足りないかもしれないがここでeditorialを見てしまった．基本的に方針は合っていて，自分の数を他の数を用いて表せるか，というのは独立か従属かの問題となる．これはビット列のまま考えてベクトルとして見て，それを並べた行列と見ると，その階数(rank)が答えとなる．
精進したいという気持ちが増した．

Code

#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <map>
#include <set>
#include <queue>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define EPS 1e-8
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int, int> P;

struct Mat {
  int n, m;
  vector<vector<int> > dat;

  Mat(int n, int m) : n(n), m(m), dat(n, vector<int>(m)) {}

  int rank() {
      int r = 0;
      vector<vector<int> > A = dat;
      rep(i, m) {
          int pivot = -1;
          REP(j, r, n) {
              if(A[j][i]) {
                  pivot = j;
                  break;
              }
          }

          if(pivot == -1) continue;
          swap(A[pivot], A[r]);

          REP(j, r + 1, n) {
              if(A[j][i]) {
                  rep(k, m) {
                      A[j][k] ^= A[r][k];
                  }
              }
          }
          r++;
      }

      return r;
  }
};

class LightSwitches {
  public:
  long long countPossibleConfigurations(vector <string> switches) {
      int n = switches.size();
      int m = switches[0].size();
      
      Mat mat(n, m);
      rep(i, n) {
          rep(j, m) {
              mat.dat[i][j] = (switches[i][j] == 'Y');
          }
      }

      int r = mat.rank();
      return (1LL << r);
  }
};

ry0u_ydのblog

SRM306 D1M LightSwitches

TopCoder Statistics - Problem Statement

Code