naoya_t@topcoder

SRM441 Div1 Easy: PerfectPermutation

過去問, 練習 | 19:14 |

Mediumを先に解いてたら分かったのかも・・・いや分からなかったかな

• isle(),summary()はMediumのような問題のために書いてみた
  • isle(map)でグラフを島分けしたvector<int>を返し
  • summary() でその結果から各島のノード数をまとめる
• これってcafelierさんのunion-findがやろうとしてる事かな
• グラフ系問題にもっと慣れないと駄目だ

#define sz(a)  int((a).size())
#define rep(var,n)  for(int var=0;var<(n);var++)

vector<int> isle(const vector<vector<bool> >& plan) {
  /// vector<string> にすれば、YNが入ったやつも行ける
  int n=plan.size();
  vector<int> id(n,0); for(int i=0;i<n;i++) id[i]=i;
  for (int i=0;i<n-1;i++) {
    for (int j=i+1;j<n;j++) {
      if (plan[i][j]) {    /// plan[i][j]=='Y'とか
        int idi=id[i],idj=id[j];
        if (idi>idj) {
          replace(id.begin(),id.end(),idi,idj);
        } else if (idi<idj) {
          replace(id.begin(),id.end(),idj,idi);
        }
      }
    }
  }
  return id;
}

map<int,int> summary(const vector<int>& id)
{
  map<int,int> s;
  for(int i=id.size()-1;i>=0;i--){
    if(s.find(id[i])==s.end()) s[id[i]]=1;
    else s[id[i]]++;
  }
  return s;
}

class PerfectPermutation {
 public:
  int reorder(vector<int> P) {
    int n=sz(P);
    vector<vector<bool> > a(n,vector<bool>(n,false));
    rep(i,n) a[i][P[i]]=a[P[i]][i]=true;
    map<int,int> isles=summary(isle(a));
    int s=sz(isles);
    return (s==1)?0:s;
  }
};