Pの競プロ記

競技プログラミングに関することを書きます。

TopCoder Open 2014 Round 2B easy : SwitchingGame

解法・感想など


本番で解けなかったやつ。

自分の中では分かったつもりですが、うまく文章にできてないのでご了承下さい。


ライトのオンオフがどちらでもよい"?"の処理が重要である。

Twitterでのアドバイスや他の人のコードを参考にしながら、状態数が2つ(ライトのon/off)と3つ(ライトのon/off、どちらにも対応できる)のやり方を試した。

・2状態の場合
各levelで on -> off や off -> on することが確定である場合に便乗して先にライトを切り替えておく的発想。

level n のライトの状態がどちらでもよい場合は、level (n + 1) 以降のライトの状態を見て、ライトのオンオフを切り替えるべきであれば level n の時点でライトを切り替えておく。

・3状態の場合
"?" は on/offどちらにも変化できると考える。
例えば on -> off することが分かっているとき、level n のライトの状態がどちらでもよい場合は"?"としておく。
そうすることで level (n + i) で on/off に切り替えないといけないとき、level n でその状態に切り替えておいたとすればよい。

とある生放送で「どっちにも出来る所を後で都合のいいようにしておく系のgreedy」とコメントしている方がいて、なるほどなと思った。

ソースコード

class SwitchingGame {
public:
  
  int timeToWin(vector <string> states) {
    int ans = 0;
    int n = states.size();
    int m = states[0].size();
    
    string now(m, '-');
    
    // 3 states
    for(int i = 0; i < n; i++) {
      bool on = false;
      bool off = false;

      for(int j = 0; j < m; j++) {
        if(now[j] == '+' && states[i][j] == '-') off = true;
        if(now[j] == '-' && states[i][j] == '+') on = true;
      }

      if(on) {
        ans++;
        for(int j = 0; j < m; j++) {
          if(now[j] == '-' && states[i][j] == '+') now[j] = '+';
          if(now[j] == '-' && states[i][j] == '?') now[j] = '?';
        }
      }
      if(off) {
        ans++;
        for(int j = 0; j < m; j++) {
          if(now[j] == '+' && states[i][j] == '-') now[j] = '-';
          if(now[j] == '+' && states[i][j] == '?') now[j] = '?';
        }
      }
      
      for(int j = 0; j < m; j++) {
        if(now[j] == '?' && states[i][j] != '?') now[j] = states[i][j];
      }

      ans++;
    }

    // // 2 states
    // for(int i = 0; i < n; i++) {
    //   bool on = false;
    //   bool off = false;
      
    //   for(int j = 0; j < m; j++) {
    //     if(now[j] == '-' && states[i][j] == '+') on = true;
    //     if(now[j] == '+' && states[i][j] == '-') off = true;
    //   }
      
    //   if(on) {
    //     ans++;
    //     for(int j = 0; j < m; j++) {
    //       if(now[j] == '-' && states[i][j] == '+') now[j] = '+';
    //       if(now[j] == '-' && states[i][j] == '?') {
    //         int k = i;
    //         while(k < n && states[k][j] == '?') k++;
    //         if(k < n && states[k][j] == '+') now[j] = '+';
    //       }
    //     }
    //   }
      
    //   if(off) {
    //     ans++;
    //     for(int j = 0; j < m; j++) {
    //       if(now[j] == '+' && states[i][j] == '-') now[j] = '-';
    //       if(now[j] == '+' && states[i][j] == '?') {
    //         int k = i;
    //         while(k < n && states[k][j] == '?') k++;
    //         if(k < n && states[k][j] == '-') now[j] = '-';
    //       }
    //     }
    //   }
      
    //   ans++;
    // }
        
    return ans;
  }