Yandex.Algorithm 2015 Online Finals F問題 - Random Points

Source

Yandex.Algorithm 2015
Yandex.Algorithm 2015 Online Finals
問題文

問題概要

次のような擬似乱数生成法を考える. 最初に種となる整数 $s, \;\; 0 \leq s < 2^{32}$ を与える.
$0$ 以上 $x$ 未満の整数を得たいときは,$s$ を $s \leftarrow (as+c)\ {\rm mod}\ 2^{32}$ と置き換えてから $\lfloor sx/2^{32} \rfloor$ を返す.
ここで,パラメータは $a = 134775813, c = 1$ を用いる.
$N$ 個の格子点を以下のどちらかの方法で生成する.
$1$ つ目の方法は,上の擬似乱数生成法により,$2N$ 個の $[0, 10^8)$ の乱数を作り,最初から $2$ 個ずつペアにする.
$2$ つ目の方法は,上の擬似乱数生成法により,$2N$ 個の $[0, 10^8)$ の乱数を作り,それらを上の擬似乱数を使いながらシャッフルした後,$2$ 個ずつペアにする.
(詳細は問題原文を参照)
生成された $N$ 個の点の座標が与えられるので,どちらの方法で生成されたかを判定する問題.

解法

$1$ つ目の方法で生成されたかどうかを判定することにする.
$1$ つ目の方法で生成されたのであれば,最初に生成された整数は最初の座標であり,これを $p$ とすると,その時の種の値はだいたい $p \times 2^{32} / 10^8$ ぐらいということになる.
$x=10^8$ の時,$\lfloor sx/2^{32} \rfloor$ の値が等しくなる $s$ の範囲は広くないので,種は $X \times 2^{32} / 10^8$ の周辺の何処か狭い範囲にいる.
よって,考えうる種を全部試し,問題に書かれた擬似乱数生成法で入力が再現することがあるかどうかを調べれば良い.

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

#include<bits/stdc++.h>
using namespace std;

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

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

#define ll long long
#define ull unsigned ll

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void writer(const char x[], char c){int i;for(i=0;x[i]!='\0';i++)mypc(x[i]);mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}

unsigned seed = 1234u;
int get(void){
  seed = 134775813U * seed + 1U;
  return (seed * 100000000ULL) >> 32;
}

int in[300000];

int A[10000], B[10000];

int main(){
  int i, j, k;
  int N, a, b;
  ull m;

  reader(&N);
  N *= 2;
  rep(i,N) reader(in+i);

  m = (((ull)in[0])<<32) / 100000000;

  REP(i,-100,100){
    seed = (unsigned)( ((ll)m + i + (1LL<<33)) % (1ULL<<32) );
    REP(j,1,100){
      k = get();
      if(k!=in[j]) break;
    }
    if(j==100){ writerLn("RAW"); return 0; }
  }

  writerLn("SHUFFLED");

  return 0;
}

Current time: 2017年07月23日17時40分17秒
Last modified: 2015年08月15日14時42分24秒 (by laycrs)
Tags: Competitive_Programming Yandex_Algorithm Yandex_Algorithm_2015 Yandex_Algorithm_2015_Finals
トップページに戻る

Logged in as: unknown user (not login)

ログイン: