SRM432 Div2Med LampsGrid

TopCoder SRM

解法
ポイントは以下

  • はじめの状態で同じ配置の行は何度列をフリップしても同じ配置の行のまま
  • 同じ列を2回フリップすると Kが2回分消費できる

よって、各行について '0' の数をカウントし '0' の数が K "以下" で、'0' の数と K との偶奇が一致すればその行が lit であるときが答えとなる。後はその行と同じ行の数を全体の vector からカウントし、最大の数を求めれば良い。

反省・感想
自分では2^50のdfsしか思いつかず、解けなかった。editorial を見て納得した。

2回同じ列をフリップすれば元に戻るのは容易に思いつくれど、わざと2回フリップさせれば、「K回ちょうど」から「K回以下」に帰着できるという考えまでは至らなかった。

#define ALL(x) (x).begin(), (x).end()

class LampsGrid {
public:
  int mostLit(vector <string> initial, int K) {
    
    int res = 0;
    
    for(int i=0; i<initial.size(); i++) {
      int zero = count(ALL(initial[i]), '0');
      
      if(zero % 2 == K % 2 && zero <= K) {
        res = max(res, (int)count(ALL(initial), initial[i]));
      }
    }
    
    return res;
  }
};