GKS 2021 Round B

之前我提過這系列解題筆記原本是要在 GKS Round A 時就開始寫的，既然 Round B 可以上場了那就來寫吧。

先提一下：接下來的 GKS 我不會全部參加；現在已經知道的是至少七月的 Round D 舉行的時間正好我會比較忙，所以那一回確定不參加。其他回就看我那個時間有沒有空了。

分數截圖以下開始有雷。(對，這張截圖是在結束前半小時時截的 XD 賽後的名次是 164 名，果然 Q4 +4 太傷了……)

Q1. Increasing Substring

果然是 GKS 的難度，第一題是送分題所以就不多說了，只提一個是這題的做法是 DP 的基本型。

Q3. Consecutive Primes

Q2 由於等一下會提的原因決定晚點寫，所以先跳來寫 Q3。

這題比較有問題的其實是值域估計。大測資有到 10¹⁸ 的大小，因此我們會需要判斷大約是 10⁹ 大小的數是否為質數，因此需要建立至少到三萬多的質數表；比較麻煩的是這裡不能寫死一個 \(\lfloor\sqrt{10^9}\rfloor=31622\)的上限，因為可能會需要判斷稍微大於 10⁹ 的數的的質數性。這有兩個辦法：

1. 就直接任意定一個大不少的範圍建表，例如十萬；
2. 算出我們可能會求到多大的質數，用那個推上限。由於下面計算，我們頂多會往後找 10⁹ 之後的一個質數；這一個質數是 \(10^9+7\) (各位刷過不少題目的一定常常看過這個數 XD)，所以開根號的估計值其實沒差很多，因此 31622 的上限事實上是可以沿用的。

實際計算則相對簡單：在輸入值 Z 的平方根附近找比它大的一個質數和比它小的兩個質數，答案一定是這三個質數之間的兩個乘積之一。找的方法也不用太麻煩，一個一個找過去判斷是否質數就好了。質數定理告訴我們平均只要試 \(O(\log n)\) 個數就能找到 \(n\) 附近的下一個質數，因此這裡的平均詢問是否質數次數是 \(O(\log n)\)，每次詢問也花 \(O(\log n)\) 次除法，所以一個回答的時間是 \(O((\log n)^2)\)，代入 \(n=\sqrt{Z}\) 即是 \(O((\log Z)^2)\)，很容易就能完成。

Q4. Truck Delivery

簡述一下題目是這樣的：

有一個 N 個點的樹形圖，每個邊上有個「載重限制」跟「花費」；現在問 Q 個問題，每個問題是給定樹上一點和一個重量，求由這一點到 1 號點的簡單路徑中，所有比這個重量大的載重限制的邊上的花費，其最大公因數值。

這個敘述裡最顯眼的就是這個「最大公因數」了－－但是其實這只是拿來唬你的東西，這題真正的難關是在其他的細節裡。就先來簡單考慮一下大致上這題要怎麼做好了：

• 所有問題的路線終點是一樣的，都是 1 號點，所以其實可以反過來，從 1 號點出發，求出各個點要往哪走才會走到 1 號點；
• 每個問題一進來，就沿著紀錄下來的路線邊走邊問邊整理即可。

這樣差不多就能過小測資了，但大測資會在這裡送你一個 TLE。問題在於，這個做法每個問題要花 \(O(N)\) 的時間回答，所以 Q 個問題總計要花 \(O(QN)\) 時間。解決這個問題需要拿空間換時間，也就是我們需要多算一點東西記下來，問題來了就可以花少於 \(O(N)\) 的時間回答。

既然問題在每次要花 \(O(N)\) 步才能求完，那就把這 \(O(N)\) 步先算完吧！於是每個點額外紀錄從這裡出發多重的貨物的最大公因數多少。貨物重量最大雖然是 \(2\times10^5\)，但我們不需要記下每個重量：因為路線有限長的關係，只需要記多重到多重結果是多少即可；然後因為這個重量範圍是連續的，我們甚至不需要記上界，只要記下界就好。因此每個點紀錄的東西就會變成類似：重量 0 起結果為 0，重量 2 起結果為 4，重量 6 起結果為 2，等等這樣的結果。更新的時候二分搜尋找到所要的目標，把那個範圍切開，更新所有比它重的紀錄就行了；例如來了一個重量限制 1 費用 5 的，那就把 0~2 這一塊切開，1~2、2~6、6~∞ 分別和 5 做最大公因數更新就行了。

－－然後就會吃一個 MLE。(倒) 可以知道，這樣子紀錄的資料量最多是所有點到 1 號點的簡單路徑長度和，因為某個長度的路徑最多有這麼多分段點，每個分段點都要有一個紀錄。那麼當所有路徑串成一串時，這個路徑長度和就是 \(O(N^2)\)，再算上要能二分搜插入的資料結構很容易就爆炸了。

