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: 2017年07月25日05時33分07秒
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)

ログイン: