SRM 566 Div2 Medium PenguinPals

問題

赤と青のペンギンが輪になって並んでいる. 同じ色どうしのペンギンを直線でつなぐ. その時直線同士は交差してはいけない.

可能な限り線を引いた時の最大の線の数を答える問題.

解答

まず,直感的に分かるのは同じ色が隣り合うとき,その2つのペンギンを繋いだ直線は他の直線と交わることはないということ. グリーディーに隣り合う同じ色のペンギンを削除していけば問題のサイズを小さくすることが出来る.

さてそのような削除を行った場合'・・・RBRB・・・'などRとBが交互に出現する文字列になるはず.難しいのはある直線を結ぶと他の直線が結べなくなる場合があるということ.しかし,観察するととても簡単に計算することが出来るということが分かる.Rを結ぶ直線とBを結ぶ直線の内Rを結ぶ直線をまず最大化するような結び方を考えよう.これは一番近いR同士をグリーディーに直線で結ぶことで得られる.(Rの数) / 2の直線が引ける.そのようにグリーディーに直線を引いた場合.直線で結ばれたR同士をRiで表現したとすると・・(Ri-1)B(Ri)B(Ri)B(Ri+1)B(Ri+1) となる.このように結ばれた状態で(Ri-1)B(Ri)と(Ri)B(Ri+1)で囲まれたB同士も結ぶことが出来る.とすると(Ri)B(Ri)を除外すると(Rを除外し)Bも隣り合うB同士をグリーディーにつなぐことが出来る. よって'・・・RBRB・・・'の数をnとするとR同士を結ぶ直線は(n+1)/4と,B同士を結ぶ直線の数(n/2 - 1) / 2となる.

アルゴリズム自体はすぐに思いついたが,実装面で色々ミスした. 新しい配列と置き換えた配列,いつ切り替わるか. ループ(処理)が終わった時その配列達はどういう状態にあるのか気をつける必用がある.

class PenguinPals
{
public:
  int n;
  int findMaximumMatching(string colors)
    {
      n = colors.size();
      int i;
      vector<bool> cols(n, false);
      vector<bool> cols2;
      for(i = 0; i < n; i++)
        if (colors[i] == 'R') cols[i] = true;
        else cols[i] = false;

      bool replace = true;
      int res = 0;
      vector<bool> new_col = cols;
      while (replace && new_col.size() > 1){
        cols = new_col;
        new_col.clear();
        n = cols.size();
        for (i = 0; i < n; i++){
          if (cols[i]) cout << "R";
          else cout << "B";
        }
        cout << endl;
        replace = false;
        n = cols.size();
        if (cols[0] == cols[n-1]){
          new_col = vector<bool>(cols.begin() + 1, cols.end() - 1);
          replace = true;
          res++;
        }else{
          for (i = 0; i < n-1; i++){
            if (cols[i] == cols[i+1]){
              new_col = vector<bool>(cols.begin(), cols.begin()+i);
              new_col.insert(new_col.end(), cols.begin()+i+2, cols.end());
              replace = true;
              res++;
              break;
            }
          }
        }
        // cols.clear();
      }
      if (cols != new_col && new_col.size() > 0) cols = new_col;
      n = cols.size();

      for (i = 0; i < n; i++){
        if (cols[i]) cout << "R";
        else cout << "B";
      }
      cout << endl;
      cout << "n=" << n << endl;

      cout << "res:" << res << endl;
      return res + (n+1)/4 + (n/2 -1 ) / 2;

    }
};