--- tags: Academic --- # 題解：鳳梨組 [Final Scoreboard](https://i.imgur.com/SfqZGBJ.jpg) ## 道歉啟示 對於 房地產投資客 和 K進制轉換 兩題的題目中出現的錯誤，我們均是在比賽進行中和題解撰寫時才發現。 對於這些錯誤，我們會銘記在心，並且會在下一屆比賽時特別注意。 ## A. 金錢規劃 題目：教授 題解：曾俊宏 照著題目做即可! 先讀取總測資數後，對於每一筆測資讀兩數字整數(分別是收入 $I$ 與支出筆數 $N$)，之後再讀取 $N$ 個數字並且從 $I$ 中扣除即可! [Python by 黃鈺程](https://github.com/henrybear327/2018-CCU-Pineapple-Contest/blob/master/%E9%87%91%E9%8C%A2%E8%A6%8F%E5%8A%83/amos.py) [C++ by 郭晏誌](https://github.com/henrybear327/2018-CCU-Pineapple-Contest/blob/master/%E9%87%91%E9%8C%A2%E8%A6%8F%E5%8A%83/macaca.cpp) ## B. 房地產投資客 題目：教授 題解：黃鈺程 非常抱歉，這題題目有一點小瑕疪，我們現在寫題解時才注意到：題目關於「投入金額、房貸利率、操作次數」的型態，輸入格式、技術規格、範測是不太一致的。我們測試的測資裡使用的是技術規格中所說的 float, float, int。這可能造成部份隊伍只使用範測測試是找不出這種情況的。 另外這題在 judge 時有開放浮點數誤差，只要你的結果與答案誤差在 0.1 以下即可。比賽中會 rejudge 來自於 pc^2 會錯誤估計程式執行時間，他把他判斷是否在誤差內的時間也算進去，而他判斷的時間莫名的長……。至於有些隊得到的 Incomplete Output，是因為在 pc^2 的誤差處理機制有瑕疵。如果最後一筆測資在輸出答案的時候並沒有輸出換行，會造成比對錯誤。 另外比賽中有許多隊沒看到要輸出結果至**小數點後二位**，造成無法 AC。 Python(3.6) 的寫法是 `print(f'{ans:.2f})'` C 的寫法是 `printf(“%.2f“, ans);` C++ 的寫法是 `cout << fixed << setprecision(2) << ans << endl;` [Python by 黃鈺程](https://github.com/henrybear327/2018-CCU-Pineapple-Contest/blob/master/%E6%88%BF%E5%9C%B0%E7%94%A2%E6%8A%95%E8%B3%87%E5%AE%A2/amos.py) [C++ by 陳煒杰](https://github.com/henrybear327/2018-CCU-Pineapple-Contest/blob/master/%E6%88%BF%E5%9C%B0%E7%94%A2%E6%8A%95%E8%B3%87%E5%AE%A2/andy.cpp) ## C. 車用發電機電壓轉譯 題目：教授 題解：黃鈺程 Hint 中給的應該足夠明顯。假設每個測資有字串 `L`, `H`, `Q`，那所求即為找出 `L` 與 `Q` 不同的那連續 7 個位置，然後將 `Q` 中對應位置的子字串轉為 10 進位。實作就一個 for 掃一下，看是從第幾個位置開始，`L` 與 `Q` 是不同的。 [Python by 黃鈺程](https://github.com/henrybear327/2018-CCU-Pineapple-Contest/blob/master/%E8%BB%8A%E7%94%A8%E7%99%BC%E9%9B%BB%E6%A9%9F%E9%9B%BB%E5%A3%93%E8%BD%89%E8%AD%AF/amos.py) [C++ by 陳煒杰](https://github.com/henrybear327/2018-CCU-Pineapple-Contest/blob/master/%E8%BB%8A%E7%94%A8%E7%99%BC%E9%9B%BB%E6%A9%9F%E9%9B%BB%E5%A3%93%E8%BD%89%E8%AD%AF/andy.cpp) ## D. 單字背誦 題目：黃鈺程、郭晏誌 題解：黃鈺程 這題是經典的一筆畫問題。用圖論的語言來講，是歐拉環（Euler Circuit）。每筆測資可以轉換成一個有向圖 $G$。每個單字是圖中的邊，圖的節點是字母，例如 `[electricity, yarn, negotiate, abandon, ninja]` 與 `[xy, yx, ab, ba]` 分別建成圖： ![](https://i.imgur.com/TRcUdrC.png) 題目所求就是在問 $G$ 是不是一個或多個歐拉環所組成，而這可以藉由檢查圖中是不是每個節點的入邊數（in degree）等於出邊數（out degree）。這個 **充要關係** 可在各離散課本找到，因此不在此說明。題外話，如果這題改成問給定的單字可不可以組成 **僅一個** 歐拉環，那就得先判這個圖中所有 degree ≠ 0 的點是連通的喔。 不過如果不知道歐拉環，這題也是某種程度可以解出來的： 1. 每個單字只有字首與字尾的字母有意義，中間有什麼字母不影響結果。 2. 如果一筆測資是 Lucky，則對於任意字母，它「出現在單字字首的次數」要等於「出現在單字字尾的字數」。 這可以用反證法證明：假設這些單字是 Lucky，且字母 c 出現在字尾的次數比出在字首的次數多一，則會有一個字尾為 c 的單字找不到下一個單子繼續接，因此不是 Lucky。 至此，你就可以 **猜說** 是不是統計一下各字母的情況，來判定是 Lucky 還是 QAQ。這剛好會是對的，不過不正確，因為並沒有在邏輯中證明這是「若且唯若」的關係。上述只證明了 => 的關係，並沒有 <=，也就是說如果統計的結果成立，那這筆測資就一定是 Lucky 嗎？（答：是的，性質由歐拉環的證明保證）。 我不知道解出這題的選手們是不是都有注意到這個，不過就算沒有，既然是比賽，證明不嚴謹是可以接受的啦~有想法比較重要。這題被許多應該沒聽過歐拉環的人（非資工系的選手與資工大一）解出來，讓我非常驚訝！ 這題實作非常簡單，統計一下即可，利用英文字母的 ASCII Code 是連續的，可以直接開陣列算一下各字母的次數。 [Python by 黃鈺程](https://github.com/henrybear327/2018-CCU-Pineapple-Contest/blob/master/%E5%96%AE%E5%AD%97%E8%83%8C%E8%AA%A6/solution.py) [C++ by 郭晏誌](https://github.com/henrybear327/2018-CCU-Pineapple-Contest/blob/master/%E5%96%AE%E5%AD%97%E8%83%8C%E8%AA%A6/macaca.cpp) ## E. 寶藏獵人 題目：李晨維 題解1：李晨維 此題是一題簡單 DP 題，運用的是高中排列組合的加法原理，對於每一個位置，我們去看他的下方以及左方的位置是否為陷阱，如果否就把走到那個位置的方法數加到目前在算的位置上，所以 DP 更新式子如下: ``` dp[i][j] = dp[i - 1][j] + dp[i][j - 1] if dp[i - 1][j] and dp[i][j - 1] are not traps dp[i][j] = dp[i - 1][j] if dp[i][j - 1] is a trap dp[i][j] = dp[i][j - 1] if dp[i - 1][j] is a trap ``` 另外，此題有兩個地方須注意: 1. dp 表必須開 long long int，因為 `m` , `n` 最大到 30 時 int 會 overflow (思考一下，完全沒陷阱時，路徑數為 $\frac{60!}{30!30!}$，這個數字有多大呢？)。 2. 如果做法是一開始將邊界初始化為 1，須小心邊界是否有陷阱，如果有的話除了起點到陷阱的部分初始化為 1 之外，其餘部分需初始化為 0 或是直接標記成陷阱。 ---- 題解2：黃鈺程 你可以將題目的地圖與 dp 表格分開存，也許會比較好理解。假設題目給的地圖是 `A`（0-based index），則 dp 寫成： ``` dp[r][c] = 從起點走到位置 (r, c) 的方法數 dp[0][0] = 0 if A[0][0] is trap else 1 dp[r][0] = 0 if A[r][0] is trap else dp[r-1][0] dp[0][c] = 0 if A[0][c] is trap else dp[0][c-1] dp[r][c] = 0 if A[r][c] is trap else dp[r-1][c] + dp[r][c-1] ``` 顯而易見的，在都沒有陷阱的情況下，走到 `(r, c)` 方法數即為走到 `(r-1, c)` 的方法數加上走到 `(r, c-1)` 的方法數。 [Python by 黃鈺程](https://github.com/henrybear327/2018-CCU-Pineapple-Contest/blob/master/%E5%AF%B6%E8%97%8F%E7%8D%B5%E4%BA%BA/amos.py) [C++ by 李晨維](https://github.com/henrybear327/2018-CCU-Pineapple-Contest/blob/master/%E5%AF%B6%E8%97%8F%E7%8D%B5%E4%BA%BA/solution.cpp) ## F. 最後衝刺 題目：教授 題解：曾俊宏、郭晏誌 關鍵點是 sorting 針對時間區間的右端點排序，如果右端點相同時再對左端點排序。dp 轉移方程式定義為 $dp[ i ]$ 表示使用前 $i - 1$ 個科目且必使用第 $i$ 個科目時所能達到的最大分數提升。 初始值設定為 $dp[ i ] = inp[ i ].score$ (第 $i$ 個科目的分數) 之後迴圈迭代 $j < i$ 時先將 $dp[ i ]$ 值取出($cur\_score$) 從後面往前看如果第 $j$ 個科目的時間沒有與 第 $i$ 個科目重疊則 $dp[ i ] = max (dp[ i ] , cur\_score + dp[ j ] )$ **注意**: 可能有起始時間 = 結束時間的 case，所以說，如果沒有對右端點相同時進行左端點排序的話，下面這筆測資會炸開。 Sample Input ``` 1 4 1 3 10 8 8 1 5 8 5 6 8 5 ``` Sample Output ``` 16 ``` [Python by 黃鈺程](https://github.com/henrybear327/2018-CCU-Pineapple-Contest/blob/master/%E6%9C%80%E5%BE%8C%E8%A1%9D%E5%88%BA/amos.py) [C++ by 李晨維](https://github.com/henrybear327/2018-CCU-Pineapple-Contest/blob/master/%E6%9C%80%E5%BE%8C%E8%A1%9D%E5%88%BA/tom.cpp) [C++ by 陳煒杰](https://github.com/henrybear327/2018-CCU-Pineapple-Contest/blob/master/%E6%9C%80%E5%BE%8C%E8%A1%9D%E5%88%BA/andy.cpp) [C++ by 曾俊宏](https://github.com/henrybear327/2018-CCU-Pineapple-Contest/blob/master/%E6%9C%80%E5%BE%8C%E8%A1%9D%E5%88%BA/henry.cpp) ## G. 超級傳情 題目：教授 題解：黃鈺程 題目稍為難讀懂，不過從範測推一下，應該可以了解。這題有 2 種做法，時間分別是 $O(N*E)$ 與 $O(N^3)$，$N$ 代表圖的節點數而 $E$ 是邊數。因為這題的 $N$ 不大，所以兩種解法都會 AC。 首先 $O(N*E)$ 的解法來自一個簡單的想法：針對每個人，我去算他能傳情給多少人，假設第 `u` 個人能傳情給 `cnt[u]` 的人，那題目所求就是 `sum(cnt)`。而我們可以利用圖論來求出某一個人能傳情給多少人：將傳情當作有向圖的邊，人當作有向圖的點，那對於點 `u` 來說，它能傳情的數量就是從 `u` 出發，能走到的點的數量再減一（去掉自己）。這可以用一個簡單的 dfs 來完成，dfs 本身的時間為 $O(N+E)$。因此，對每個點 dfs 算 `cnt`，最後加總，整體時間為 $O(N * (N + E) + N) = O(NE)$。如果是完全圖的話，會是 $O(N^3)$ $O(N^3)$ 的解法改自 Floyd Warshall，dp 寫成： ``` dp[k][u][v] = 只使用前 k + 1 個點的情況下，u 是否可以傳情給 v。 ``` 我們特設一開始自己是可以傳情給自己，另外再加上題目給定的傳情，我們有以下初使情況： ``` dp[0][:][:] = False dp[0][u][u] = True dp[0][u][v] = True 對於所有題目給定的 (u, v) ``` 彷造 Floyd Warshall 的轉移方程： ``` dp[k][u][v] = dp[k - 1][u][v] || (dp[k - 1][u][k] && dp[k - 1][k][v]) ``` 當我們建好這個 dp 後，我們枚舉任 2 個**相異點** `(u, v)`，查表看看 `u` 能不能傳情給 `v`，加總所有可以的情況，即為題目所求。 [Python by 黃鈺程, $O(NE)$](https://github.com/henrybear327/2018-CCU-Pineapple-Contest/blob/master/%E8%B6%85%E7%B4%9A%E5%82%B3%E6%83%85/amos.py) [C++ by 曾俊宏, $O(N^3)$](https://github.com/henrybear327/2018-CCU-Pineapple-Contest/blob/master/%E8%B6%85%E7%B4%9A%E5%82%B3%E6%83%85/henry.cpp) ## H. 資工學霸 題目：教授 題解： 對於學霸的定義，$P[i] \geq P[t]$ 且 $M[i] \geq M[t]$ 且 $M[i] + P[i] > M[t]+P[t]$，直接思考可能有點抽象。如果我們換個方式思考，以數學能力為 $x$ 軸，程式能力為 $y$ 軸進行作圖，我們可以觀察到如果一個點 $(x_i, y_i)$ 代表的是學霸的話，他的右上方區域就不會有其他點的存在！換句話說，大於 $x_i$ 且 大於 $y_i$ 的區域裡，是不會有其他點的！ 實作的話，我們先對其中一種成績進行排序，之後對於該成績由大到小檢查回來即可。 [C++ by 李晨維](https://github.com/henrybear327/2018-CCU-Pineapple-Contest/blob/master/%E5%AD%B8%E9%9C%B8/tom.cpp) [C++ by 陳煒杰](https://github.com/henrybear327/2018-CCU-Pineapple-Contest/blob/master/%E5%AD%B8%E9%9C%B8/andy.cpp) [C++ by 曾俊宏](https://github.com/henrybear327/2018-CCU-Pineapple-Contest/blob/master/%E5%AD%B8%E9%9C%B8/henry.cpp) ## I. 蟲洞 題目：黃鈺程 題解：黃鈺程 這題是倍增法再稍為轉個彎。首先，我們換個思路，題目原先問建築物 0 之前 K 步可能在哪，我們改成枚舉每個建築物，看看這個建築物 K 步後是不是在建築物 0，而找出每個建築物 K 步後在哪，可以透過倍增法預建表，將查詢時間降到 $O(lgK)$。 ``` dp[i][u] = 從建築物 u 出發，走 2^i 步後在哪 dp[0][u] = p ``` ``` dp[i][u] = dp[i - 1][dp[i - 1][u]] ``` 建築物 `u` 走 `2^i` 步後的位置，即為走 `2^(i-1)` 後的位置，再走 `2^(i-1)` 步。例如 8 步後的位置，即為走 4 步再走 4 步。當我們把這個 dp 表建好，我可以透過對 K 二進制分解，來查詢 K 步後的位置。例如我想知道從建築物 3 走 21 步後的位置，因為 `21 = 16 + 4 + 1 = 2^4 + 2^2 + 2^0`，所以答案是 `dp[4][dp[2][dp[0][3]]]`，即為從建築物 3 走 `2^0` 步再走 `2^2` 步再走 `2^4` 步。 預建表的時間為 $O(lgK * N)$，查詢時間為 $O(N * lgK)$，所以整體時間為 $O(NlgK)$。實作上，因為 N 仍然不小，使用 Python 會 TLE，得使用 C++ 或 Java 這題才會 AC。 [Python (by 黃鈺程，TLE)](https://github.com/henrybear327/2018-CCU-Pineapple-Contest/blob/master/%E8%9F%B2%E6%B4%9E/solution.py) [C++ (by 黃鈺程，AC)](https://github.com/henrybear327/2018-CCU-Pineapple-Contest/blob/master/%E8%9F%B2%E6%B4%9E/solution.cpp) [C++ by 陳煒杰](https://github.com/henrybear327/2018-CCU-Pineapple-Contest/blob/master/%E8%9F%B2%E6%B4%9E/andy.cpp)