Hatena::Grouptopcoder

kuuso1の日記

2017-01-11

SRM 654 Div1 Easy SquareScores

| 23:40 | SRM 654 Div1 Easy SquareScores - kuuso1の日記 を含むブックマーク はてなブックマーク - SRM 654 Div1 Easy SquareScores - kuuso1の日記

https://community.topcoder.com/stat?c=problem_statement&pm=13694

  • M 文字の小文字のアルファベットと '?' からなる長さ N の文字列 S が与えられる.
  • '?' には 確率 p[i] percent で 文字 c が入る ( c は アルファベット順で i 番目の 文字).
  • ある文字列のスコアは 同じ文字が連続する部分文字列1つごとに 1ポイント入り,その合計であらわされる

 例えば aaaba の場合, a × 4 , aa × 2, aaa × 1, b × 1 で スコアは 8 となる.

  • 与えられた文字列 S のスコアの期待値を求めよ

(制約)1 ≤ N ≤ 1000,1 ≤ M ≤ 26

・期待値の線形性を使う問題について最近開眼した気がしたので日記に書く.

・期待値の線形性の証明の概要を眺める.

f:id:kuuso1:20170111232341p:image

・ある事象Xの期待値を考えるときに,Yが起きる確率も起きない確率も全部足すので結局Xが起きる確率だけを考えればいいというのが 証明のポイントなのですが,そう思うと,「複合してる要素があっても最小単位まで分解すればいい」「ただし,網羅性が必要」の 2点に気を付ければいいのではというのが最近の気づき.

・そう思って今回の問題を見る

f:id:kuuso1:20170111232342p:image

・例えば aaa* にはa***が含まれるような気がするかもしれないが,

 これは aaa* が起きる(X)に対してa***が起きる確率がP(X)=P(X,Y)+P(X,/Y)のP(X,/Y)=0となっているだけ,みたいに考えるといい感じ.

・という事でコード.最初に書いたACコードはO(N^2*M)

// O(N^2*M)
public class SquareScores {
    public double calcexpectation(int[] p, string s) {
        int N = s.Length;
        int M = p.Length;
        double[] P0 = new double[M];
        for(int j=0;j<M;j++) P0[j] = (double)p[j] / 100.0;
        
        double ret = 0;
        for(int i=0;i<N;i++){
            double[] P = new double[M];
            if(s[i] == '?'){
                for(int j=0;j<M;j++) P[j] = (double)p[j] / 100.0;
            }else{
                P[s[i] - 'a'] = 1.0;
            }
            for(int l=1;i+l-1<N;l++){
                if(l == 1){
                    ret += 1.0;
                    continue;
                }
                if(s[i+l-1] == '?'){
                    double sum = 0.0;
                    for(int j=0;j<M;j++){
                        P[j] *= P0[j];
                        sum += P[j];
                    }
                    ret += sum;
                }else{
                    double sum = 0.0;
                    for(int j=0;j<M;j++){
                        P[j] *= (j == s[i+l-1] - 'a') ? 1.0 : 0.0;
                        sum += P[j];
                    }
                    ret += sum;
                }
            }
        }
        
        return ret;
        
    }

ついでにO(NM)も

// O(NM)
public class SquareScores {
    public double calcexpectation(int[] p, string s) {
        
        int N = s.Length;
        int M = p.Length;
        double[] P0 = new double[M];
        for(int j=0;j<M;j++) P0[j] = (double)p[j] / 100.0;
        
        double[] P = new double[M];
        for(int j=0;j<M;j++) P[j] = 0.0;
        double ret = 0;
        for(int i=0;i<N;i++){
            if(s[i] == '?'){
                for(int j=0;j<M;j++){
                    P[j] = (P[j] + 1.0) * P0[j];
                }
            }else{
                for(int j=0;j<M;j++){
                    P[j] = (P[j] + 1.0) * ( j == (s[i] - 'a') ? 1.0 : 0.0 );
                }
            }
            ret += P.Sum();
        }
        
        return ret;
    }

SRM埋め(SRM660-679)をしようとしてSRM654を開いてしまったが例題的良問だと思ったので.sigma425さんwriter回だった模様.

・最近違うところで見た期待値の線形性を使う問題も同じように考えれば解けるので一応リンク貼ってみますが,こちらは脳内ACでもう十分なやつ.

 https://www.hackerrank.com/contests/infinitum17/challenges/matchstick-experiment