Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1047-56e3e817
この記事にトラックバックする(FC2ブログユーザー)

SRM464 DIV1 EASY/DIV2 MEDIUM - ColorfulStrings (この記事を編集する[管理者用])

Source

TopCoder SRM464 DIV1 EASY (250pt)
TopCoder SRM464 DIV2 MEDIUM (500pt)
Problem Statement
SRM 464 自分の参加記録

問題概要

全ての部分文字列の積が異なるような長さnの数字の中でk番目に小さいものを求める問題.
nは50以下,kは10^9以下.

解法

同じ文字は使えないので長さは10以下じゃないと存在しない.
もうちょっと考えると,0と1は長さ1のときしか使えないので,長さ8以下.
長さ1の時は例外処理して,長さが2から8の時は,全列挙してみる.

C++によるスパゲッティなソースコード

このコードは実際に本番にサブミットしたコードです.

// #includeとusing namespace std;は略

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int is_ok(int in[],int k){
  int i,a,b,c,d,A,B;

  rep(a,k) REP(b,a,k){
    A=1; REP(i,a,b+1) A*=in[i];
    REP(c,a+1,k) REP(d,c,k){
      B=1; REP(i,c,d+1) B*=in[i];
      if(A==B) return 0;
    }
  }
  return 1;
}

class ColorfulStrings {
public:
string getKth(int n, int k) {
  int i,j,in[8]={2,3,4,5,6,7,8,9},cnt=0;
  string res="", tmp;
  vector<string> gen;

  if(n==1){
    if(k<=10) res+=(char)('0'+k-1);
    return res;
  }
  if(n>=9) return res;

  do{
    if(!is_ok(in,n)) continue;
    tmp="";
    rep(i,n) tmp += (char)('0'+in[i]);
    if(gen.size() && gen[gen.size()-1]==tmp); else gen.push_back(tmp);
  }while(next_permutation(in,in+8));

  if(k-1<gen.size()) res=gen[k-1];
  return res;
}

};

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1047-56e3e817
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。