Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

Source

TopCoder SRM475 DIV1 EASY (300pt)
TopCoder SRM475 DIV2 MEDIUM (550pt)
Problem Statement
SRM475 DIV1 自分の参加記録

問題概要

最初,17マス以下のセルが直線上にある.
ランダムにウサギが,r匹いる.
端のウサギは真ん中よりに,W色のセルにいるウサギは右へ,B色のセルにいるウサギは左へ,R色のセルにいるウサギは前いたセルに戻る(最初だったら左へ行く).
同じマスに2匹の兎が集まると居なくなる.
毎ターン,右端のマス目が消える.
残り2マスになったとき,うさぎの残りの数の期待値を求める問題.
細かい条件は問題文参照.

解法

初期パターンを全部列挙して,全部シミュレーションすれば良い.
実は,シミュレーションしなくても,偶奇に着目すれば解ける.
初期値で,偶数番目のセルにいるウサギの集合と,奇数番目のセルのいるウサギの集合に分割して考えると,
それぞれ衝突せず,衝突するときは必ず2匹が衝突して消え,最終的に辿りつける可能性のあるセルは,それぞれ1個なので,
それぞれ,奇数だけのうさぎがいると,それぞれ最後に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)

int bef[20], next[20];

int solve(int n, string mp, int d[]){
  int i,j,k;

  rep(i,n) bef[i] = 1;

  while(n>2){
    rep(i,n) next[i]=0;
    rep(i,n) if(d[i]){
      if(i==0){ next[1] ^= 1; bef[1]=-1; continue; }
      if(i==n-1 || i==n-2){ next[i-1]^=1; bef[i-1]=1; continue; }
      if(mp[i]=='W'){ next[i-1]^=1; bef[i-1]= 1; continue; }
      if(mp[i]=='B'){ next[i+1]^=1; bef[i+1]=-1; continue; }
      if(mp[i]=='R'){ next[i+bef[i]]^=1; bef[i+bef[i]]=-bef[i]; continue; }
    }
    rep(i,n) d[i]=next[i];
    n--;
  }

  return d[0] + d[1];
}

class RabbitStepping {
public:
double getExpected(string field, int r) {
  int i,j,k,n;
  double res=0, per=0;
  int d[100], t[100];

  n=field.size();
  rep(i,n) t[i]=0;
  rep(i,r) t[n-1-i]=1;

  do{
    rep(i,n) d[i]=t[i];
    res += solve(n, field, d);
    per += 1;
  }while(next_permutation(t,t+n));

  return res / per;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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