2016年12月3日 星期六

農場例行賽 #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} + 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。

以下是我的程式碼: