Codeforces #54 D Writing a Song

題意﹕給定 $N$ 和 $K$ ，現在有一長度為 $L_P$ 的字串 $P$ 和一長度為 $N - L_P + 1$ 的01字串 $B$ ，並依 $B$ 構造一長度為 $N$ 的字串 $R$ 。若 $B_i$ 為1，則子字串 $R_{i\cdots i+L_P-1}$ 必須要等於字串 $P$ 。若 $B_i$ 為0則該子字串必須不能等於 $P$ 。另，只能使用首 $K$ 個小寫英文字母。問能否存在此字串並輸出答案。

顯然易見的是某些位置該於甚麼字元是固定的。先把那些地方寫好固定的字元。然後檢測有否沖突。如果有衝突的話則必無解。

但，如無衝突的話，可能存在未固定字元的位置，那麼該放甚麼呢？首先理解的是不能亂放。可以參考題中第二樣例。
如果允許字元只有 $\{a, b\}$ 而且 $P = a$ 、 $B = \underbrace{10\cdots 01}_{N-2\text{ zeros}}$ 。那麼除固定首尾為a之外，其餘位置必須放置b。如果隨機放的話，只有 $\frac{1}{2^{N-2}}$ 機會判斷正確。那麼，當 $N$ 很大的時候幾乎沒有可能找到正確(且唯一的)解。那麼是不是代表亂放不奏效？又未必！

其實大可以想想以下一個有可能錯的算法﹕對於未固定位置，枚舉可放置的字元，找到第一個能放的字元又不引起衝突即可。這個算法，相信大家很快找到反例﹕某一個位置首先找到的字元，可能會令往後的任意放置變成無解。於是，先放置甚麼字元就顯得比較重要了。來到這裡，可以問一個問題了﹕能不能應用隨機算法？似乎可行。每次枚舉未固定位置前，先為可用字元隨機取一排列 $\sigma$ ，然後按 $\sigma$ 的順序嘗試。把這個過程重複 $T$ 次，估計誤判沒有解的機會很小。我的算法甚至取 $T = 1$ 都可以安然通過。

至於為甚麼能找到解的機會很高？這個我沒法証明…

另，正確的解法是動態規劃。