naoya_t@topcoder

SRM464

01:59 |

参加50回目。

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

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