GCJ 2015 Round 1C B. Typewriter Monkey

2015/05/13 (Wed) GCJ DP

問題

問題文

$K$ 文字のアルファベット (重複があり得る) からなるキーボードがある． この中から一様ランダムに $S$ 回叩いて，長さ $L$ の目標の文字列を入力したい． 入力された文字列に含まれる，目標の文字列の数の期待値を求めなさい．

方針

Small は全探索する．Large は 「$dp(i,j,k) $ $=$ $i$ 文字目まで打ったときに，過去に $k$ 回最後まで一致していて，今は $j$ 文字目まで一致している確率」とかおいて解くんだと思う…

実装

namespace small {
    int cnt(string have, string target){
        int res = 0;
        rep(i,have.size()-target.size()+1){
            if(have.substr(i,target.size())==target) res++;
        }
        return res;
    }

    double solve(string keys, string target, int S){
        ll pat = 1;
        rep(i,S) pat *= keys.size();
        ll mx = 0, sum = 0;
        rep(mask,pat){
            string r(S,' ');
            int t = mask;
            rep(i,S){
                r[i] = keys[t%keys.size()];
                t/=keys.size();
            }
            ll c = cnt(r,target);
            sum += c;
            mx = max(mx,c);
        }
        return (double)mx-(double)sum/pat;
    }
}

namespace large {
    // あとで解く
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    signed T;
    cin >> T;
    rep(i,T){
        int K,L,S;
        cin >> K >> L >> S;
        string keys; cin >> keys;
        string target; cin >> target;
        // double ans_small = small::solve(keys, target, S);
        double ans_large = large::solve(keys, target, S);
        // printf("Case #%d: %lf\n",(int)i+1,ans_small);
        printf("Case #%d: %lf\n",(int)i+1,ans_large);
    }
}