2016年12月9日 星期五

農場例行賽 #16 官方解答

本周的題目其實在兩個月前就準備好了,原本要放在 10/9 那天的比賽,但由於這場比賽比較適合用 IOI 的給分方式,但卻研究不出 Codeforces 的 group contest 要如何轉換成 IOI 的給分方式,寄信問了 MikeMirzayanov 但他都不理我 Q_Q 於是就先把這套題擱著了。但這周呢,實在是沒空生新的題組,所以就勉強把這套題拿來用了 XD 希望大家能夠喜歡 >__<

Problem A - Apple Pen

小測資算是基本的 string 習題,讀入後把所有物件的組合有兩種順序湊在一起看看是否有其中一種等於 $T$,是的話就先把答案記錄下來,最後再輸出。細節請直接參考程式碼:


大測資似乎很容易讓大家走火入魔去使用 hash 或 trie 等比較厲害的東西,等仔細思考後可發現,我們並不需要任兩個物件都湊湊看,因為 $S_i$要碼是 $T$ 的前綴字串會後綴字串才有可能被和其他字串組出 $T$,所以對於每個 $S_i$ 只需要比較兩次而已,並開兩個表格 $pre$ 和 $suf$,分別記錄 $T$ 的某個長度的前綴或後綴是等於第幾項東西的名字。最後再枚舉 $T$ 的所有中切兩半的方法,試試看是否切出的兩段都是某個東西的名稱。

我的大測資程式碼如下:

Problem B - Two Swords Style

小測資的重點是給初學者練習位元運算或是 bitset 吧 XD 每個詢問都個別計算。對於單一詢問,只要枚舉兩把劍的組合,計算他們屬性的聯集是否包含任務所需的屬性集合,懂得運用位元運算或 bitset 就會變得很好寫 code,請直接參考程式碼,我的程式碼是使用 bitset:

中測資則可利用與集合有關的 DP 問題解它。一樣是每個詢問都個別計算,但這次對於單一詢問,我們只枚舉一把劍,希望能快速得知有多少劍與枚舉到的劍互補。

從這裡我們開始使用集合的相關術語和符號。首先把屬性編號為 $1 \sim m$,我們所討論的宇集就是 {$1, 2, \ldots, m$},$S_i$ 為第 $i$ 把劍所擁有的屬性集合,令 $M$ 為任務所需屬性的集合。所以我們想要快速知道的事情是:對於每個 $S_i$,有多少個 $S_j \subset M - S_j$ ( 減號表示 $M$ 和 $S_j$ 的差集,運算結果將包含所有在 $M$ 卻不在 $S_j$ 的元素 ) 。 實際上,這件事可以用 DP 以 $O(m \times 2^m)$ 的時間複雜度預處理 。我們用 $dp$[$x$][$T$] $=$ 滿足 $T$ 為 $S_i$ 子集且 $S_i$ 為 {$1,2, \ldots, x$} $\cup$ $T$ 的子集 的 $S_i$ 的個數,且dp[0][$T$] 就是 滿足 $S_i = T$ 的 $S_i$ 的個數。這樣的 DP 狀態會有以下關係式:

如果 $x$ 包含於 $T$, $dp$[$x$][$T$] $=$ $dp$[$x-1$][$T$] 否則 $dp$[$x$][$T$] = $dp$[$x-1$][$T$] $+$ $dp$[$x-1$][$T+{x}$]。

這個 dp 表格求出來後 dp[$m$][$T$] 就是 包含 $T$ 的 $S_i$ 的個數了。

再實作時可以發現,我們其實只要用 $O(2^m)$ 的記憶體就可以得到最終我們要的東西,詳情請以下程式碼:

現在來到了大測資,對 FWT ( Fast Walsh–Hadamard transform, 可參考此連結 ) 熟的人大概一看就知道大測資可以用 FWT 解掉了吧?( 賽中 AC 的三個人有兩個人是使用 FWT ),但若問題繼續推廣成問三刀流或四刀流呢?這時還能用 FWT 解嗎?就我的理解是不能啦,所以我寫在這裡的解法會是個甚至可以推廣到 $K$ 刀流 (可惜對於一筆測資 $K$ 必須是固定的),且是繼續使用上述中測資的解法的類似概念。

