cafelier@SRM

SRM432 Div1 250

あとで | 19:45 |

新年会につきギリギリ登録間に合わなかったので後でやってみた。

同時に全点灯させられるのは初期パターンが完全に同じところだけ、というのに全く気づかず 2^50 の探索を枝刈りで通す方向に走ったのであった。

class LampsGrid {
public:
  int curMax;

  int mostLit(vector <string> initial, int K) 
  {
    vector<LL> s;
    for(int j=0; j<initial[0].size(); ++j) {
      LL x = 0;
      for(int i=0; i<initial.size(); ++i)
        if( initial[i][j]=='1' )
          x |= (1LL << i);
      s.push_back(x);
    }

    curMax = 0;
    for(; K>=0; K-=2)
      if( K <= initial[0].size() )
        rec((1LL<<initial.size())-1, s, 0, K);
    return curMax;
  }

  void rec(LL lit, vector<LL> s, int i, int K) // exact K flips
  {
    int c = 0;
    for(LL j=1; j<=lit; j<<=1)
      if( lit&j )
        ++c;
    if( c<=curMax )
      return;
    if( i == s.size() ) {
      curMax = c;
      return;
    }

    if( i+K < s.size() ) // noflip
      rec( lit&s[i], s, i+1, K );
    if( K ) // flip
      rec( lit&~s[i], s, i+1, K-1 );
  }
};

• 今までの最高点灯列数(curMax)を覚えといて、下回ったら即再帰打ち切り、みたいなの。
  • flipするのとしないののどちらかはlitの立ってるビット数を半分以下にする
  • だからたぶん log_2(50)<6回 間違った方を選んだら確実に枝刈り対象になる
  • なので多く見積もっても 50C5 くらいの探索空間なはず。どうにかなる。

とかなんとか考えた末のコードでした。ううむ賢さ不足