唯物是真 @Scaled_Wurm

プログラミング(主にPython2.7)とか機械学習とか

TopCoder SRM 654 Div1 o-- 1283->1323

たまたま時間的に参加できた
190th, 91.23pts, +0/-0 challenge
Volatility: 324->304

writerの解説sigma425.hatenablog.com

今回も途中で問題文に訂正が入ったのでunratedかと心配になった

Div1 Easyが動的計画法っぽいというのはすぐにわかったのに終了直前まで解けずorz
Pythonで1000 * 1000 * 26ぐらいのループが通るかどうか自信がなかったので適当に定数倍高速化をしていた

250: SquareScores

'a'から'z'のアルファベットと'?'で構成された文字列\(s\)が与えられる(\(s\)の長さは最大1000)
'?'の部分は与えられる確率の配列\(p\)にしたがって'a'から'z'の文字列にランダムに置き換わる
このとき同じ文字が1個以上連続したsubstringの作り方の組み合わせの数(同じ文字でも別の位置なら違うsubstringとみなす)の期待値を答える(誤差は\(10^{-9}\)以下)
たとえば"aaaba"ならsubstringの組み合わせの数は8("a": 4,"aa": 2, "aaa": 1, "b": 1)

期待値の線形性より文字ごとに計算した結果の和を求めればよい
注目する文字ごとに、文字列のある位置で、連続した同じ文字の長さが\(l\)になる確率を求めて足していく

'?'がたくさんのケースに対する高速化のために確率が\(10^{-40}\)という適当な値以下になったらそれ以上の長さについては計算しないっていうのを入れといた
'?'の長さが長くなると確率は指数的に減少するので、あまり長い場合については考えないでよい

他の人の解法を見ていたら短く簡潔に解いていたので解き方が違うっぽい(?)
以下ちょっときれいにしたコード
文字列の長さを\(N\)、文字の種類数を\(K\)とすると最悪計算量は\(O(N^2K)\)ぐらい?

# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect

class SquareScores:
    def calcexpectation(self, p, s):
        result = 0.0
        L = len(s)
        A = len(p)
        tpl = [1] + [0] * L
        mapp = {chr(97 + i): i for i in xrange(A)}
        EPS = 1e-40
        
        for a in mapp.keys():
            dp = tpl[:]
            pa = p[mapp[a]] / 100.0
            for c in s:
                new_dp = tpl[:]
                for l in xrange(1, L + 1):
                    if c == a:
                        new_dp[l] = dp[l - 1]
                    elif c == '?':
                        new_dp[l] = dp[l - 1] * pa
                    else:
                        break
                    result += new_dp[l]
                    if new_dp[l] <= EPS:
                        break
                dp = new_dp
        return result

以下の記事を読んでいたところDPの回し方を変えれば配列が要らなくなるらしいので修正

'?'を含まない文字列の場合は、\(i\)番目に多く出てくる文字について多めに見積もっても\(\frac{N^2}{i^2}\)回のループをすればよい
二乗で割っていく時の調和級数\(\sum_{i=1}^N \frac{1}{i^2}\)は定数に収束するので計算量は\(O(N^2)\)

'?'だけを含む文字列を考えると文字列の2番め以降に確率の高い文字について、確率を\(\frac{1}{2}\)と多めに見積もっても、指数的に減っていってすぐに誤差よりもかなり小さくなるので、連続する文字に対するループ数はたかだか定数回なので計算量は\(O(NK)\)ぐらい
一番高い確率の文字は最後までループすると考えて\(O(N^2)\)
これらをまとめると全体で\(O(N^2)\)ぐらいになる

# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect

class SquareScores:
    def calcexpectation(self, p, s):
        result = 0.0
        L = len(s)
        A = len(p)
        mapp = {chr(97 + i): i for i in xrange(A)}
        EPS = 1e-40
        
        for a in mapp.keys():
            pa = p[mapp[a]] / 100.0
            for i in xrange(L):
                prob = 1
                for j, c in enumerate(s[i:], i):
                    if c == '?':
                        prob = prob * pa
                    elif c != a:
                        break
                    result += prob
                    if prob <= EPS:
                        break
        return result

writerの解説には\(O(NK)\)の解があると書かれているけど、考えてもわからなかったorz
一つ考えたのは区間の期待値の和をしゃくとり法っぽく更新していく方法なのだけれど、実際に試してみたら浮動小数点演算の誤差で動かなかった(\(\frac{1}{100}^{1000}\)とか出てくるから当たり前)