怎麼辦？意外地，這裡我們需要回到最一開始題目裡那個最顯眼的目標：求最大公因數。如果題目是問費用和那就完全沒輒，但最大公因數不一樣：因為所求必須是給定費用的最大公因數，很有機會在更新時好幾個區間的結果能夠合併在一起。上面舉的例子就是這樣：1~2 更新成 5 了沒錯，但 2~6 和 6~∞ 都更新成了 1，因此可以合併成 2~∞ 結果為 1。這樣的合併如果問的是費用和那就完全不可能發生。¹

Q2. Longest Progression

這裡我先提一下我後半場的解題順序。在 Q1 和 Q3 做完之後我其實是先做 Q4，主要原因是一下子沒有很明確的 Q2 解法，但 Q4 已經有了上面那一節的前半部份的想法了。寫完之後上傳時才回頭來好好想了一下 Q2 的做法，寫了一個半解傳上去；這時 Q4 的那個上傳才回報上段前半提到的 TLE，不過既然 Q2 這邊已經有了一半想法，認真思考了一會總算是知道要怎麼改了，所以改好上傳過了之後這才回去把 Q4 補完的。

為什麼一開始沒有想法？主要是沒有抓住「要改哪一個」的問題。一個很明顯的點是，要改就要想辦法把兩個等差數列給接在一起：參考輸入的第二組是一種 (把兩個 5 串給接起來)，但主要是像 3 4 5 6 0 8 9 10 11 這種，把 0 改成 7 接起兩個等差數列這種狀況。因此很自然的會去紀錄「到哪裡的等差數列長度」－－這個操作其實我們在 Q1 就已經實作過一次了，所以就拿來用吧。(這就是為什麼我特別在上面 Q1 那裡提 DP，因為同一個 DP 可以用在這一題上)

那麼問題來了：要怎麼接？並不是每一組輸入都能把兩串數列接起來的。我在這裡稍微花了點時間確認分類，整理出來的有這些情形：

• 延伸：例如參考輸入第三組。這對任何已有的等差數列都能用，只要有空間給它延伸就行了。
• 數列跨過改動的數接上另一個數列：這是上面提的接數列。
• 數列跨過改動的數接上一個數：這是在兩邊的數列的公差接不起來，只有首項能接的時候；例如 4 5 6 0 8 10 這樣。

於是我寫一半的做法即是以已知數列為主，嘗試往前接看能不能接到前面其他數列。雖然自認寫起來沒問題，但可能是中間哪個條件沒確認好，傳上去吃了一個 WA……。再認真想了想之後才想到說：我為什麼要去分析數列，直接考慮我改這個位置的數能夠接多長就好啦。所以最後通過的做法是：

• 對不是中間的位置，先把這個位置兩邊兩個數給接起來。如果無法用整數接就不管這個位置了。
• 然後檢查這樣接起來之後兩邊原有的等差數列能不能連起來。為此，上面提到的 DP 正反兩個方向我都先各做一次存起來。
• 能連起來的才來計算總長度，找出最大值。
• 延伸的狀況怎麼辦？因為延伸對任何已有的等差數列都能用，所以在 DP 做完之後就先找出最長數列長度加一當基底，然後才做上面。這也是為什麼上面可以直接考慮兩邊接起來的狀況，因為只接一邊代表這是個延伸，我們已經考慮完了；如果中間接起來了但兩邊的已有等差數列都接不上也不用處理，因為這樣會得到一個長度 3 數列，但這裡最長數列長度加一至少是 3。

時間複雜度是輕鬆通過的 \(O(N)\)。

總結

其實這場我一開始以為是週日晚上十一點開賽。(爆) 當初在我的行事曆上記時間時忘記開 UTC+8 了，所以記到了 UTC 時間；週日晚上要準備開場時才發現搞錯了。於是半夜摸魚寫另一篇文章寫了一個晚上之後早上七點開賽，腦袋有點卡卡了所以才會在 Q2 這種題目卡關…….。

然後還有一件這三場下來注意到的事：最近的題目越來越喜歡打破 2³² 的範圍了……包含這一場，我其實好幾次送上去 WA 的原因是忘記一些值能夠超過這個範圍所以用了 32-bit 的 int 來裝。嘛還好現在已經不是十五年前那種連 long long 都要測能不能用的時代，int64_t 在各大編譯器都已經支援了，加上 C++ 輸出不用寫格式字串所以用起來比以前方便很多了。

下一場五月中的 GCJ R2 再見～

註腳

1. 事實上由於小於等於 \(10^{18}\) 的最大的高合成數是 74,801,040,398,884,800，其有 64,512 個因數，和我們的 \(N\) 相當，因此測資其實是可以很過份地全部出這個高合成數的因數；好在這不是 GCJ，沒有這麼過份的測資存在 (笑) 這題的官方題解是用了線段樹做離線查詢，詳情就自行參考官方題解吧；用線段樹的話即使題目是問費用和也能輕鬆求出。 ↩︎