農場例行賽 #15 官方解答

本次的題目全部都是原創題，不過不保證其他地方沒有一模一樣的題目 >__< 像第一題這種東西就覺得出現好幾次也不奇怪？

= = =

A. Construct a Triangle!

這題按照 $N$ 的奇偶性討論答案，可以直接參考程式碼。證明如下：不妨假設三角形的三邊長由小到大分別為 $a, b, c$，面積非零的充要條件是 $a+b > c$，所以 $c < \frac{N}{2}$。且 $a > 0$ 是肯定的，故我們可以推得 $c - a \le$ floor$(\frac{N-1}{2}) - 1$，若 $N$ 是奇數有唯一的 $a, b, c$ 使得等式成立，偶數的話則會發現等式一定無法成立，於是退而求其次，構造出 $c - a = floor(\frac{N-1}{2}) - 2$ 的三角形。

我的程式碼如下：



B. Construct a Permutation!

這題想信大家的解法可能都不太一樣，我這裡就先給一個超難寫的解：有一種經典題是一要你算出有多少 permutation 滿足題目所給的所有不等式關係，這種經典題可以用 $O(N^2)$ dp 求出，而利用 dp 的過程可以 backtrack 出一組解。當然我自己不是這樣寫的啦，我的解請參考以下程式碼，相信直接看程式碼比我用說的還容易明白，正確性也很容易檢驗。

我的程式碼如下：



C. Construct Numbers

寫題解時發現這題標題不太合群...沒有驚嘆號 XD

不妨先假設我們構造出來的 $N$ 個數 $a_1, a_2, \ldots, a_N$ 滿足 $a_1\le a_2 \le \ldots \le a_N$。

在構造答案前，我們該思考的是：若固定$N, K1, V1, K2$ 的值，能夠造出答案的 $V2$ 的範圍是什麼？首先，我們來求 $V2$ 可能的最小值吧～

先想像 $K1 + K2 \le N$ 的 case，我們有 $a_1 + a_2 + \ldots + a_{K1} = V1$，而最大的 $K2$ 個數每個數都 $\le a_{K1}$，所以 $V2 \ge K2 \times a_{K1} \ge K2 \times ceil(\frac{V1}{K1})$，也就是說，我們把 $V1$ 均勻地分配給前 $K1$ 小的數，並讓剩下的數都等於 $a_{K1}$，就會構造出 $V2$ 值最小的數列，如果要使得後 $K2$ 個數的和變大，只要再增加 $a_N$ 的值就行了，於是我們就里完整的解決並且證明了 $K1 + K2 \le N$ 的 case。

若 $K1 + K2 > N$ 呢？有了前一個 case 的經驗，我們會猜測若存在答案，則平均的把 $V1$ 分配給前 $K1$ 個數也一定能用一樣的方法構造出答案。實際上這幾乎是對的，這裡就不證明為什麼了 >__< ，但要注意有一個例外：$K1 = N$ 時，雖然 $V2$ 的極小值發生的時候也可以用上述方法構造出來，但 $V2$ 更大的情形，就無法直接增加 $a_N$ 的值了，因為直接增加 $a_N$ 的值，前 $K1$ 項的和也會變大。相信大家 WA 那麼多次也是因為這個例外沒有好好處理。那我們要怎麼處理這個例外呢？其實改成這樣：增加 $a_N$ 的同時，也減少 $a_1$ 的值，若 $a_1$ 已變成 $1$，則繼續減少 $a_2$ 的值即可，依此類推，但若 $V2 > V1- (N - K2)$ 也是無解的，畢竟前 $N-K2$ 項的和至少就是 $N-K2$。細節請參考程式碼。

我的程式碼如下：



D. Construct a Walking Path!

令 $e_i$ 為小月經過第 $i$ 個據點和第 $i+1$ 個據點間的道路的次數 (從左到右或從右到左都算)。

這題若改成下腳踏上和上腳踏車的據點一樣，且上腳踏車的那次不列入計算的話，相信這題就會有很多人 AC 了。現在我們用 $e'_i$ 表示在這樣的狀況下，小月經過第 $i$ 個據點和第 $i+1$ 個據點間的道路的次數。因為題目改成這樣後，就會存在 $c_i \times 2 = e'_{i-1} + e'_i$ 這樣的等式( 因為一個據點每被經過一次，左邊和右邊共會長出兩條邊 )，並且因為 $e'_0 = 0$ ，於是 $e'_1 = c_1$, $e'_2 = c_2 - e'_1$, $e'_3 = c_3 - e'_2$，所以我們可以用遞推的方式求出所有 $e'_i$ 的值，若每條邊 (可以把據點間的路徑想像成圖論的邊) 經過的次數都大於零且 $e'_N = 0$，就一定可以使用找尤拉路徑的方式找出解了( 因為每個點的 degree 是偶數且連通 )。