若我們能快速知道對於所有集合 $T$ ,有多少組 ($i$, $j$) 滿足 $i < j$ 且 $S_i \cup S_j = T$,那我們就可以利用中測資所說的方法求出答案了!但這似乎有沒那麼簡單?

再退而求其次,我們改求有多少組 ($i$, $j$) 滿足 $i < j$ 且 $S_i \cup S_j \subset T$,但這也沒那麼簡單的樣子,那我們就再退一步吧。

這次只求有多少 $S_i$ 滿足 $S_i \subset T$。現在這個問題就可以使用類似中測資的 DP 方式解了!這次則是用 $dp$[$m$][$T$] $=$ 滿足 $S_i$ 為 $T$ 子集且 $T$ - {$1,2, \ldots, x$} 為 $S_i$ 的子集 的 $S_i$ 的個數,轉移也將是 $O(1)$ 轉移,大家可以試著自己推推看~

剛剛退了那麼多步,我們終於要開始前進了!現在已知"有多少 $S_i$ 滿足 $S_i \subset T$",要推得"有多少組 ($i$, $j$) 滿足 $i < j$ 且 $S_i \cup S_j \subset T$",其實只要把取組合述就好了,也就是若有 $v$ 個 $S_i \subset T$ 那麼將有 $\frac{v \times (v-1)}{2}$ 個 ($i$, $j$) 滿足 $i < j$ 且 $S_i \cup S_j \subset T$。

接著,我們要從 $T$ 的 subset 的數量求回等於 $T$ 的數量,這個也只要把上上一步的運算全部倒回做就行了,其概念就像是 $A$ 加上 $B$ 後等於 $C$,那我們就只要用 $C$ - $B$ 就可以求回 $A$ 一樣!於是現在我們每一步都會做了!

關於所有細節請細細的品味以下程式碼 >__<

Problem C - Zekken Easy

小測資沒使用特別技巧的 DP 題,考驗看看你有沒有正確理解題意,有可能的 bug 諸如運算有沒有使用 long long 或有沒有注意到 $t = 0$ 時你的座標是在 $x = 0$。首先,把所有落葉按照落下時間排序,接著用 $dp$[$i$] 表示若有擊中第 $i$ 個落葉,在這之前至多可以擊中幾個,在計算 $dp$[$i$] 時,枚舉所有小於 $i$ 的 $j$並判斷若有擊中第 $j$ 個落葉,是否可以再繼續擊中第 $j$ 個落葉,若可以,則用 $dp$[$j$]$+1$ 去更新 $dp$[$i$] 的最大值。總時間複雜度是 $O(n^2)$。


中測資開始我們用圖片示意,先考慮 $d = 1$ 的情況如下,水平座標代表落葉落下的位置,垂直座標代表烙下的時間,綠色的點代表落葉們。每擊中一片落葉後下一片能擊中的落葉必須落在當前落葉左右各張開 $45$ 度的直角框框裡,看這張圖可能還不會有什麼啟發,現在我們施點魔法,把他向右旋轉 $45$ 度!
 於是現在變成了下面這張圖,有所啟發了嗎~這張圖顯示著:所有落葉都必須落在上個落葉的右上角。
我們可以發現,把圖向右旋轉 $45$ 度後,把所有落葉按照新的水平座標,垂直座標將呈現非遞減的關係,所以這題實際上就是 LIS 問題!所以解這題的步驟為:1) 計算旋轉每個落葉所對應的點在坐標系向右旋轉 $45$ 度以後的座標。 2)  拔掉所有不再第一象限的點。3) 按照水平座標把所有點排序。4) 求出 LIS。

至於大測資的差別只是紅色的虛線張的比較大而以,但我們只要把所有落葉的落下時間都乘以 $d$ 就變得和中測資一樣了。(也許對大部分的人來說中測資和大測資難度沒什麼差吧>__<)

這次直接附上大測資的程式碼:

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} 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。

以下是我的程式碼: