GKS 2021 Round C

最近睡眠時間有點囧，晚上起來的時間讓開賽時腦袋還是一半睡著的狀態所以出了好些個簡單失誤吃了不少 attempt…還好這是 GKS 所以影響並不大就是了。

最終結果是做完前三題，第四題在賽後也花了另外的三個半小時寫完了。

分數截圖以下開始有雷。

Q1. Smaller Strings

仔細想就知道這題是 K 進位計數題。給定的字串只不過是 (補零到) N 位的 K 進位數字，所以對稱字串數就切一半轉成十進位就是答案了。這裡的 +1 嘗試是……忘了 10⁹+7 乘上 N 會溢位。(倒)

Q2. Alien Generator

我們有以下的式子：
$$G=\sum_{i=x+1}^{y} i=\left(\sum_{i=1}^y i\right)-\left(\sum_{i=1}^x i\right)=\frac{y^2+y}2-\frac{x^2-x}2=\frac12(y+x+1)(y-x)$$
因此總數就是把 \(2G\) 拆成兩個數乘積使上式的 \(x,y\) 有整數解。易知 \(y+x+1\) 和 \(y-x\) 需要一奇一偶，因此把 \(2G\) 所有的 2 的因數拿出來，再拆成兩部份，然後把全部的 2 因數貼給其中一邊；\(x\geq0\) 的條件使得一定有 \(y+x+1>y-x\)，因此拆成兩部份之後，2 貼給特定一邊可以得到一種解，因此解的個數就是 \(2G\) 移除所有 2 的質因數後，剩下的數的因數個數。題目要的 \(K\) 值就是 \(x+1\)。

例如題目的第二組 \(G=125\)，\(2G\) 移除所有 2 的質因數之後仍然是 125，其因數有 1, 5, 25, 125 四個。因此拆分方式就有：

• \((1, 125\times2)\)：\(y+x+1=250, y-x=1\Rightarrow y=125,x=124\Rightarrow K=125\)
• \((5,25\times2)\)：\(y+x+1=50, y-x=5\Rightarrow y=27, x=22\Rightarrow K=23\)
• \((25, 5\times2)\)：\(y+x+1=25, y-x=10\Rightarrow y=17, x=7\Rightarrow K=8\)
• \((125, 1\times2)\)：\(y+x+1=125, y-x=2\Rightarrow y=63, x=61\Rightarrow K=62\)

這即是題目給的四組解。

然後這裡的 +2 嘗試是……一個忘記為平方數加上等號，一個則還是溢位 (輸入最大到 10¹²)。(orz)

Q3. Rock Paper Scissors

到這裡開賽約莫半小時，腦袋比較清楚一點了，所以在看完後兩題之後決定出去買晚餐的同時來思考這一題。

簡單估計一下給定的目標。容易發現我們可以把得分簡化成：贏得一分，平手得 1、1/2、1/10、或 0 分，然後再乘上實際贏的得分來得到最後得分。由於所有測資平均下來每次贏的平均得分是 500，因此給定的目標 X 除以 500 即可轉化為簡化版的得分。三組測資分別對應 29.2、31、32.8 分。

不過也許也是因為單純只有想的關係，一開始掉進了一個很大的誤區：或許可以經由限制自己的出的拳種來強迫對方出不利拳種。這可能是被範例測資的開頭給誤導了吧：範例第一拳出石頭，因此對方的第二拳必定是布，因此自己第二拳出剪刀即可確實獲勝。然後我就在思考到底要怎麼調整兩拳的比例給自己優勢。

在考慮了半天沒有一個好結論的時候決定就定一個簡單一點的策略下去寫程式來試……結果平均最好的分數是 23.7 分。詳細策略就不提了，不過這種爛分數連第一組測資都過不了……

不過，也是因為這次實際下去寫程式才讓我注意到：這題並不需要提前決定什麼策略也可以直接做。很容易看到不管是什麼策略，在計算最佳步驟時一定符合 DP 結構 (固定已出拳的數量，出什麼拳可以由少掉該拳的最佳結果進行比較而得)，因此不需要提前設定什麼策略，直接利用這個 DP 結構下去跑就行了。

也就是說，這題是個包裝的很精美的簡單 DP 題。時間複雜度可以這麼估計：總共至多 N 拳的已出拳數量的種類數是 \(C^{N+3}_3=O(N^3)\)，每一格比較三種拳哪一個能得到最好的結果，所以時間是 \(O(N^3)\)；題目只有四種不同的 E/W 比例，所以甚至可以先把四種比例的最佳解都算出來 (容易看到比例相同的輸入最佳解也會相同)，題目給什麼就丟什麼出去就好了。

我 DP 出來的結果，四種比例的簡化分數分別是：E/W=1 得 41.64 分、E/W=1/2 得 33.34 分、E/W=1/10 得 29.15 分、E/W=0 得 28.47 分，因此全部四種狀態等比例的平均值是 33.15 分，輕鬆超過了題目要求的 32.8 分的目標。

Q4. Binary Operator