現在回到原題，把起點 $s$ 和終點 $t$ 也考慮進去，將會發現，$c_i \times 2 = e_{i-1} + e_i$ 這個等式會變成 $c_i \times 2 = e_{i-1} + e_i + [ i == s ] + [ i == t ]$ ( 如果 $condition$ 成立，$[condition] = 1$，否則 $[condition] = 0$ )，再遞推一次可推得

$e_i = e'_i + [i \ge s] \times (-1)^{[(i-s)\ is\ even]} + [i \ge t] \times (-1)^{[(i-t)\ is\ odd]}$。

用文字來描述這個式子就是：從 $s$ 把 $e'_s$ 減 $1$，把 $e'_{s+1}$ 加 $1$，把 $e'_s{i+2}$ 減 $1$，...，直到 $e_N$。之後再對 $t$ 也做同樣的事。

有了這樣的觀察，我們就可以給出一個初步的 $O(N^3)$ 演算法，也就是枚舉 $s$ 和 $t$ 的值，求出所有 $e_i$ 後檢查合不合法，但這樣顯然不夠快解這題，實際上是存在 $O(N)$ 的做法。

$O(N)$ 的作法大概也是有千百種吧？希望大家先自己想想看，看有沒有和筆者的做法一樣>__<。

我的想法是，既然我們想要讓所有數字都大於零且 $e_N = 0$，那我們就先找到最左邊的不合法的數字，並用最大的 $s$ 使該數字變得合法，做完第一次後就再用 $t$ 做同樣的事一次就好了！若做完兩次後整個序列變得合法，那你就找到答案了，否則就是 Impossible。有個例外是，一剛開始全部都是合法的，那我們可以直接令 $s = N-1, y = N$，大家可以試著證證看我的作法到底是不是對的 XD(抱歉我懶的在這裡證明了 >__<) 這個做法程式碼非常乾淨，也許直接看我的程式碼能更快理解整個過程。

我的程式碼如下：



E. Construct Expressions!

最初在設計這題時，其實只有單筆詢問，也就是 $Q$ 永遠是 $1$ 但後來覺得這樣實在很難生出有鑑別度的測資，所以就改成多組詢問，於是，這題一不小心又被改得更難的樣子 XD

我先試著揣摩一下猜賽者看到這題會如是想： 這個題目感覺上，要好好做就是得使用 DP，可是也不太像存在 $O(N)$ 的 DP 方法，但用 $O(N^2)$ DP 肯定會 TLE 呀？難道是 greedy 嗎？可是純粹 greedy 就可解的話，這題還會被放在 pE 嘛？

我有猜中大家的想法嘛 >__<，先公布一下這題我預期的解法輪廓： $N$ 大到某種程度就一定能使用 greedy找到解，太小就使用 DP。

恩...總之先假設 $V$ 是偶數且 $V > 2 \times N$的 情況，這兩種情況顯然無解。

我相信對大家來說最直覺的 greedy 方法就是：初始時想所有運算都使用加號，之後先把盡量多連續的 $2$ 乘在一起直到再多乘一個 $2$ 總和就會超過 $V$，然後隔一個家號後再做一樣的事，如此重複下去直到總和真的變成 $V$ 為止。舉例來說 $N = 10, V = 32$。

step 1： $2+2+2+2+2+2+2+2+2+2 = 20$
step 2： $2\times2\times2\times2+2+2+2+2+2+2 = 28$
step 3： $2\times2\times2\times2+2\times2\times2+2+2+2 = 30$

step 4： $2\times2\times2\times2+2\times2\times2+2\times2\times2 = 32$

於是我們就成功用 greedy 得到答案了。並且 $2$ 也剛好用完。但很可惜這的 greedy 有時會雖然存在解卻找不到 ( 可以試著自己找找看這樣的例子，懶惰一點的話也可以用電腦找 )，但似乎能夠相信，當 $N$ 大到一定程度，總是能找到答案。若是在比賽，或者你可以亂個能否定找到答案的 $N$ 值分界線，但很可惜我是出題者沒有這樣的權利 Q_Q我一定要能夠證明這個分界線足夠低 ...

我們把 greedy 的每一步描述得更數學一點會變成：把 $k$ 個 $2$ 間的加號改成乘號，總和將會增加 $2^k - 2 \times k$。這樣來描述方法是否很有背包問題的感覺呢？於是原題就變成，我們可以用掉 $k$ 個 $2$ 得到的 cost 為 $2^k - 2 \times k$ 並且我們希望用掉不超過 $N$ 個 $2$，使得總 cost 恰為 $V - 2 \times N$。而 greedy 的過程就是從較大的 $k$ 開始嘗試。

