Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2009-05-28

SRM441 Div1 Medium: StrangeCountry

| 04:42 | SRM441 Div1 Medium: StrangeCountry - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM441 Div1 Medium: StrangeCountry - naoya_t@topcoder SRM441 Div1 Medium: StrangeCountry - naoya_t@topcoder のブックマークコメント

  • 方針は大体合ってた
    • 修正1:島分け間違ってた:2つの島が出会った時に島番号が隅まで伝播してない
    • 追加2:孤立点があった時に-1を返してない
  • 以上2点を直してPassed System Test
typedef long long ll;
typedef vector<int> vi;
#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define found(s,e)  ((s).find(e)!=(s).end())

class StrangeCountry {
 public:
  int transform(vector <string> g) {
    int N=sz(g);
    // 島分け
    vi isle(N); rep(i,N) isle[i]=i;
    rep(i,N-1){
      for(int j=i+1;j<N;j++){
        if(g[i][j]=='Y'){
          // isle[j] = isle[i] = min(isle[j],isle[i]); //←駄目コード
          // ↓修正1===
          int i_=isle[i],j_=isle[j],m_=min(i_,j_);
          rep(k,N) if(isle[k]==i_||isle[k]==j_) isle[k]=m_;
          // ↑修正1===
        }
      }
    }

    // 各島に含まれる町の数を数える
    vi cnt(N,0); rep(i,N) cnt[isle[i]]++;
    // ↓追加2===
    rep(i,N) if(cnt[i]==1) return -1; /// 孤立点があれば -1
    // ↑追加2===

    // 島
    set<int> ic; rep(i,N) if(cnt[i]) ic.insert(i);
    // 島内の道の数
    vi hz(N,0);
    rep(i,N-1){
      for(int j=i+1;j<N;j++){
        if(g[i][j]=='Y') hz[isle[i]]++;
      }
    }

    // 各島内の「余ってる」道の数
    vi ov(N,0); rep(i,N) ov[i]=hz[i]-(cnt[i]-1);
    int s=0,k=0;
    tr(ic,it){
      k++; s+=ov[*it];
    }

    // ぜんぶ繋ぐのに必要なだけの余剰道路があるか
    int nz=k-1;
    if(nz>s) return -1;
    return nz;
  }
};

もうちょっとよく考えれば防げるミスで落ちているのが辛いところ。十分に射程圏内なので焦らず確実に。

トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20090528