Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM531 DIV1 MEDIUM - MonsterFarm (この記事を編集する[管理者用])

Source

TopCoder SRM531 DIV1 MEDIUM (500pt)
Problem Statement

問題概要

この世の中にはN種類 (50以下) のモンスターがいる.
最初は,種類1のモンスターが1匹だけいる.
各種類のモンスターはちょうど1日で死に,死んだ時に,新しくモンスターを生み出し,そのとき,新しく生み出されるモンスターの種類の番号が与えられる.
各種類が死んだ時に生み出されるモンスターの数は1以上24以下ぐらい.
総モンスター数は,無限に増えるかどうかを判定し,有限に収束するなら,最終的なモンスター数 mod 1000000007で求める問題.

解法

増え続けるなら,N日に1日は必ず増える.有限にとどまるなら,N日以内に収束する.
なので,2N日以上ぐらいシミュレーションしてあげれば良い.
ただし,modを取りながらシミュレーションすると,増え続けているのに,見かけ上収束する可能性があるので,そこだけ注意する.
回避法は,複数のランダムなmodを試して,本当に収束してるか確認する方法(以下のコードはこれ)や,
グラフの形を見て,発散するかどうかを最初に判定して上げる方法がある.
グラフの形が,種類Kは,種類1からいつか作られるモンスターで,種類Kから種類Kはいつか作られ,種類Kから一度に作られるモンスターが2匹以上,
みたいなKが存在すれば無限に増える.

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

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

#define M 1000000007
#define ll long long

int getPrime(int n,int p[]){int i,j,n2=n/2;rep(i,n2)p[i]=1;for(i=3;i*i<n;i+=2)if(p[i>>1])for(j=(i*i)>>1;j<n2;j+=i)p[j]=0;j=1;p[0]=2;REP(i,1,n2)if(p[i])p[j++]=i*2+1;return j;}
int ps, p[1000000];

int read_int_from_char(const char in[],int l,int ret[]){
  int i,n,fg,mfg;
  if(l<0) {for(i=0;;i++) if(in[i]<' ') break; l=i;}
  n=0; fg=0; mfg=0; ret[0]=0;
  rep(i,l+1){
    if(in[i]=='-'){mfg=1; continue;}
    if(isdigit(in[i])){ret[n]=ret[n]*10+in[i]-'0'; fg=1; continue;}
    if(!fg) continue;
    fg=0; if(mfg){ret[n]=-ret[n]; mfg=0;}
    ret[++n]=0;
  }
  return n;
}


class MonsterFarm {
public:
int numMonsters(vector <string> transforms) {
  int i,j,n,loop,go;
  int edge[51][51], es[51];
  ll now[51], next[51], sum, old_sum, seq;

  srand(time(NULL));

  n = transforms.size();
  rep(i,n) es[i] = read_int_from_char(transforms[i].c_str(), -1, edge[i]);
  rep(i,n) rep(j,es[i]) edge[i][j]--;

  ps = getPrime(1000000, p);

  rep(go,21){
    int mod = p[rand()%ps];
    if(go == 20) mod = M;
    
    rep(i,n) now[i] = 0;
    now[0] = 1;
    old_sum = 1;
    seq = 0;
    
    rep(loop, 300){
      rep(i,n) next[i] = 0;
      rep(i,n) rep(j,es[i]) next[edge[i][j]] += now[i];
      rep(i,n) next[i] %= mod;
      sum = 0;
      rep(i,n) sum += next[i];
      sum %= mod;
      
      if(old_sum == sum) seq++; else seq = 0;
      if(seq > 2*n) break;
      old_sum = sum;
      rep(i,n) now[i] = next[i];
    }
    if(loop == 300) return -1;
  }

  return sum;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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