naoya_t@topcoder

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)

また青くなった＞＜