Codeforces Round #298 (Div. 2)

這場的題目敘述偏長有些題目都是閱讀題 ( 要自己根據題目發生的事件來判斷有哪些限制，如 pB 和 pD )，對英文不好的人大概很吃力吧 ...

Problem A --- Exam

題意：給找出正整數 $1 \sim N$ 的最大的 subset，使得可以把這個 subset 的所有數排成一列，使得相鄰兩個數的差的絕對值都不是 1，並給出任一種排列方法。
數據範圍：$N \leq 5000$。

tag：[構造]

= = = = = = = = = = = = = = =
身為 Div 2 A 的構造題，應該就是個隨便亂構造都構造的出來的東西吧？合理猜測大部分的 $N$ 值都有辦法找到一個 $1 \sim N$ 的排列滿題目條件，只有 $N = 2, 3$ 時例外。

我除了特例以外的構造方法可直接參考我的 code 。

Problem B --- Covered Path

題意：有一台車共行駛 $t$ 秒，第 $1$ 秒的速度是 $v_1$，第 $t$ 秒的速度是 $v_2$。每一秒內的速度都是等速，相鄰兩秒的速度差至多為 $d$，請問這 $t$ 秒鐘最長的可能行駛距離是多少？

數據範圍： $1 \leq v_1, v_2 \leq 100$，$2 \leq t \leq 100$，$1 \leq d \leq 10$

tag：[ 數學 ] [ 物理 ]

關鍵字：斜率
= = = = = = = = = = = = = = =
某種程度這題算是閱讀題吧？要確實理解題目所說的物理意義。若把此題的物理意義移除，則會變成：有 $t$ 個數 $a_1, a_2, \cdots , a_n$，已知$a_1 = v_1$，$a_t = t_2$，任相鄰兩數差都不超過 $d$，請問所有數的總合最大是多少？ (你若問要是速度出現負數也能這樣轉變題目嗎？我並不清楚，題目關於速度是負的似乎沒寫清楚要怎麼考慮這樣的狀況。)

轉換完題目後就比較好思考了。我們會希望每個數愈大愈好，考慮 $a_1$ 及 $a_t$ 對所有其他數產生的限制會得到不等式： $a_i \leq a_1 + d * (i-1)$ 以及 $a_i \leq a_t + d * (t-i)$。並且直接令 $a_i = \min(a_i + d * (i-1), a_t + d * (t-i))$會滿足題目條件，於是得到能使這 $t$ 個數總合最大的序列了。

這個解法其實是很常見的概念，我印象中 SRM中 Div1 Easy 裡根本有簡化後一模一樣的題目。

另外，由於這題的數據很小，所以也可以使用 dp 來做，$dp[x][y]$ 用來儲存 時間 $x$ 速度為 $v$ 時從時間 $1$ 至時間 $x$ 所能行駛的最長距離。

Problem C --- Polycarpus' Dice

題意：有 $n$ 個骰子，第 $i$ 個骰子的可能結果為 $1 \sim d_i$ ，已知擲出來的骰子結果為 $A$，請對每個骰子輸出一定不可能骰出的點數有幾種。

數據範圍： $n \leq 200,000$，$1 \leq d_i \leq 10^6$，$n \leq A \leq d_1 + d_2 + \cdots + d_n$。

tag：[ 貪心 ]

= = = = = = = = = = = = = = =
個人覺得這題比 B 還要簡單耶？可是 B 的 AC人數還是多很多。這題 pretest沒有會爆 int 的測資，所以可以 hack 到大量只開 int 的解。

對於一個骰子，不難想像他可能骰出的值的範圍是連續的，所以只要求出他最低可能值和最高的可能值就結束了。最高的可能值就是其他骰子的值盡可能小的時候，也就是 $\min (d_i, A-(n-1))$，而最低的可能值則是其他骰子的值盡可能大時，也就是 $\max (1, A-(\sum_{x=1}^n{d_x}) + d_i)$

