因為各種原因，今天是在老家裡參戰，那 11am ~ 2pm 這段時間硬是卡了一個午飯時間就有點微妙了。還好中餐沒有耽誤到多少 (正好拿來讓我想題目)，所以參戰結果還算滿意。
這次成績是 95 名，三四兩題的大測資都 TLE；不過這兩題看起來就是這場的魔王了，所以雖然只拿 62 分，但名次還有在前百。分數截圖以下有雷。
Q1. Transform the String
這題沒什麼難度，就很簡單的看每個字移到哪個位置最近而已。考慮到輸入會很長的狀況，因此就先預處理一次，算好所有 26 個字母各要多少次變動到點，然後字串進來就掃一邊加過去就好。
Q2. Painter
如果能看出三原色其實是個別獨立的話，這題就很簡單了；對三原色去求出連續格子的個數。為了不要被判斷式絆住，輸入的字串先轉成 0~7 的數字之後，用 bitmask 分開掃。
Q3. Silly Substitutions
這題絆住我有點大，原本是有想做大測資的但包含午飯時間想了想之後發現堆疊法有好多特殊狀況要處理。
如果只要過小測資的話，最簡單的做法大概只要二十行左右就能搞定，直接呼叫一般的字串處理函數就可以了；問題在於這種函數呼叫單次時間是 \(O(n)\)，全部最多的操作數也是 \(O(n)\)，總計就是 \(O(n^2)\)。
我所謂的堆疊法就是數字進來時就直接往前結算，處理完之後再看下一個數字。主要理由是，幾乎每個數字都強烈偏好和前面一起結算 (例如：123 的 2 會先跟 1 結算，取代成 33，而不會向後找 23 取代變成 14)，因此先進來的就能先處理。
問題就在上面的「幾乎」兩個字：最容易想到的問題是 0，比起 90 它更喜歡 01，所以 901 會變成 92 而不是 11；不過不只 0 有這問題：89101 的中間的 1，它應該要跟後面 01 取代成的 2 一起變成 3，所以 89101 應該要變成 03，但如果中間 1 先和前面 89 取代成的 0 變成 2 的話，結果就是 22。
題解裡提到的串列法其實也有想到，但因為不太好確認要怎麼維護想要取代的位置所以就暫時放下了。最後是在開賽兩小時後決定算了去做 Q4，把只過小測資的解送了上去。
Q4. Dependent Events
這題看起來很可怕，但其實可以說這題已經把算式寫給你看了。基本概念很簡單：三個事件 \(A, B, C\) 如果在同一條依賴鏈上的話，我們有：\[P(C|A)=P(C|B)P(B|A)+P(C|B^c)P(B^c|A)\] 這就是題目中間的 \(0.2\times0.8+0.4\times0.2=0.24\) 在算給你看的。
至於第一題的 3 5 這種測資又如何？它們的最小共同祖先 (LCA) 是事件 1，在事件 1 給定發不發生之後兩者是獨立的，因此我們有 \[\begin{aligned}P(E_3\cap E_5)&=P(E_3\cap E_5|E_1)P(E_1)+P(E_3\cap E_5|E_1^c)P(E_1^c)\\&=(P(E_3|E_1)\times P(E_5|E_1))P(E_1)+(P(E_3|E_1^c)\times P(E_5|E_1^c))P(E_1^c)\end{aligned}\] 中間的四個條件機率就能用和上面一樣的算法求出來。
另外一個可怕的東西是這題的奇怪輸出格式：它要求將一個分數 \(\frac{p}{q}\) 表示成一個整數 \(R\)，使得 \(R\times q\equiv p \pmod{10^9+7}\)。所以我們好像需要用分數算出答案來之後，再用歐基里德演算法求乘法逆……看起來就是一陣麻煩事。這裡的關鍵是注意到，因為給定的分數是以百萬分之一為單位，所以所有的分母都只會有 2 和 5 的因數，因此我們可以直接把給定的機率值就變成這種 R 表示法，然後所有的計算全部都用這種表示法進行，最後出來的結果也就自動是這種型式了。例如：\[\begin{aligned}0.2=\frac{200,000}{1,000,000}=\frac{1}{5}&\equiv400,000,003\pmod{10^9+7}\\
0.8=1-0.2\equiv1-400,000,003&\equiv600,000,005\pmod{10^9+7}\\
0.4=2*0.2\equiv2*400,000,003&\equiv800,000,006\pmod{10^9+7}\end{aligned}\] 這樣上面的 \(0.2\times0.8+0.4\times0.2=0.24\) 就變成：\[\begin{aligned}&400,000,003\times600,000,005+800,000,006\times400,000,003\\=&240,000,003,800,000,015+320,000,004,800,000,018\\\equiv&120,000,001+560,000,004\\=&680,000,005\pmod{10^9+7}\\0.24=&\frac{6}{25}\equiv6\times280,000,002\\=&1,680,000012\equiv680,000,005\pmod{10^9+7}\end{aligned}\] 確實是求出所要答案的表示了。
最後一個小時的時間整理好這個算法再把它直接寫成程式就差不多用完了 (我是在截止前四分鐘上傳的，LCA 寫的是最簡單的 \(O(n)\) 算法)，所以很容易想像地大測資同樣 TLE 了。要解決這個 TLE，注意到最小共同祖先的計算跟機率計算會在同樣的樹分支上跑兩次，因此可以把 LCA 更好的算法 (預處理 \(O(n\log n)\)，查詢 \(O(\log n)\)) 當中機率部份對應的計算也先算出來，這樣跑一次樹就能一口氣直接求出所求來。
小結
翻了一下之後的名次才嚇一跳：做完 Q3 兩個測資但 Q4 沒做的 60 分是前 225 名……。算是果斷放棄 Q3 大的回報吧。
那麼今年的 Kickstart 就到此為止。明年……要看狀況，之後有可能無法參賽，不過現在八字也都還沒一撇所以就還是別多說吧。