Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

ARC 003 D - シャッフル席替え (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #003
問題文

問題概要

N人 (11以下) の人が,等間隔に円周上に座っている.
隣会いたくない人の組がM (10以下) 与えられる.
K回 (0以上20以下) だけランダムに異なる2人を選んで,入れ替えるという操作を行う.
隣会いたくない人の組が全部隣り合ってない確率を求める問題.
絶対誤差2*10^-3以下であれば正答とみなされる.

解法

許容誤差がとても大きいので,モンテカルロ法.
十分な回数だけランダムにシミュレーションして確率を計算すれば良い.

Cによるスパゲッティなソースコード
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

unsigned myrand(){
  static unsigned x=123456789, y=362436069, z=521288629, w=88675121;
  unsigned t;
  t = (x^(x<<11));
  x=y; y=z; z=w;
  w = (w^(w>>19))^(t^(t>>8));
  return w;
}

int main(){
  int i,j,k,l,m,n,loop;
  int now[12];
  int lis[20][20];
  double ok, dame;

  scanf("%d%d%d",&n,&m,&k);
  rep(i,n) rep(j,n) lis[i][j] = 0;
  while(m--){
    scanf("%d%d",&i,&j);
    lis[i][j] = lis[j][i] = 1;
  }

  ok = dame = 0;
  rep(loop,16000000){
    rep(i,n) now[i] = i;
    rep(l,k){
      i = myrand() % n;
      j = myrand() % (n-1);
      if(j >= i) j++;
      m = now[i]; now[i] = now[j]; now[j] = m;
    }
    m = 0;
    rep(i,n-1) m += lis[now[i]][now[i+1]];
    m += lis[now[n-1]][now[0]];
    if(m) dame += 1; else ok += 1;
  }

  printf("%.10f\n",ok/(ok+dame));

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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