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

以下是我的程式碼:


2016年11月26日 星期六

農場例行賽 #14 官方解答

本次農場例行賽的其中兩題是近期 Atcoder 題目改變讀入限制條件,另三題則是系列題,這次我們不按照題號,先從 Atcoder 改編的題目講起吧。

= = =

Problem B - Write a Special Judge!

這題是從 AGC007 - Shik and Stone 改編,原題是我自己的原創題,兩題的差別只在於 Input 是否為合法的 path。其實原題最初的版本就是大家現在看到的題目,但是 Atcoder 的審題者覺得不夠簡單所以才增加 Input 限制條件,因為加了以後就只要判斷路徑經過的格子數是不是 $n + m - 1$ 就行了。(可以想想看為什麼這題不能這樣解)

雖然現在不能直接數 '#' 字元的個數來判斷答案,但相信這題仍存在各種解法,這裡給出一個筆者認為挺好理解及寫程式碼的作法:先從左到右,再從上到下遍歷所有格子,每遇到一個新的 '#' 字元就檢查是否在上一個 '#' 字元的右邊或下面,並要確定第一個和最後一個 '#' 字元的位置分別是左上角和右下角。

額外聊一下,這題測試者在驗題時,連兩次雖然過了所有測資,但他的程式碼其實都還是錯的,讓我有機會再加強測資,非常感謝測試者屢敗屢戰的精神!

我的程式碼如下:


Problem D - Edit Sequence

這題是從 ARC063 - An Invisible Hand 改編,兩題的差別在於新題把敘述大量簡化以及 Input 的數列變得可出現重複數字。不瞞大家說會有這題的出現其實是因為該場比賽我沒有看到不會有重複的數字這個條件 XD (該場比賽我對許多人都那麼快 AC 該題感到不可置信 ... 賽後在開別人的程式碼來看才發現我漏掉條件了)

首先,我們令 $f(a) = h$。要解這題,直覺的想法是:先把造成 $f(a) = h$ 的數字們找出來,試著改變他們當中的一些數使 $f(a)$ 變小。

舉個例:當 $a$ = [3,5,3,3,5,2,3,4,3,3,2,4,1,2,3],此時 $h=2$,現在我們把與 $h = 2$ 有關的數字留下來如右:[3,5,3,3,5,2, ,4, , , 2,4,1, ,3],可以發現我們能把留下來的數字分成兩兩部相交的區塊如:[3,5,3,3,5][2,4,2,4][1,3],每個區塊只包含兩個不同的值,且愈右邊的區塊較小的數的值是嚴格遞減,分完區塊後,只要把每個區塊分成兩半(其中一個可以是空的),左半邊都改成區塊較大的那個值,右半邊都改為區塊較小的那個值,如:[5,5,3,3,3][4,4,2,2],[3,3]。經過這樣操作, $f(a)$ 的值就變小了!以上所用到的計算或操作都可以使用簡單的 dp  或記數來做到 $O(n)$,細節請參考程式碼。

在 Codeforces 上,有人提出了利用 matching 和 maximum flow 的關係,最後用貪心的方法解上述分完好多個小區塊地之後的部分。連結請點我

我的程式碼如下:





Problem A - Score Distribution 1

這題是系列題的第一題,不妨假設 $p_1 \le p_2 \le \ldots \le p_N$。由於選 $x$ 題的總得分的最小可能值就是 $\sum_{i=1}^x p_i$,最大可能值則是 $\sum_{i=N-x+1}^N p_i$,所以我們只要讓 $i$ 從 $1$ 到 $N-1$ 依序檢查 $i+1$ 題的最小題分和是否嚴格大於 $i$ 題的最大題分和就行了。當然,絕對不可以傻傻地每次從重新把 $i$ 個數的核都重新計算一次,必須有效率的計算。

我的程式碼如下:


Problem C - Score Distribution 2

這題是系列題的第二題。以下都假設 $p_1 \le p_2 \le \ldots \le p_N$。

