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

我的程式碼如下：