Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

Source

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

問題概要

1桁以上9桁以下の文字列が50個以下与えられる.文字は0~9の数字.
000000000~999999999までの数字の中で,少なくても1つ与えられた文字列をサフィックスにもつものの割合を求める問題.

解法

他のもののサフィックスになる文字列を取り除く.
後は,その文字列に 10^文字列の長さ に1個該当し,重複して該当することはないので,数えるだけ.

C++によるスパゲッティなソースコード
// #includeとusing namespace std;は略

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

class TheLotteryBothDivs {
public:
double find(vector <string> in) {
  int i,j,k,n;
  double res = 0;
  int ok[60]={};

  n=in.size();
  sort(in.begin(), in.end());

  k=1;
  REP(i,1,n) if(in[i]!=in[i-1]) in[k++] = in[i];
  n=k;

  rep(i,n) rep(j,n) if(i!=j) if(in[i].size() <= in[j].size()){
    if(in[j].substr(in[j].size()-in[i].size()) == in[i]) ok[j] = 1;
  }

/*  rep(i,n) printf("%d %d\n",ok[i],in[i].size());*/
  rep(i,n) if(!ok[i]) res += 1.0 / pow(10.0, (double)(in[i].size()));

  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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