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)$.
#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;
}
#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: 2024年04月27日09時48分02秒
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)