naoya_t@topcoder

SRM441 Div1 Medium: StrangeCountry

過去問, 練習 | 04:42 |

• 方針は大体合ってた
  • 修正１：島分け間違ってた：２つの島が出会った時に島番号が隅まで伝播してない
  • 追加２：孤立点があった時に-1を返してない
• 以上２点を直して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]); //←駄目コード
          // ↓修正１===
          int i_=isle[i],j_=isle[j],m_=min(i_,j_);
          rep(k,N) if(isle[k]==i_||isle[k]==j_) isle[k]=m_;
          // ↑修正１===
        }
      }
    }

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

    // 島
    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 |

05.27+.2009

DIV	level	問題名	競技中	後で	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)

また青くなった＞＜