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;
  }
};

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

SRM441

02:17 | SRM441 - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM441 - naoya_t@topcoder SRM441 - naoya_t@topcoder のブックマークコメント

05.27+.2009

DIVlevel問題名競技中後でSystem Test通過率備考
1 250 PerfectPermutation 提出せず - -
1 500 StrangeCountry 撃沈 - - -
1 1000 - -

250点問題: PerfectPermutation

  • 問題文のテストケースは全部通るが、最悪ケースで帰ってこないプログラムが仕上がった
  • 提出はしていない
  • みんな単純なコードだった><

明日の自分のために恥コードを晒しておくか

class PerfectPermutation {
  vi p_,q; int N, difm;
  map<ll,int> mp;
 public:
  void sub(ll rest,int cur,int diff){
    ll key=rest;
    if(found(mp,key)){ if(mp[key]<diff) return; }
    mp[key]=diff;
    if (diff>=difm)return;
    if (rest==0){
      if(diff<difm)difm=diff;
      return;
    }
    ll m=1LL;
    rep(i,N){
      if(i==cur)goto skip;
      if(!(m&rest))goto skip;
      if(q[cur]>=0)goto skip;
      q[cur]=i;
      sub(rest-m,i,(q[cur]==p_[cur])?diff:(diff+1));
      q[cur]=-1;
   skip:
      m<<=1;
    }
  }
  int reorder(vector <int> P) {
    N=sz(P); p_.resize(N); rep(i,N) p_[i]=P[i];
    difm=INT_MAX;

    ll rest=(1LL<<N)-1;
    q.resize(N); rep(i,N)q[i]=-1;
    sub(rest,0,0);
    return difm;
  }
};

↑問題文のTestCaseは余裕で通るけど、N=50のときに死にます

500点問題: StrangeCountry

  • テストケースは全部通る
  • 50x50でもまあなんとか
  • submitted. 300.xxpoints
  • challenge timeにLayCurse先生に撃墜された
  • 孤立点を考慮してない!!最初の島分けが間違ってる!!orz

1000点問題:

  • 開いてない!

Challenge Time

0点で室内16位。Div1全体では439/600位

1501→1393 (△108)

http://gyazo.com/a46ba90b6715d83fe0456ffcacf1b6dc.png

また青くなった><

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