只看範例測資猜答案的話,也許你會猜做法是二分搜出最小的滿足條件的連續 $N$ 個數,但非常抱歉,我不是這麼好心的出題者 >__<,若使用這一類的方法,找出來的數列數值可能超過 $10^9$,但其實還是有辦法找到在範圍內的其他答案的。

在解這題之前,我們來證明此系列題的一個重要的性質:若存在 $i+1$ 題的題分和小於或等於某 $i$ 題的題分和,我們就稱這個 $i$ 是 bad。若已知 $i$ 是 bad,那麼所有大於 $i$ 但不超過$(N-1)/2$ (本篇提到的除法都是整數除法) 的 $j$,也一定是 bad。

證明:因為 $i$ 是 bad 等價於 $S_i = \sum_{j=1}^{i+1} p_j - \sum_{j=N-i+1}^N p_j \le 0$,且不難發現 S_i 是個先遞減再遞增的數列,且此數列最小值一定是 $S_{(N-1)/2}$。(以後我們稱$S_{(N-1)/2}$為該數列的判別式,記做 $\Delta(p)$)

有了以上性質,首先我們可以知道,若測資的 $y > (N-1)/2$,答案一定是 Impossible。接著我們也知道 $S_y \le 0$ 且 $S_{y-1} > 0$。

現在我們只考慮數列 $p$ 只由兩種數值組成,且前 $(N+1)/2$ 個數一樣都是 $v1$,後 $N/2$ 個數一樣都是 $v2$。

於是我們就可以列出兩個不等式: $v1 \times y> v2 \times (y-1)$ 及 $v1 \times (y+1) \le v2 \times y$。我們只要另 $v1 = y$、 $v2 = y+1$ 就可以同時滿足這兩個不等式了!

我的程式碼如下:


Problem E - Score Distribution 3

這題是系列題的第三題。以下都假設 $p_1 \le p_2 \le \ldots \le p_N$。

我們稱 $p$ 的一個子序列 $q$: $q_1 = p_{k_1}, q_2 = p_{k_2}, \ldots, q_m = p_{k_m}$ 是 good ($k_1 < k_2 \ldots < k_m$),若且為若此子序列的分數們滿足小月的要求。

首先,我們會發現,若保留此 good 子序列的所有數值不變,並把其他的數都變為$p_{k_{(m+2)/2}}$,那麼整個數列就會變為 good。(因為這樣改變後 $\Delta(p)$將會等於 $\Delta(q)$)

接著應該有種直覺,若存在某個長度為 $m$ 的子序列,那麼也一定存在某個長度為 $m$ 的"連續"子序列是 good (意即 $k_1 = k_2 -1 = k_3 - 2 = \ldots = k_m - m + 1$)。其原因是,我們只要取以 $q_{(m+1)/2}$ 為連續 $m$ 個數中的第 $(m+1)/2$ 個數,判別式只可能變大。於是我們就找到連續的長度為 $m$ 的 good 子序列。

最後有一個解這題的關鍵性質:若一個連續子序列是 good,則此連續子序列的連續子序列也是 good!

證明如下:設此連續子序列 $q$ 長度為 $m$。我們在移除此子序列最右邊的數變成 $q'_1, q'_2, \ldots, q'_{m-1}$,若 $m$ 為偶數,$\Delta(q) - q_{m/2+1}+q_m = \Delta(q')$;若 $m$ 為奇數 $\Delta(q) - q_{(m+1)/2} + q_m = \Delta(q')$。無論 $m$ 是奇數或偶數,此子序列的判式在移除最右邊的數後都只會變大,所以移除後仍是 good 的子序列。同樣的可以證明移除左邊的數後也仍是 good 子序列。於是對於任意的子序列,都可以藉由先移除右邊的數在移除左邊的數達來獲得,至此證明完畢。

當知道這個性質後,就不難想到能在時限內找到最長的 good 子序列的方法。例如說,我們枚舉子序列的右界,然後去二分搜最左邊的 good 子序列左界,就一定可以枚舉到最長的 good 子序列。甚至若讀入檔案原本就把題分按照非遞減數列給你的話,是存在 O(N)的作法的。

我的程式碼如下:



2016年11月7日 星期一

農場例行賽 #13 官方解答

時隔一年多耍費日誌又出現新文章了!這代表此部落格要復活了嗎~唉再看看吧 Orz 有時覺得自己一頭熱也不知道寫這些題解到底有何用,基本上官方都有題解了啊~但我現在似乎算是農場例行賽的官方,所以題解只好自己來寫了 Orz 恕不支援英文版題解 >__<

= = =

在這之前先來介紹一下農場例行賽。

這系列的比賽是 Facebook 粉絲專業 競程日誌 所舉辦的每周例行賽,目前比賽所在的平台為 Codeforces 的 Group tw-icpc-blog ,最初主要是由卡恩 (tmt514) 和蜥蜴 (drazil) 負責打理題目。 而自從第 10 場開始蜥蜴邀請我幫忙出初階組的題目,於是我也加入了~

說句心裡話,每週參賽的人數都少少的不到五人,真沒想到這系列比賽能出到十幾場 wwwwww。那我為什麼要淌這趟渾水呢?目前是為了練快速出原創題的手感吧,因為最近感到我都出不了難題,覺得超難過,想要碰碰運氣能不能不小心生出個難題來,但這幾周下來似乎毫無成果的樣子 QQ 不過說到底... 練這個究竟有啥意義呢 XD

= = =

Problem A - Become an Escapiest!

這題是個簡單數學題。

首先,我們可以把每個可逃脫座標個別處理,只要有一個座標可以逃脫就夠了。

接著,要判斷是否可以從某個座標逃脫,條件有二:

1)  $P$ 和 $x_i$ 要在 $B$ 的同一側。
2)  你要能比熊早到達 $x_i$。

這題雖然簡單,但似乎有不少人會忘記判斷條件 (1) XD

我的程式碼如下:
Problem B - Become an Escapiest Again!

這題是常見的 BFS 題。

我們可設計狀態如右:step[x座標][y座標][上一步是遞增 or 遞減] = 到此狀態至少要幾步。
而有兩個狀態我們要設為起點(也就是初始 dp 值為 0): step[0][0][遞增] 和 step[0][0][遞減]。

每個狀態的下一步可以走到哪大家就自行判斷或參考程式碼吧~

我的程式碼如下:
Problem C - Problem setter is also an Escapiest!

這題是不常見的構造題。

先閒聊一下,原本沒有這題的,這題是在試著生 problem B 的測資時冒出來的。原本我 pB 測資 random生成時答案要不是 $-1$ 就是 $2 \times N-1$ 實在是非常困擾 XDrz,很多時候,生測資其實比解該題難上好幾倍呀 XD
閒聊到此。
- - -

首先先注意到,最佳解的路徑一定不會通過同一個格子兩次以上,這是因為格子狀的東西是奇偶分明的,有些格子一定走到時一定是偶數步,其他的則是奇數步,所以走出第一步後,不管什麼時候踏入同一格一定永遠是走(遞增/遞減)的數字近來,所以若有某個路徑會走過同一格兩次以上,我們一定可以把第一次進入該格到位後一次進入該隔間的步數都省略掉。於是我們在構造測資時就不必考慮經過同一格兩次以上的路徑了。

上一段講那麼多,但其實大家應該都會直接猜路徑是 S 形吧 XD 當 $N \equiv 3( mod 4)$ 時 S 行走過的格子數是 $(N \times N + 1) / 2$,剛好滿足條件! 而 $N \equiv 1( mod 4)$ 更是不用說了,接著我們就是要想辦法讓逃跑路徑除了 S 型別無選擇了!
於是我們就得限制住某些相鄰的格子的數字的大小關係(那些大小於的開口是朝向比較大的數字) 如下右,並且我們很開心地發現這些大小關係沒有 cycle 存在!於是我們的最後一步就是填入數字滿足這些大小關係。有沒有發現這其實就是拓樸排序問題呢?於是我們已經確保這題是可解的了,出題者並不是沒有把問題解決就丟給參賽者解唷 XD