這題之所以我連在賽後都決定想要把它寫出來的原因是：這題明擺著給你看就是個語法樹操作題，算是我為數不多的強項之一。曾經在我大學出國比 ACM-ICPC 的時候，2009 年的首爾站 pG 正是一個語法樹題 (那題簡單的說是：給你一個簡化版的 C struct 宣告及對齊值，求出該 struct 佔的空間)，那一次我在賽中電腦閒著的時候就佔來寫這一題，最終拿到了這題的首殺 XD 印象沒錯的話事後看成績表好像全場連我們隊只有兩隊還三隊有解出這一題的樣子。

這一題沒有像那題 ACM 一樣可怕，因為給你的輸入字串甚至幫你完全括號，也就是我們可以簡單判斷這是不是式子，是式子的話運算子在哪裡；但這題的重點其實是語法樹的操作，因為就連小測資都會需要對式子進行交換律、結合律、分配律的操作，大測資甚至還需要合併同類項；這如果沒有一個好的資料結構的話會發覺非常難下手操作。題解裡對於小測資的化簡是利用一個四元組 (A,B,C,D) 表示 (A#B)*C+D，利用這個表示法的話交換律和結合律自動適用，分配律則只要簡單地對 C 和 D 做運算即可。

我這一題本來就是打算要一口氣寫全部的，所以架構一開始就不是這種簡單的定式，而是比較通用的多項式結構，不過細節倒也是經過了兩三次的改動就是。最終通過的架構是這樣的：

• 輸人的字串將它轉成類似題解裡提的那種語法樹，然後就直接把式子展開。
  • 基本單位是 vector<乘項>，表示這些乘項的和；這就是我上面提到的「多項式」。
  • 兩個這東西的 # 運算就簡單地把兩者各自轉成字串，連起來當做跟 x y 這種東西一樣的「變數」。這個會變成乘項的變數單位；每個乘項其實就是一個 multiset 收集這一項的所有變數名，加上一個常數表示係數。
  • 兩個這東西相加就進行同類項判定加起來。有了上面的 multiset，同類項就直接比較兩個 multiset 是否相等即可。
  • 兩個這東西的乘法就簡單地進行分配律全部乘開，得到一堆乘項再加起來，同樣進行同類項判定。
  • 上面這些處理會對 0 項特別操作：0 加任何東西都不變，乘任何東西都會變成 0。
• 處理完之後直接轉成字串。為了保證轉成的字串唯一，額外做了這些處理：
  • 多項式把每個乘項各自字串化，用字串排序後再用 '+' 連起來；
  • 而乘項的字串化則直接使用 multiset 幫忙排的順序，把變數名用 '*' 連起來；
  • # 運算的字串化已經在上面描述了，各自遞迴地應用這裡描述的乘項和字串化。
  • 這樣做雖然類似的式子會有不同的同類項排序順序，但至少它們不同；因此我們只要簡單的比對字串是否相同即可判斷是否是一樣的式子了。
• 另外，如同範例測資的第三組所暗示的，這題的常數會需要大數，好在只有加和乘所以寫起來還算簡單。

由於每個式子最多只有 100 個字元長，結構的總長度並不會太長；題解裡提到的分配律地獄輸入：

((0#1)+1)*((0#2)+1)*((0#3)+1)*…

仔細算一算就會發現計入完全括號後最多只會有八個加項相乘，也就是同類項至多只有 256 種，所以甚至連同類項判定都不需要額外資料結構，把所有項線性地掃過一次都是足夠的；而輸入的式子最多也只有 100 個，因此判定式子是否相等也可以線性地掃過一次 (而且很大機率兩個字串長度不同，所以判定不同的速度幾乎都很快)。我送通過的程式裡的常數計算甚至全部都是十進位大數，但就連這樣的計算量都是能夠通過測試的。

這裡可以也提一下題解裡提到的另類做法。這其實是一個更廣一點的概念的應用：兩個 (有限的) 多項式如果它們不恆等，則它們取值相同的地方只會是相對很小很小的一部份。因此如果我們將變數隨機取值的話，有很大機率會把不同的多項式對應到不同的值，就能藉此判斷兩者是否 (有很高的機會) 不恆等。同樣概念的其他應用還有使用在電腦對局的 Zobrist Hashing，它將局面化成了各項要素的集合，然後將要素隨機取值，代入總集的線性運算 (多半是 XOR) 當中得到這個局面的雜湊值；根據類似的理由，不同的局面因為具有的要素不同，線性運算的結果有很大機率會是不同的雜湊值，就能用很少量的計算去快速判斷兩個局面是相同或是不同，進而可以為其建立雜湊表格。

總結

這次的題目原本以為只有兩題簡單，在深入思考以及實際寫程式之後才注意到原來第三題的核心也非常簡單，只是被包裝得很精美而已。第四題則很有趣：正規路線其實不好做，但可以取巧得到一個高機率正確的做法。

如同之前提到的，下一回七月初的 GKS Round D 我有事無法參加，Round E 就要到三個月之後的八月底了。