Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2010-03-17

SRM464

01:59 | SRM464 - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM464 - naoya_t@topcoder SRM464 - naoya_t@topcoder のブックマークコメント

参加50回目。

DIVlevel問題名競技中後でSystem Test通過率備考
1 250 ColorfulStrings o - 撃沈 - 0.0
1 550 ColorfulDecoration 間に合わず - - - -
1 1000 - - -

Easy(250): ColorfulStrings

  • "23456789"のpermutationを回して上n桁取るとかいう賢くないやり方。n>8とかk>8!の場合は無条件に""
  • 提出コード(恥晒し)
#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0;var<(n);var++)
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define found(s,e)  ((s).find(e)!=(s).end())
 
class ColorfulStrings {
  vector<char> u;
  int n_;
  
  bool p() {
    set<int> m;
    rep(i,n_) {
      int x=1;
      rep(k, n_-i){
        x *= (int)u[i+k];
        if (found(m,x)) return false;
        m.insert(x);
      }
    }
    return true;
  }
 
 public:
  string getKth(int n, int k) {
    n_=n;
    if (n>8) return "";
    if (k>40320) return "";
 
    u.resize(8); rep(i,8) u[i]=2+i;
    int y=0,la=0;
    set<int> lu;
    do {
      int z=0,w=1;rep(i,n){z+=w*(int)u[i];w*=10;} if(found(lu,z)) continue;lu.insert(z);
 
      la = u[n-1];
      if (!p()) continue;
      if (++y==k) {
        rep(i,n_) u[i]+='0';
        return string(u.begin(), u.begin()+n);
      }
    } while(next_permutation(all(u)));
    return "";
  }
};

Medium(550): ColorfulDecoration

Hard(1000): 開いてない

Challenge Phase:

  • 速攻撃沈
  • 1桁の場合は0も1も使えますねはい
  • もうがっかりだよ
  • というわけで。k>40320(=8!)判定の直後に
    if (n==1) {
      if (k<=10) { string s; s.pb('0'+k-1); return s; }
      else return "";
    }

とか入れれば行けます(行けました)。こんなのに気付かないなんて職業プログラマ失格です…n=1から出直します。

Result:

0 point

Room: 12/20

Div I: 418/776

1487 → 1438 (-49) 微落

http://gyazo.com/c8295fcd488a7045ba926c64fb086e22.png

青の中で激しく浮き沈みを繰り返すばかり。とりあえずEasyを確実に取れるようにならないと駄目だな。

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