Problem D --- Handshakes

題意：有一個資訊競賽活動，每個新進場的人都要和在場的所有沒有正在比賽的人握手，且任何時刻在場的任三個人都有可能組成隊伍並開始比賽，直到活動結束，在活動結束前不會有任何人離開會場。給你每個人進場時各和多少數量的人握手，請判斷給你的資訊是否有某種符合的所有人進場順序，若有，請給出一組解。

數據範圍：人數不超過 $2*10^5$。

tag：[ 貪心 ]
= = = = = = = = = = = = = = =
這題我看了大家的 code 後發現有各種做法，我就講一下最多人使用同時也是我使用的方法。

一樣先簡化一下題目，把他變成比較正統的數學描述方法。
若把這些人的握手數按照進場順序寫下來($d_1 \sim d_n$)，必須滿足以下三個條件：

1. $d_1 = 0$
2. $d_i % 3 = (i-1) % 3$
3. $d_{i+1} \leq d_i + 1$

我想了一下下後直覺告訴我這題是貪心的題目，若要使用貪心，一個很常見的方法就是，每次決定下一個數時，直接選擇最大的可以用的數，而在這題這樣子做會是對的，而且將有很好的複雜度。

實作方式如下：
1. 設一變數 $v$ 代表我們想要取的值，初始值為 $0$。
2. 若存在握手數為 $v$ 的人，則把他當作下一個進場的人，並且把 $v$ 值加一。
3. 否則把 $v$ 值減 $3$ 並回到步驟 2，若還沒取到 $n$ 個人 $v$ 值就變為負，則答案為 Impossible。
 可參考第一名的 code。

我們不需要擔心步驟 3 執行太多次，因為所有過程 $v$ 的減少量不會超過 $v$ 的增加量加二，而會增加 $v$ 值的步驟 2只會執行至多 $n$ 次，且每次只加一。

至於此方法的正確性嘛 ...有一類的貪心法證明是長這樣：若存在某個解答長的和我們構造出來的的不一樣，一定有辦法經過一些變換變成和我們構造出來的一樣，於是若存在解則我們的構造法一定也能找到解！

於是我們先假設，我們若找出的解答，則會是 $d_1, d_2, \cdots, d_n$，以及現在存在另外一組解答為 $a_1, a_2, \cdots, a_n$。
若序列 a 和序列 d 不同，必有一最小的 index $i$ 使得 $d_i \neq a_i$，並且由於 $d_i$ 是可以挑的最大的數，所以我們可確定 $d_i > a_i$，接著我們令 $j$ 為大於 $i$ 的最小的 index 使得 $a_j = d_i$，接下來我們想要選一個 index $k$，使得我們能把序列 $a$ 的第 $i$ 個數至第 $i+k-j$個數整段能無痛的和 第 $j$ 個數至第 $k$ 個數交換。舉個實例：

$d$ 序列為 0,1,2,3,4,5,6,1,2,3,1
$a$ 序列為 0,1,2,3,1,2,3,4,5,6,1

則 $a$ 序列和 $d$ 序列第一個不同的數的位置是 4，並且在 $a$ 序列中 $d_4 = 4$ 這個數下一次出現的位置是 $a_7$，而我們發現我麼可以把藍色這段和紅色這段交換就變成 $d$序列了！分 case 討論後可以證明，令交換的子序列為最長的子序列，滿足 紅色子序列的所有數比對應到的藍色子序列的數都還要來的大(嚴格)，則一定可以交換。(我覺得兩個子序列緊接在一起的 case 並不太好證。但總之我確實把所有 case 都證過了。)

實際上並無法總是只交換一次就把 $a$ 序列變成 $d$ 序列，必須交換數次才能讓同樣的 prefix長度增加為序列長度。

徵求精減的證明 >_<。

Problem E --- Berland Local Positioning System

