Yandex.Algorithm 2014 Round 3 B問題 - Science

Source

Yandex.Algorithm 2014
Yandex.Algorithm 2014 Round 3
問題文

問題概要

長さ $N$ の文字列で,各文字が等確率,かつ,独立に $\verb|A|$ か $\verb|B|$ であるようなものを考える.
この文字列の部分文字列で,$\verb|B|$ が $1$ つ,$\verb|A|$ が $K$ 個,$\verb|B|$ が $1$ つ,という風に並んだ $K+2$ 文字の部分は何箇所あるか,という期待値を求める問題.

解法

$K+2$ 文字の部分文字列の候補は $N - K - 1$ 通りあって,それぞれ確率 $(1/2)^{K+2}$ で条件を満たすから,答えは $(N - K - 1) / 2^{K+2}$.
ただし,$N-K-1$ が負の時は答えは $0$.
$K \leq 100$ なので,今 $\verb|A|$ が連続で何文字続いているかを状態としたDPを行列べき乗で解いても良い.
時間計算量は前者で $O(\log K)$,または,$O(1)$,後者で $O(K^3 \log N)$.

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 ll long long
#define mygc(c) (c)=getchar_unlocked()
void reader(ll *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);}

ll N, K;

int main(){
  double res;
  reader(&N);
  reader(&K);
  res = max(0.0, pow(0.5, K+2) * (N-K-1));
  printf("%.10f\n", res);
  return 0;
}

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 ll long long
#define mygc(c) (c)=getchar_unlocked()
void reader(ll *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);}

typedef struct ll_matrix{
  int r,c;
  double **data;
}llMatrix;

llMatrix newLLMatrix(int r,int c){
  int i; llMatrix res;
  res.r=r; res.c=c;
  res.data    = (double**) malloc(r*sizeof(double*));
  res.data[0] = (double*) malloc(r*c*sizeof(double));
  REP(i,1,r) res.data[i] = res.data[i-1]+c;
  return res;
}

void* setMemoryLLMatrix(llMatrix *a,int r,int c,void *WorkMemory){
  int i;
  a->r=r; a->c=c;
  a->data = (double**)WorkMemory; WorkMemory = (void*)(a->data + r);
  rep(i,r){a->data[i] = (double*)WorkMemory; WorkMemory = (void*) (a->data[i] + c);}
  return WorkMemory;
}

void deleteLLMatrix(llMatrix *a){
  free(a->data[0]); free(a->data);
}

void llMatrixSetZero(llMatrix *a){
  int i,j;
  rep(i,a->r) rep(j,a->c) a->data[i][j]=0;
}

void llMatrixSetIdentity(llMatrix *a){
  int i,mx;
  mx=a->r; if(mx>a->c) mx=a->c;
  llMatrixSetZero(a); rep(i,mx) a->data[i][i]=1;
}

void llMatrixMultipleMod(llMatrix *a,llMatrix *b,llMatrix *res,ll m){
  int i,j,k;
  llMatrixSetZero(res);
  rep(i,res->r) rep(k,b->r) if(a->data[i][k]) rep(j,res->c) {
    res->data[i][j]+=a->data[i][k]*b->data[k][j];
  }
}

void llMatrixPowerMod(llMatrix *a,llMatrix *res,ll k,ll m,void *WorkMemory){
  int i,j,n=a->r;
  llMatrix tmp1,tmp2;
  
  res->r=res->c=n;
  if(k==0){ llMatrixSetIdentity(res); return; }
  if(k==1){ rep(i,n)rep(j,n)res->data[i][j]=a->data[i][j]; return; }
  if(k==2){ llMatrixMultipleMod(a,a,res,m); return; }

  WorkMemory = setMemoryLLMatrix(&tmp1,n,n,WorkMemory);
  llMatrixPowerMod(a, &tmp1, k/2, m, WorkMemory);
  if(k%2==0) llMatrixMultipleMod(&tmp1,&tmp1,res,m);
  else {
    WorkMemory = setMemoryLLMatrix(&tmp2,n,n,WorkMemory);
    llMatrixMultipleMod(&tmp1,&tmp1,&tmp2,m);
    llMatrixMultipleMod(a,&tmp2,res,m);
  }
}

ll N, K;

int main(){
  int i, j;
  
  void *mem = malloc(100000000);
  llMatrix mt = newLLMatrix(110, 110);
  llMatrix pw = newLLMatrix(110, 110);

  reader(&N);
  reader(&K);

  mt.r = mt.c = K+3;
  rep(i,K+3) rep(j,K+3) mt.data[i][j] = 0;
  
  rep(i,K+1) mt.data[i][i+1] += 0.5;
  mt.data[K+1][K+1] += 0.5;

  rep(i,K+2) mt.data[i][0] += 0.5;
  mt.data[K][K+2] += 0.5;

  mt.data[K+2][K+2] += 1;

  llMatrixPowerMod(&mt, &pw, N, 0, mem);

  printf("%.10f\n", pw.data[K+1][K+2]);

  if(0){
    int loop;
    double ok = 0, all = 0;
    char arr[2000];

    rep(loop, 100000){
      rep(i,N) arr[i] = rand()%2;
      rep(i,N){
        if(i+K+1 >= N) break;
        if(arr[i] != 0 || arr[i+K+1] != 0) continue;
        rep(j,K) if(arr[i+1+j] != 1) break;
        if(j<K) continue;
        ok++;
      }
      all++;
    }

    printf("%f\n",ok/all);
  }

  return 0;
}

Current time: 2017年07月24日15時48分10秒
Last modified: 2014年08月06日01時21分25秒 (by laycrs)
Tags: Competitive_Programming Yandex_Algorithm Yandex_Algorithm_2014 Yandex_Algorithm_2014_Round3
トップページに戻る

Logged in as: unknown user (not login)

ログイン: