農場例行賽 #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)的作法的。

我的程式碼如下：

農場例行賽 #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$ 中最大的兩個數的和，有興趣就自行更深入的研究相關問題吧。

我的程式碼如下：

總結：

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