但所有 AC 的人包括出題者都不是使用拓樸排序解啦 XD 我們再仔細看看這個大小關係圖,可以發現要自己直接構造並不是那麼困難,因為你會發現編號為奇數的 row 都大於編號為偶數的 row!所以我們就每條 row 分別填入數字就好啦,並且把 $1 \sim N \times N$ 中比較大的數字分給編號奇數的 row填,比較小的數則分給編號偶數的 row 填。

於是剩下的問題就是給你一條 row 相鄰兩隔的大小關係,請指定的相異 $N$ 個數使得所有大小關係皆滿足,這應該是個農場例行賽初階組最簡單的題目的程度的問題了吧~這部分就交由讀者囉。

我的程式碼如下:
Problem D - Become an Escapiest is not easy!

這是個不常見的 BFS 題。

先處理一下所有的 $d_i$ 的最大公因數 $g$ 不為 $1$ 的 case。明顯的,此時我們有機會走到的座標都是 $g$ 的倍數,所以若 $E$ 不是 $g$ 的倍數就哭哭逃不掉了,並且我們也只需考慮那些為 $g$ 的倍數的 $x_i$ 們。最後,不妨把所有數包括 $d_i$ 和殘存的 $x_i$ 以及 $E$ 都除以 $g$,於是問題就變成最大公因數為 $1$ 的版本了。

再來想想簡單一點的版本:$E < 10^6$。
這個本版甚至是比 Problem B 還要更容易構思出程式碼的,大家可以自己想想看,而且呀,這個版本的問題是解出原來版本的問題的其中一步唷!大家先想想看要如何拿從這個簡單的本版當跳板來解這題吧。


合理的猜測是,我們可以把題目所出現的 $x_i$ 比較近的都分在同一組,更精確地說我們可選定一個參數 $D$,兩個座標 $x_i$ 和 $x_j$ 若差的絕對值不超過 $D$ 就一定要分在同一組。分組出來後每個組別裡最遠的兩個座標都不會超過 $D \times N_i$ ($N_i$為第 $i$ 組的座標數)若每一組都可以從所有點的左邊跨到所有點的右邊,那就是可逃走的了。

最後的問題就是如何決定 $D$ 的數值了,其實啊,大家可以不用那麼認真來決定 $D$ 的值,因為考慮到時間複雜度問題, $D$ 不可能太大嘛,所以就直接不妨直接設 $D = 100$ 吧 ~ 你若有這麼做的勇氣就可以 AC這題了 XD 對不起這是超不良示範 >_<

好啦我們認真解決這個問題。首先要知道 $D$ 的意義是什麼 (題外話:唉,至今還是搞不懂航海王裡的 D 究竟是有何意義 XD),它的意義是,若連續 $D$個整數座標都是可走的,那麼這 $D$ 個座標都可以藉由卡恩製的傳送道具互相往返,且 $D$ 必須不小於所有 $d_i$ !!! (標紅色是因為最初的標程忘了考慮這個條件...所以若有人在比賽中寫出正解是會拿到 WA 的 QQ)
如此一來,若能逃到某組座標的右邊任一點和下一組之間的所有座標點就保證可以到達了!

若我們不去考慮如何證明 D 一定不會太大的話,要求出最小的 $D$ 值,只要慢慢增加 $D$ 的大小並做 DSU 即可,或是用 BFS測試之類的。

實際上啊,若只有兩個傳送道具傳送的距離長度分別是 $x$ 和 $y$ 且 $x$、$y$ 互質,則 $D$的最小值就會是 $x+y-2$,藉由此性質,我們有辦法證明 $D$ 的值一定不會超過 $d_i$ 中最大的兩個數的和,有興趣就自行更深入的研究相關問題吧。

我的程式碼如下:

總結:

稱我還有餘力的時候,大家快糾朋引伴來參加農場例行賽吧~