再貪心的過程中，若我們某次使用了 $k$ 個 $2$ ，就代表在該次使用之前我們還需要得到的 cost 少於 $2^{k+1} - 2 \times (k+1)$，所以若連用了兩次 $k$ 個 $2$，就代表還需要的 cost 少於 $(2^{k+1} - 2 \times (k+1)) - (2 \times (2^k - 2 \times k)) = 2 \times (k-1)$ 並且我們知道 我們可以使用 $3$ 個 $2$ 能得到的 cost 為 $2$，所以若連續 $2$ 次 變出 $k$個連乘的 $2$，就只要至多再花 $3 \times k - 3$個 $2$ 就能得到我們所要的總 cost。，令第一個使用 兩次的 $k$ 值為 $u$，則 我們總共使用的 $2$ 的個數就不會超過 $(\sum_{i=u}^{59} i) + u + 3 \times u - 3$。而對於所有 $u$ ，這個式子的最大值是 $1777$。(這只是粗略估計，實際上在 $V \le 10^{18}$ 時能找出更小的 bound)

於是現在我們只考慮 $N \le 1777$ 的 case，前面有提到，這個問題和背包問題很像，可是背包問題並不能解決容量那麼大的背包呀，而且還得一次性的處理多組不同 $N$ 的詢問。

首先呢，如果你被我前面誤導，使用 $k$ 個 $2$ 的 cost 是 $2^k - 2 \times k$ 的概念想下去，就會想到天荒地老也想不到吧，這夠結構有兩的缺點，第一，對於不同 $N$ 要得到的總 cost 不一樣。第二， $cost$的值長得不漂亮。

所以我們換個理解方式：我們可以使用 $k$ 個 $2$，得到 $2^k$ 的 cost，並且我們的目的是恰用 $N$ 個 $2$ 得到恰為 $V$ 的 cost。這樣子感覺起來就有機會一次性處理不同的 $N$ 值了，但仍沒有解決關鍵的 $V$ 很大的問題。

所有 cost 都是二的冪次方，不覺得這個性質很有機會可以利用嗎？首先為了湊到 $V$ 所使用 單獨一個 $2$ 的次數的奇偶性 (更準確地說，其實是 $\mod 4$ 後同餘 $0$  或 $2$但之後類似的東西我一律都稱為奇偶性。) 一定是固定的！所以我們可以先決定單獨一個 $2$ 要使用幾次，決定並使用完後，我們就可以把現在已經有的 cost、使用不同個數的 $2$ 的 cost 以及 $V$ 值都除以 $2$(整數除法)，之後再決定要使用幾次兩個 $2$ 乘在一起，接著決定連續三個 $2$ 乘在一起的次數，依此類推，且 cost 永遠是 $2$。這樣的過程將會持續到你能已有 $cost = V$ 。由於你只有 $N$ 個 $2$ 可使用，所以在任何時刻，現在已有的 cost 值都不會超過 $2 \times N$。

於是我們列的 DP 狀態將是 dp[正在嘗試連乘 $k$ 個 $2$][已經使用 $N$ 個 $2$][現在已有的 cost]

陣列的 size 會是 60 * 1777 * 1777 左右。

走訪 dp table 時，每個狀態都至多只有兩種可能的選擇：一、花 2的 cost 再增加連續 $k$ 個 $2$。 二、若已有 cost 和 $V$ 的奇偶性一樣，那麼就可以改成嘗試 $(k+1)$ 個 $2$ ，並把已有 cost 及 $V$ 值都除以 $2$。 於是，此問題 DP 的複雜度會是 $O( log^5 V)$ ( 因為實際上 1777 來自 $log^2 V$，而 $60$ 是 $log V$ )。

以上是以解單一的 $N$來做講解的，擴展成多個 $N$ 做法並不會差太多，詳情參考程式碼。(可能要注意一下，我的程式碼再最初就先把 $V$ 和 所有 cost 都除以 $2$ 了，所以每次的 cost 會變為 $1$)

最後大家還要注意的一點是，這提使用的記憶體諒還蠻大的，而且你必須回溯出一個解， dp 的狀態不能用完即丟，幸運的是，無論是 一個為值有沒有被走訪過或是soutce的來源都可以只以一個bit表示，於是可以用 bitset 輕鬆搞定，若沒使用 bitset 就會 MLE。

以下是我的程式碼：