保存されている過去のバージョンの一覧

2014年04月26日14時39分17秒
2014年04月26日14時33分27秒
2014年04月26日14時31分50秒

Google Code Jam 2014 Round 1A C問題 - Proper Shuffle

Source

Google Code Jam 2014 Round 1A C問題
Problem Statement

問題概要

$0$ から $N-1$ までの置換を $\verb|a|$ をランダムに生成する方法を考える．
$1$ つ目は

  for(k=0;k<N;k++) a[k] = k;
  for(k=0;k<N;k++){
    p = RAND(k, N-1);
    swap(a[k], a[p]);
  }

とする方法で，全ての置換が等確率で生成されることがわかっている．
ただし，$\verb|RAND(|a\verb|,|b\verb|)|$ は $a$ 以上 $b$ 以下の整数を等確率で返す関数．
$2$ つ目は

  for(k=0;k<N;k++) a[k] = k;
  for(k=0;k<N;k++){
    p = RAND(0, N-1);
    swap(a[k], a[p]);
  }

とする方法で，これは全ての置換が等確率で生成されるわけではない．
$1$ つ目の方法を良い方法，$2$ つ目の方法を悪い方法と呼ぶ．
テストケースごとに，等確率でランダムにどちらかの方法を選び，その方法で生成された置換が与えられる．
どちらの方法で生成された置換かを求める問題．
テストケースの数 $T$ は $120$ で，そのうち，$G = 109$ ケース以上で正解したら正答とみなす．
また，全てのテストケースにおいて，$N=1000$ である．

解法

良い方法では全ての置換が等確率で生成されるので，与えられた置換が悪い方法で生成される確率が $1/N!$ 以下か以上かを求めれば良いことになる．
が，それを厳密に求めるのは難しい．
そこで，悪い方法で，$10^6$ 個程度置換を実際に生成してみて，$\verb|a[|i\verb|]=|j$ となる確率を $i,j=0,1,\ldots,999$ について求めておき，
与えられた置換に対し，各場所において，その場所にその整数がある確率を全部掛けたものが $1/N^N$ より大きいかどうかを調べて，それで代用する．
$\verb|a[|i\verb|]=|j$ を実際に見てみると，どのような傾向があるかは明確にわかり，それをうまく使っても良い（らしい）．
アンダーフローを回避するため，$\verb|a[|i\verb|]=|j$ となる確率は $N$ 倍して覚えておくと良い．

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

#include<cstdio>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
#include<string>
#include<utility>
#include<iostream>
#include<cmath>
using namespace std;

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

double Gper[1200][1200];

void test3(int n, int t){
  int i, j, k, loop;
  vector<int> p;
  static int per[1200][1200] = {};

  rep(i,n) p.push_back(i);

  rep(loop,t){
    rep(i,n) p[i] = i;
    rep(i,n){
      k = rand() % n; // bad
      swap(p[i], p[k]);
    }

    rep(i,n) per[i][p[i]]++;
  }

  rep(i,n) rep(j,n) Gper[i][j] = (double)per[i][j] / t * n;
//  rep(i,n){ rep(j,n) printf("%f ",(double)per[i][j]/t*n); puts(""); }
}

int main(){
  int i,j,k;
  int T, cnt = 0;
  int N, p[2000], sum;
  double res;
 
  test3(1000, 1000000);
  
  scanf("%d",&T);
  while(T--){
    fprintf(stderr,"rest %d\n",T);
    printf("Case #%d: ", ++cnt);

    scanf("%d",&N);
    rep(i,N) scanf("%d",p+i);
    res = 1;
    rep(i,N) res *= Gper[i][p[i]];
    if(res <= 1) puts("GOOD"); else puts("BAD");
  }

  return 0;
}

Current time: 2024年04月19日03時11分25秒
Last modified: 2014年04月26日14時39分17秒 (by laycrs)
Tags: Competitive_Programming Google_Code_Jam GCJ_2014 GCJ_2014_Round_1A
トップページに戻る

Logged in as: unknown user (not login)

ログイン：