TopCoder SRM607: PalindromicSubstringsDiv1

PalindromicSubstringsDiv2 と要領は同じ。

Sのi番目からj番目までの部分文字列をS[i,j]と表記する。

「S に含まれている回文の個数の期待値」＝「S の部分文字列の回文の個数の期待値」。期待値の線形性よりこれは「Sのそれぞれの部分文字列について回文になる期待値の和」と等しくなる。Editorialの数式がわかりやすい。期待値問題はこの手の線形性を使った読み替えが常套手段になっている。

S[i,j] が回文になる確率は、「S[i]とS[j]が同じになる確率」×「S[i+1,j-1]が回文になる確率」となる。

S[i]とS[j]が同じになる確率は、片方が'?'の場合は1/26になり、S[i]とS[j]が違うアルファベットなら 0 、同じアルファベットなら 1.0 になる。

あとは動的計画法で計算できるが、PalindromicSubstringsDiv2 と同様にループ処理で書ける。

今回は、Func を使った部分関数で実装してみた。

public class PalindromicSubstringsDiv1 {
    public double expectedPalindromes(string[] S1, string[] S2) {
        var S = String.Concat(S1.Concat(S2));
        int n = S.Length;
        double ans = n;

        Func<int, int, int> solve = (p1, p2) => {
            double p = 1.0;
            while (0 <= p1 && p2 < n) {
                if (S[p1] == '?' || S[p2] == '?') p /= 26;
                else if (S[p1] != S[p2]) break;
                ans += p;
                p1--;
                p2++;
            }
            return 0; // Action<T1,T2> is prohibited !!!!
        };

        for (int i = 0; i < n; i++) {
            solve(i - 1, i + 1);
            solve(i, i + 1);
        }
        return ans;
    }
}