2537:Tight words - komiyamの日記

keyword

概要

[0..k](k<=9)の文字を繋げて長さn(<100)の文字列を作る。このとき隣接する要素の差が1以下であるような文字列の出現率を求める問題。
末尾の数字と文字列の長さでDPすれば該当する文字列の個数が分かる。計算量は最大で10*100だから余裕。ただし全ての文字列の作り方が10^100だったりして精度に不安がある。JavaでBigIntegerとかBigDecimal使っても良いけど手抜きでdoubleを使った。これだと落ちたのでlong doubleに修正して送信したら無事AC。

int main(){
    long double total;
    int k, n, i, j;
    long double dp[102][10];

    while(scanf("%d %d", &k, &n)!=EOF){
        REP(i,102)REP(j,10) dp[i][j] = 0.0;
        total = pow((long double)k+1, n);
        REP(j,k+1)dp[1][j] = 1.0;
        for(i=2;i<=n;i++)REP(j,k+1){
            if(j>0) dp[i][j-1] += dp[i-1][j];
            dp[i][j] += dp[i-1][j];
            if(j<k) dp[i][j+1] += dp[i-1][j];
        }
        printf("%.5llf\n", accumulate(dp[n],dp[n]+k+1,(long double)0.0)/total*100+(long double)EPS);
    }

    return 0;
}