= = =
在這之前先來介紹一下農場例行賽。
這系列的比賽是 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 中最大的兩個數的和，有興趣就自行更深入的研究相關問題吧。
我的程式碼如下：
總結：
稱我還有餘力的時候，大家快糾朋引伴來參加農場例行賽吧~
沒有留言:
張貼留言