SRM 509 Div1 Easy + Medium

Easy: 給了一個不帶零的正整數$N$，可任意刪除數位(不能全部刪除、也可以不刪)但保持其原來次序，可得一集合$\mathcal{S}$。求$\sum_{i \in \mathcal{S}} i \bmod{9}$。例如$N = 123$則答案是
\[ 123 + 12 + 13 + 23 + 1 + 2 + 3 \equiv 177 \equiv 6 \pmod{9}\]
首先求取模$9$的意義。從上式可知
\[ 123 \equiv 1 + 2 + 3\pmod{9}\]
因此其實是問所有數位出現多少次，求和並取模。不難從例子發現，若$N$是一$L$位整數，則每個數位會出現$2^{L-1}$次。設$d(N)$是$N$的數位之和，則答案顯然是\[d(N)\times 2^{L-1} \bmod{9}\]
注意$2^{L-1}$可以超越整數範圍。

Medium: 給了一個字串$S$，並只給了幾種特定的操作，其操作形式只有三種。
(1) 在字串內刪除其中一個為$a$的字元，費用為$w_1$。
(2) 在字串內把其中一個為$a$的字元變成$b$，費用為$w_2$。
(3) 在字串加上一個為$a$的字元(可以在字串前後加上)，費用為$w_3$。

現給予$R$種互不相同的操作，問把$S$變成迴文的最少費用。

處理這類字串成問題通常是考慮動態規劃狀態$F(x, y)$，即最少把子字串$S_{x\cdots y-1}$修改成迴文的最小費用。

先考慮簡化版問題﹕允許任意操作，並且一律費用為$1$。那麼其狀態轉移方程可以簡單描述成
\[F(x, y) = \begin{cases} 0 & \text{if $y-x \le 1$} \\ F(x+1, y-1) & \text{if $S_x = S_{y-1}$} \\ \min(F(x+1, y), F(x, y-1)) + 1 & \text{otherwise}\end{cases}\]
但套在這道問題又是否可行呢？首先留意到並非任意操作都可行，所以狀態方程必須因應對應字元而再設計。其次是任意操作的費用不再單純是$1$，意味著若把上述方程的費用$1$寫成通用的$W_{S_x,S_y}$，那麼其意義不只限於單次操作使得$S_x$和$S_y$匹配，而是可以經過一系列操作令$W_{S_x,S_y}$最少化。先考慮$C_{a,b}$，即最少費用把字元$a$修改成字元$b$，然後$W_{a,b}$則可經如下公式求得
\[W_{a,b} = \min_{c}\{C_{a,c} + C_{b,c}\}\]
這引伸了另一個問題﹕如何求$C_{a,b}$？可以想像到的是最短路算法。但首先留意求算需要周全考慮所有操作﹕如果只考慮改變字元的話是不夠的，因為可能最小費用操作可以循這種方式獲得﹕修改$\rightarrow$刪除$\rightarrow$加入$\rightarrow$修改。可見刪除和加入這兩種一般難以用最短路方式描述的操作是可以出現在最小費用操作的任意位置中。解決這個問題的一種思路是﹕何不可以把這兩種操作歸約成修改操作？留意兩種操作可以這樣看的﹕
(1)刪除﹕把字元$a$修改成字元$\emptyset$。
(1)加入﹕把字元$\emptyset$修改成字元$a$。
因此我們只需把空字元$\emptyset$列為可考慮修改字元的話，那麼$C_{a,b}$即可以用最短路
\[C_{a,b} = \min_{c \in \{\text{`a', `b', $\cdots$ `z', $\emptyset$}\}}\{C_{a,c} + C_{c, b}\}\]
求得，因此亦得到$W_{a,b}$。現在重新考慮狀態轉移方程，留意因為費用不再全部都是$1$的關係，因此我們把簡化版的方程的$S_x = S_y$情況一併歸約至一般情況之中，即可得解決本題的方程，如下﹕
\[F(x, y) = \begin{cases} 0 & \text{if $y-x \le 1$} \\ \min(F(x+1, y), F(x, y-1)) + W_{S_x,S_y} & \text{otherwise}\end{cases}\]