隨手coding筆記 by波路特石

原題連結： https://atcoder.jp/contests/arc058/tasks/arc058_d 前言 網路上的題解感覺都寫得不是很完整，而 Atcoder 自己的官解又是日文，但我個人又覺得這題官解過份精湛所以乾脆打算久違的來發一篇文加深印象（？ 天真做法 首先看完題目有一個天真做法如下： $$dp[i][j] := \text{前 }i\text{ 個字串組成長度 }j\text{ 的最小字典序字串}$$ 轉移的部份，每個 $dp[i][j]$ 可以直接轉移到 $dp[i+1][j]$。 此外，若 $dp[i][j]$ 有值，就可以在後面加上 $s_{i+1}$ 並轉移到 $dp[i][j + |s_{i+1}|]$。若該格已經有值了就取最小字典序的那個留著。 這樣光每一排就得存下至多 $O(K^2)$ 個字元，每次轉移也可能要比較 $K$ 次長度至多 $K$ 的字串，這樣無論是時間還是空間複雜度都是 $O(NK^2)$，顯然會 TLE + MLE。 我認為這題官解厲害的地方是他不打算直接改狀態，而是直接從優化下手，一般而言 dp 優化都會想從轉移速度、或是壓狀態開始優化，但直接在這題想要這樣做的話就會發現很難行得通。 巧妙的點就在於，官解打算先從壓空間開始。 空間優化 有一個很直觀的空間壓法就是在每個 $dp[i][j]$ 存下轉移來源和構造方法，這樣的話顯然能夠乾淨的將空間壓到 $O(NK)$，不過這個方法的轉移會變得很難優化，我自己在 virtual 中有嘗試這個思路但失敗了，甚至後來發現可能要用 rolling hash + 倍增才有辦法讓轉移變成 $O(\log N + \log K)$，又難寫又胖。 官解從「刪除無用答案」當成出發點，什麼叫無用答案呢？一個狀態 $dp[i][j]$ 存的答案無用代表他符合以下兩點其中之一： 1. 無法利用 $s_{i+1}\sim s_N$ 湊出長度為 $K-j$ 的字串。 2. 存在另一個有值、滿足 1. 的 $dp[i][j']$，使得「他的字典序嚴格比 $dp[i][j]$ 小」 不滿足 1. 就無用應該很顯然，但對於 2.，什麼叫嚴格小呢？舉個例子，字串「$aba$」就不嚴格小於「$ababa$」，因為有可能「$aba$」後面能接的字串太大了導致「$ababa$」反而勝出；而字串「$aa...