題意：公車站共有 $n$ 站，公車會從第 $1$ 站出發直到第 $n$ 站，再折返回第 $1$ 站，並一直反覆。有一個人他把上車到下車時所經過的所有站的編號記下來 (包括首尾站，並且他可能繞了好幾圈才下車)，但你只知道這些邊號排序後的結果，給你每站之間的距離，請問你是否能確定這個人搭了多長距離的公車？

數據範圍： $n \leq 2*10^5$，給的編號序列一定合法，序列長度為 $m$ ($1 \leq m \leq 4*10^5$)

tag：[ 模擬 ] [ 兩個指標 ]

= = = = = = = = = = = = = = =
賽中我花在 hack 的時間太久，回來寫這題時已經來不及寫不完了＠＠賽後也懶的寫完...

我想到的方法如下：

令 $d_i$ 為數字 $i$ 在序列中出現幾次，則任意合法路段，把序列 $d$ 按照連續相同的數字分段，一定不會太多段。於是我們可以用一些 tuple $(L ,R ,num)$ 來代表邊號 $L \sim R$ 的公車站都個別出現 $num$ 次。

所以我們就枚舉搭公車的起點，在枚舉開始方像為左或右，由於我們知道他搭公車的站數為 $m$，所以可以快速求出上一段所說的行式，就可以比對看看和這個人所搭的公車有沒有一樣。一樣的話就可以檢驗此種公車路線長度是否和至今合法的路線長度都一樣。

這個做法細節想起來有點複雜，會令人不想寫下去,,,

現在我們再多想一點點。

若先隨便選個點當起點，並經過 $m$個站，我們就得到了其中一種經過 $m$ 佔的公車路線。接著，我們只要把此路線的起點向前移一站，同時也把終點向前移一站，就得到另外一個公車路線了！共移 $2n-3$ 次就可以把所有可能的公車路線都試過了 =口=

於是我們可以輕鬆的使用 map 等資料結構來記錄路線的狀態有沒有和題目所給的序列一樣。

以上第二個方法是我看了第一名的 code 才發現的。

Problem F ---  Simplified Nonogram

題意：Nonogram是個類似數讀的遊戲，以一個 $n*m$的表格，請你把每一個都塗成黑色或白色，使得每一行及每一列連續的黑格段數都和測資指定的一樣。任一種填法皆可。

數據範圍：$1 \leq n \leq 5$，$1 \leq m \leq 20$。

tag：[ DP ]

= = = = = = = = = = = = = = =
我看到這題就立刻聯想到我在 SRM655 出的 Div.2 Hard，畢竟數據範圍長的那麼像...，於是我就直接從 dp 的方向去思考了。這題比我出的那題麻煩，還要輸出解...，很難讓不同層的 dp 共用記憶體。我用來儲存代表每一列的狀態數有 $21$ 那麼大，記憶體若要開 $21^5 * 20 * 2$ 不知道是否開的起來...，但我想說應該亂寫都會過吧，就不開陣列來 dp 而直接使用 STL 的 map。但寫完後使用 Codeforces 的 Custem Invocation 測了一下發現會 TLE ... 最後靠著 "用非常多map代替一個 map" 以及 "一定沒有必要走到的 status 都不要塞到 map裡" 就 AC 了。其實應該只需要靠第二個方法，因為它能減少大量的狀態數。

賽後開了別人的 code 發現，直接開陣列記憶體其實有辦法開的起來,,, (只是要想辦法只使用bool 或 char)。

我 dp 的方式是以 column 的順序 dp，每加一個 column 就更新每一個 row 的狀態，每個 row 的狀態有：已有幾條連續的黑格，以及最後一個是黑的還白的。應該算是平淡無奇吧？就狀態維度有點多令人感到有點煩而已。

而我所位的一定沒有必要走到的狀態是指：若存在某一個 row ，後面無論如何塗黑白格都無法達成目標的狀態。