比賽連結
Editorial 連結
這場比賽我除了解題順序不認真以外，其他部分我可是非常認真的！在賽中完全沒有想過要去 challenge 別人！有人在賽中敲我 g+ 我也沒回應！但是名次好慘呵，我花了一個小時左右寫完了 C、D、F 後，直接打開 G，剩下的一個半小時都栽在上面了，賽中剩下 20 分鐘才想到解法，賽後一個小時左右才 AC。最後 rank 371，連抽 T-shirt 的機會都沒有。還有人問我是否想要再一次變成藍色，聽到別人這樣問我我好傷心喔 XDDD，我這幾場都有好好的比耶 XDDD 只是最近的比賽不小心把我的實力揭露出來讓我連掉五場 rating XDDD 最近的幾場比賽大都是比較大型的比賽諸如 VK cup、ZeptoLab Code Rush 之類的，每次遇到大型比賽我的名次就會變糟糕 ... 這是心理壓力的關係嗎？
最近總是直接寫題目的解答，這篇來回覆一下我以前在 BBS 使用的方式紀錄比賽，把比賽過程中我在思考什麼，在哪些地方卡住等資訊近可能的保留下來。
這場比賽，我想要犧牲一些解簡單題的時間，來換取更高的賽中 AC 難題的可能性，所以開場就直接從 pC 看起，看完後我就立刻連想到了 CF534 B - Covered Path，都是類似的概念，相鄰兩個時間點直不能超過給定值的題目。可是我的思緒很混亂，寫出了比較複雜的做法，明明就寫一個 for 迴圈就能解決，我卻寫了兩個，順的跑一次逆的也跑一次，還出了點 bug，結果13分鐘才 AC，這時候已經有不少人前三題都寫完了 =口= 結果我先寫 C也沒省到多少時間嘛 = =
接著我直接看 pD 也是個還算直覺但要把他寫成 code 無法立刻想到好寫的做法，但我還是憑直覺寫下去了。總之就是先簡查哪些向量若可以選就一定要選他，在檢查看看使用這些所有選的向量是否能攻擊到所有得被攻擊到的位置。是說這題 Sample Output很心機，硬是要和大家直覺寫出來的 Output長的不一樣...。我原本漏考慮了有可能會攻擊到盤面外部的 case，使得 Output 總是輸出 NO，我大概花了兩三分鐘才 de 出這個問題，後來修正後 output 還是和 Sample Output不一樣 = =，check 了一下才確定我的 output 確實也是正確的。
我寫完兩題後已經有人寫了五題了！挫敗感很高耶，我決定跳過 pE，直接看也有人在短時間 AC 的 pF。pF看完我立刻往複雜度 $O(n \sqrt{n})$ 的方向去想，因為讀完題目後立刻從我腦海裡浮現的知識是：每個 node 當 $k$ 的值從 $1 \sim n-1$，在改變時，他的父節點可能只會改變 $O(\sqrt{n})$ 次，這就和 $n$ 固定，$k$ 會改變時 $\lfloor n/k \rfloor$ 的可能值至多只有 $O(\sqrt{n})$ 很像，因為父節點的編號實際上就是 $\lfloor (x-2)/k \rfloor + 1$，所以要解這題，我們只需要把每個節點的的可能的父節點都各別求出來，以及會對應到該父節點的 $k$ 值個數也求出來就行了。於是讀完題想不到一分鐘我就立刻開始寫 code，但是寫到剩最後一部分 --- 記算父節點的編號以及有多少 $k$ 值會對應到該編號，我卻卡住了，我腦袋轉不過來 ... 每次我在認真比賽的時候，都不太能進行這類比較複雜的計算 ... 團體賽的時候我還可以秤隊友還在 coding 時，在旁邊深呼吸，想辦法靜下心然後在開始動筆計算，可是在個人賽的時候我幾乎無法靜下心做這件事，啊啊啊該怎麼辦 >_<
這時我想法亂成一團，在思考要不要靜下心好好動筆算的時候，有想到了令一種思考此題的方式 --- 上段所述的方法是固定子節點，思考父節點的變化。但我們可以從另外一個角度：考慮每個父節點，看看他有哪些子節點，我們可以發現，當 $k$ 愈大的時候擁有子節點的節點數量為 $O(n/k)$ ，所以若先把所有父節點所擁有的子節點區間都離線存下來，就可以 $O(n \log^2{n})$ (因為總共有 $O(n \log{n})$ 個區間) 配合 BIT 掃過求出每個父節點有多少子節點的值比自己大。原本我有點擔心這樣會不會花太多記憶體儲存，但你若有仔細看這題的記憶體限制，會發現這題的限制是 $512$ MB，比預設的 $256$ MB 還大，就會發現 author 預設的解法大概就是這個做法吧？要不然上一段的做法根本不需要什麼記憶體 XD 這個做法想清楚後，我就把原本寫的 code 果斷砍掉了 ... 重寫新的做法，寫完 Sample 對了之後我還自己生了最大的測資測了我的 code 的速度，看來是沒什麼問題後才 submit。我寫完三題時，已經有不少人把前六題都寫完啦！！！
隨便點了幾份 pF 的 code，兩種做法都有了寫，第一種做法的程式碼可以參考 rng_58 的 code，寫的非常精簡，而賽中14分鐘就 AC 的人則是使用第二種方法，他沒有離線預處理，而是使有了比較複雜的資料結構 (WaveletTree?這什麼東西@@) 使得可以 online 快速知道一個區間內有多少數小於給定值。
上傳 pF 後，我鐵了心直接挑戰 pG。 pG 題目非常簡短如下：
有一個長度為 $l$ 由 ULRD 所組成的上下左右的移動指令，你並不知道指令的 pattern 長怎樣。有一個機器人起點在 (0,0)，每一單位時間依序按照這串指令直性移步並移動一單位距離，若這串指令都執行過，會再從頭開始用同樣的 pattern 繼續移動。告訴你這個機起人某些時間點的位置，請找出一種可能的 pattern 或輸出無解。
這題感覺起來有點數學，又有點差分約數的感覺？我覺得我一定能解出來！但是想了許久就是沒什麼想到什麼明確的起手步，是因為有一點點精神不濟想睡覺的關係嗎？先把題目化簡移下好了，這題是二維的，如果變成一維的話我要怎麼做？想到這裡，我就發現，若會做一維，也就是說只有LR兩種指令的版本那麼我們就可以解二維的了！因為我們可以把U, R以及 L,D 分別是為同意種指令，若是 U,R 的指令那麼機器人所在的座標 $(x,y)$ 中 $x+y$ 的值就會加 $1$，若是 L,D 則會減 $1$。固解出一維的 case，我們就能月定pattern的每個指令會是L,D兩者之一或是 U,R 兩者之一。接著我們在改成把 L,U 和 D,R 個別綁在一起，做出來後就能就能得所有指令了！
轉換成一維(只有 L,R 兩種指令) 後我仍舊卡了很久，要按照時間序考慮問題嗎？還是按照時間 mod $l$ 的值由小到大考慮問題呢？如果有出現兩個時間 mod $l$ 的值相同又會怎樣？我們就可以得到整串指令移動完的為移會是多少，知道這件事後又怎樣？知道這件事後我們就可以按照時間 mod $l$ 的值由小到大考慮所有已知機器人的位置，做一些運算後，得知很多諸如 (前 $i$ 個指令移動完位移將是 $d_i$ ) 的資訊，如果 $d_i < 0$ 或 $d_i > i$ 或 $d_i$ 和 $i$ 的奇偶性不同就不合法，否則就可以貪心的填入 $(d_i + i)/2$ 個 R 進去之類的。所以若有兩個已知機器人位置的時間點 mod $l$ 結果相同，我們就可以得到正確的 pattern！所以我解決的其中一種 special case！但這要怎麼推廣？完全想不到啊 >_<
這種 special case 我們能確定 pattern 的主因是我們知道了整個指令群移動完的位移的值(令其為 $ds$)，所以我們若能確定該值，就解決了吧？ $ds$ 的值的可能性有 $0 \sim l$ 那麼多種，有辦法縮小其範圍嗎？有沒有可能同一組測資擁有不同的 $ds$ 值的合法解呢？這麼說來剛剛我們確定了 $ds$ 就能知道每個區間內有多少個 R 指令，所以說我們若把每個區間內的 R 指令個數當成變數，稱其為 $r_i$ 之類的，那就可以把 $ds$ 和 $r_i$ 列出線性等式吧？而且我們擁有 $ds$ 和所有 $r_i$ 的上下界( $ds$ 的上下界是 $0$ 和 $l$， $r_i$的上下界是 $0$ 和 該區間大小)，那是否存在某種快速枚舉這些變數的值的並判定有無合法解的演算法呢？嗯... 若枚舉了任何一個變數的值那麼就可以 $O(n)$ 判斷是否有合法解了，若枚舉 $ds$ 的 $O(l)$ 種可能值，那複雜度最高就是 $O(ln)$ 有點大耶？嗯... 某種程度上這些區間是型成環狀的... 環狀？枚舉！？這件是好像有印象！那不就是 CF526 E 的其中一種算法嗎？因為有 $n$ 個區間，所以至少有一個區間 size $\leq l/n$，所以就會至少存在有某個變數要枚舉的可能性 $\leq l/n$ 於是找出該變數並枚舉的複雜度會是 $O(l)$！於是我就解出來啦！想到這裡的時候，比賽已經剩不到 $30$ 分鐘了 0.0
最後寫 code 時發現使用這種做法還有好多好多 special case 要處理 ... 那些 $ds$ 在等式中係數可能是 $0$ 之類的問題，或是所有時間點剛好 mod $l$ 都是 $0$ 的問題(我覺得這個 bug 思考時不會漏掉的一定都是怪人！)。
AC 候我就在想，我使用了一個那麼奇怪的技巧來 AC 這題，想必不是 author 所用的解吧？而且這個技巧不久前才出現過耶？後來看了其他所有 AC 的 code，果然只有我使用這個方法 ...，我忽略了一件很重要的事：所有聯立等式中 $r_i$ 的細數都是 $1$ ！所以對於每個 $q+i * ds + r_i = v_i$ 的等式，我們可以根據 $r_i$ 的上下界來更新 $ds$ 的上下界，若全部等式更新完後 $ds$仍有整數解，那麼代入任一個 $ds$ 的整數解給所有式子後一定能得到在合法範圍裡的 $r_i$ 的整數解。於是 $code$ 應該能變成更簡單一些，根本不必枚舉某個變數的所有可能值啊！若...我在看到這題時，碼上就把所有該列的變數該列的等式列出來在紙上，是否能快一點想到呢？但我相信拿麼做的話就不會產生我這種奇葩的解法了 0.0
呵呵在最後一步採用了有點多餘且非常獵奇的方法，我該為此感到自豪還哀傷呢？
賽後看了剩下的題目， pA直接暴力枚舉即可。pB 就是一個很直覺的 greedy。 pE 就普通的 tree dp，記算可能要小心一點。 pH，嗯... 感覺起來不太難，要歸類為 greedy 吧？想了一下細節，覺得應該就是那樣了。不過 pH 目前 最短的AC code 值得研究研究，他的解題步驟和我的思考順序並不一樣，我還不知道怎麼證他的做法的正確性 ... 證出來並覺得很有意思的話再分享吧？
如果我這篇相較於過去的解題報告，寫的讓大家完全看不懂，想必是很正常的一件事...
沒有留言:
張貼留言