GKS 2022 Round B

果然早七是個囧時間。星期天不是個適合早起的日子,睡到七點半跳起來參賽所以前面吃了好些失誤。不過最後還是在結束前五十分鐘破台了。

照例分數截圖以下有雷;最終排名是 69 名 (Nice!)。

Q1. Infinity Area

就很簡單的數學計算題。WA 的原因是 int64_t

Q2. Palindromic Factors

原本以為掃因數會慢的,不過看起來好像還好,範圍內最大的高合成數 6983776800 只有兩千多個因數,直接掃 √N 以內的數去做都還行。TLE 兩次的原因是 int64_t

……是的,這兩題因為早上剛起來腦袋混亂,忘記考慮 overflow 所以總共死了三次。(所以早七是個囧時間。)

Q4. Hamiltonian Tour

仔細一想這題表面上是 Hamiltonian Cycle,實際上只是 DFS 搜尋的走路而已。(應該都看過那種 DFS 搜尋的教學裡,在樹的外皮畫一個彎彎曲曲的箭頭表示搜尋的順序那玩意?這題就是要輸出那個箭頭。)

因此只要固定好 DFS 的搜尋順序 (例如先左轉再直走再右轉),就能夠把路線跟著 DFS 的過程走過一次。例如下圖,這一區塊從左邊來,上下可走但右邊不行:則路線是進來後往北,接上面那塊的路線,它會回到右上格;右邊不能走所以直接往南;再往南進下面那塊,接下面那塊的路線,回到左下格;最後往西走離開。當然有些細節例如 DFS 過的不能再走,以及開頭那格不能離開要接成圈等,不過大致上的概念就是這樣。

Q3. Unlock the Padlock

首先,由於操作是可交換的,把題目的套娃條件倒過來比較好做事,也就是先把大範圍調好再來調小範圍。這樣就能看到這題的子結構:大範圍只有兩個選項,要嘛把最左邊調成 0,要嘛把最右邊調成 0。不過有個問題:進到同一個子問題時鎖的數字不一定一樣,可能會差一個常數次數。

例如題目的 0~9 的鎖,1 1 2 2 3 3 的數字來說好了。取到中間的 [1]~[4] 的位置時,可能因為先左再右,它成了 8 9 9 0;也可能因為先右再左,它成了 0 1 1 2。如果把這兩種狀態看成兩種的話,那其實幾乎沒有重疊到子問題 (因為每個範圍有 D 種可能位置);就算直接筆記法寫下去也會需要看 2^N 個子問題,對 N<=400 這個範圍顯然不可行。

這裡的關鍵就在於,雖然進來時的狀況不同,但我可以紀錄進來之後如果我選左邊調成 0 後還要幾步,以及選右邊調成 0 後還要幾步。要哪一邊調成 0 這件事每次進來看現在狀況如何再算就好,但之後還要幾步這回事需要求子問題,所以就先算好記起來。這樣一來每個範圍就算差了常數次數也可以共用同一個子問題計算結果。不過因為腦袋大概只清醒一半,感覺筆記法比較好寫所以就還是寫了筆記法,不然理論上應該是可以寫成 DP 的。

小結

……果然早七還是個囧時間。(因為很重要所以要說三次)

這場意外的破台的人數不多 (只有約一百人),看起來是 Q4 大測資在守門;Q4 小測資因為是規則圖形,可以證明一定有解,解也很好寫;但大測資沒有規則,所以要真的找出它跟 DFS 搜尋順序的關連再來寫才會過。

接下來是 5/14 的 GCJ R2,以及 5/22 的 GKS Round C。下次見。

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

這個網站採用 Akismet 服務減少垃圾留言。進一步了解 Akismet 如何處理網站訪客的留言資料