ACM-ICPC
TOPC
2017
TOPC2017
本次賽題命題團隊為東華大學羅壽之教授、李官陵教授,清華大學李哲榮教授,元智大學張經略教授,台灣大學退役選手陳庭緯先生、王瀚中先生,清華大學退役選手李彥余先生,交通大學退役選手林韵凱先生、于尚鑫女士與裁判長所組成。由裁判長諮詢團隊後,自十道題目中選出八道進行修改調整後做為正式賽題,並委由命題團隊中的退役選手與台灣大學退役選手黃上恩先生與交通大學退役選手廖俊杰先生驗題。裁判長謹代表 2017 ACM-ICPC Asia Taiwan Online Programming Contest 感謝所有參與題組準備工作的教授與退役選手們辛勤的付出。
以下是本次的賽題講評。
isolate
Sandbox 準確量測執行時間,因此時限並不算太寬裕。vector
, set
, map
, queue
, priority_queue
等等,以及常用的演算法 sort
, lower_bound
, next_permutation
等等。cin
、cout
以及 Java Scanner
、System.out
的同學,如果在比賽中處理數以萬計的大規模輸入跟輸出,請務必留意是否有作適當的最佳化。一般的建議是在競賽時 C++ 開發者使用 scanf
、 printf
以及 Java 開發者使用 BufferedReader
配合 StringTokenizer
、 StringBuffer
暫存輸出最後再一口氣用 System.out
。題意是給定兩個集合 \(A\) 跟 \(B\) ,求兩個集合的 Jaccard similarity coefficient。
這一題是本次題組中最簡單的題目之一,只要能夠讀懂題目上的數學式,便能很快地進行程式的撰寫。這題有一個小陷阱是 Jaccard similarity 剛好是 \(0.5\) 時,如果粗心可能會錯判。如果參賽者熟悉一些語言提供的集合資料結構,那麼寫起來會更快,如下列 Python 3 程式碼:
題意是給定六張撲克牌的數字,求那六張牌的牌型。
這是在本次題組中技術難度比較低的題目,但有許多隊伍打錯字,或是實做方法選擇上,耗用了比較多實作時間。一個建議的實作方法是使用 C++ STL 的 map
、 Java STL 的 HashMap
、 Python 的 dict
來進行實作,如此一來可以很快的得知有多少種數字,以及每種數字出現的次數。Python 3的範例程式如下:
題意是給定 \(n\) 個區間,求將所有區間塗上顏色,使得任兩個有交集的區間顏色都相異的最小顏色數。
首先我們分析一下這題答案的下限:如果有一個點,落在 \(k\) 個相異區間內,那麼答案至少要是 \(k\)。落在的最多區間的那個點,所對應的 \(k\) 值(以下稱 \(k^*\)),就是答案的下限。
接下來,我們如果能夠設計出一個演算法,用 \(k^*\) 種顏色塗滿所有區間,那麼,我們就能證明 \(k^*\) 就是該組輸入的答案。這裡採用一個 Greedy method 來設計演算法。我們維護兩個集合 \(U\) (已使用)跟 \(A\) (可使用),初始均為空集合,另維護一個計數器 \(c\),初始為 \(0\),並從左到右開始塗區間的顏色。
觀察一下塗色情形需要處理的只有區間的左右兩端點。由左向右處理這些點,如有一區間左右端點相同,則先處理左端點。如果處理到左端點, \(A\) 不是空集合,就將 \(A\) 中編號最大的塗給該區間,並將該顏色加入 \(U\)。\(A\) 為空集合,則將 \(c\) 加一,將 \(c\) 這個顏色塗上該區間,並將 \(c\) 加入 \(U\)。如果處理到右端點,則代表該區間已經結束,自此之後可以使用該顏色,將該區間所塗的顏色加入 \(A\)。有興趣的同學,可以證明看看這樣做可以保證 \(c\) 值(也就是使用到的顏色數量)永遠不會超過 \(k^*\) (最佳解的下限),換言之這樣就是最佳解。
綜上可知如果我們有所有左右端點排序好的資料,便能在 \(O(n)\) 的時間內完成本題所需的計算。只要各位有排序工具,便能在 \(O(n\log n)\) 的時間內完成排序,這是本題真正的時間瓶頸。最後需要留意的,是端點的範圍,用 int
是無法好好儲存的,請各位使用適當的資料型態。
題意是給定需多排成一排的硬幣,依據一個給定的演算法,將三個硬幣融合升級為一個硬幣,直到無法進行時,還剩下多少個硬幣。
這個題目看似簡單,不過執行的時限卡的相當緊。如果使用一個陣列搭配 Run-length Encoding 來維護這些硬幣,那麼每次融合硬幣之後,都需要將後方的硬幣向前推移,並把新融合出的硬幣接在最後方,如此一來,每次操作所需要的時間將會是 \(O(n)\) ,並且至少前 \(\frac{n}{2}\) 的操作,至少需要 \(\Omega(n)\) 的時間,在本題的輸入規模下,這肯定要 TLE 。因此,必須選擇適當的資料結構來實作。第一種比較直覺的做法是採用每個操作只需要 \(O(1)\) 的 Linked list。不過 Linked list 牽涉到位址可能不連續的記憶體存取,以及需要花時間 dereferencing ,效率並不是太好。在現代的計算機結構下,通常我會推薦 C++ 開發者使用 queue
跟 vector
分別實作一個儲存可能還會發生新的融合的硬幣 (用 Queue 存) ,跟已經確定不會在前面這段找到新的融合可能的硬幣 (用 Stack 存),以連續的記憶體儲存資料,發揮快取記憶體的效能。至於 Java 開發者,我則建議各位可以使用 ArrayDeque
。
題意是有一個大圓(外層圍籬)包覆一個邊不自交多邊形(內層圍籬)。給定大圓周長以及多邊形的各邊長度這兩個形狀滿足一些性質,要求介於兩者之間的面積,即兩者面積差。
首先由題目敘述得知,多邊形的頂點與大圓的距離均相等,據此可以推斷出,所有頂點都在一個跟大圓共用圓心的小圓邊界上,因此多邊形是個圓內接多邊形。只要能夠算出小圓半徑,便可以用三角形分割算出多邊形面積,再回推答案是多少。
當我們討論一個圓內接多邊形的外接圓半徑時,有幾個情況要注意。外接圓的圓心可能會在多邊形內、多邊形上、多邊形外。將多邊形的邊當作外接圓的弦時,所對應的圓心角定為 \(\theta_1,\dots,\theta_n\),不失一般性的我們假定 \(\ell_n\) 最長,而對應的 \(\theta_n\) 最大。如圓心在多邊形內,則等式 \(\theta_1+\cdots+\theta_n-2\pi = 0\) 成立。如圓心在多邊形外,則等式 \(\theta_1+\cdots+\theta_{n-1} -\theta_n= 0\) 成立。如圓心在多邊形邊上,則兩個等式均成立。
由於我們並不知道外接圓半徑為何,我們可以觀察當把這些邊當作弦放在一個半徑為 \(r\) 的圓內,所對應到的圓心角分別為 \(\tau_1(r),\dots,\tau_n(r)\),其中 \(\tau_i(r)=2\sin^{-1}\left(\frac{\ell_i}{2r}\right)\) 。我們能夠拿來用的圓半徑 \(r\) ,最小只能是最長邊的一半,即 \(\frac{\ell_n}{2}\)。讓我們定義 \(f_1(r)=\tau_1(r)+\cdots+\tau_n(r)-2\pi\) 及 \(f_2(r)=\tau_1(r)+\cdots+\tau_{n-1}(r)-\tau_n(r)\) 兩個函數。請留意 \(f_1(r)=0\) 與 \(f_2(r)=0\) 分別對應到前段所述的兩個等式,且 \(f_1\left(\frac{\ell_n}{2}\right)=f_2\left(\frac{\ell_n}{2}\right)\) 。\(f_1\) 顯然是個單調遞減的函數,因為隨著圓半徑變大,所有的角都會變小,如果 \(f_1\left(\frac{\ell_n}{2}\right)=f_2\left(\frac{\ell_n}{2}\right)>0\),我們可以透過二分法對 \(f_1\) 進行勘根,找到 \(r\) 使得 \(f_1(r)\approx 0\),如是外接圓心在多邊形內的情形,這即能找到答案。而 \(f_1\left(\frac{\ell_n}{2}\right)=f_2\left(\frac{\ell_n}{2}\right)<0\) 時,因為 \(f_2(r)\) 是一個的特別的函數(請見補充),直接對 \(f_2(r)\) 做二分法即可勘出根的近似值,即找到 \(r\) 使得 \(f_2(r)\approx 0\),進而求出答案。當 \(f_1\left(\frac{\ell_n}{2}\right)=f_2\left(\frac{\ell_n}{2}\right)=0\) 時,就直接用 \(r=\frac{\ell_n}{2}\) 找答案了。
由於我們討論的 \(r\) 至少是 \(\frac{\ell_n}{2}>0\) ,因此在本題討論的範圍內,對任意正數 \(p\) ,可保證 \(r^p\cdot f_2(r)\) 跟 \(f_2(r)\) 同號。如有一正數 \(p\) 使得 \(r^p\cdot f_2(r)\) 具有單調遞增特性,則 \(f_2(r)\) 可以利用二分法勘根。由於 \(f_2(r)\) 是由一些反正弦函數所線性組成,先考慮反正弦函數的 McLaurin series:
\[\sin^{-1}(x)=c_0+c_1x+c_2x^2+c_3x^3+\cdots+c_jx^j+\cdots\]
其中當 \(k\in\mathbb{N}\cup\{0\}\) 時, \(c_{2k}=0\) 、 \(c_{2k+1}=\frac{1\cdot 3\cdot\cdot\cdot\cdot\cdot (2k-1)}{2\cdot 4\cdot\cdot\cdot\cdot\cdot (2k)}\cdot\frac{1}{2k+1}>0\) 。由 McLaurin series 在 \(|x| \le 1\) 時才能成立,而我們討論的 \(r \ge \frac{\ell_n}{2}\),可知在我們討論的範圍內:
\[\begin{array}{rcl}
r^p\cdot f_2(r)&=&r^p\cdot\left(\left(\sum\limits_{i=1}^{n-1}\sum\limits_{j=0}^{\infty}c_j\left(\frac{\ell_i}{2r}\right)^j\right)-\sum\limits_{j=0}^{\infty}c_j\left(\frac{\ell_n}{2r}\right)^j\right)\\
&=&\sum\limits_{j=1}^\infty \frac{c_j}{2^j}(\ell_1^j+\cdots+\ell_{n-1}^j-\ell_n^j)r^{p-j}
\end{array}\]
而 \(r^p\cdot f_2(r)\) 對 \(r\) 之導函數為:
\[\begin{array}{rcl}
\left(r^p\cdot f_2(r)\right)'&=&\sum\limits_{j=1}^\infty \frac{c_j}{2^j}(p-j)(\ell_1^j+\cdots+\ell_{n-1}^j-\ell_n^j)r^{p-j-1}
\end{array}\]
只要存在一個 \(p\) ,使得對所有正整數 \(j>0\),\((p-j)(\ell_1^j+\cdots+\ell_{n-1}^j-\ell_n^j)\ge0\) 均成立,加上上式中有一項非零即可證明 \(r^p\cdot f_2(r)\) 單調遞增。將 \(\ell_1^j+\cdots+\ell_{n-1}^j-\ell_n^j\) 視作一個自變數為 \(j\) 的函數 \(g(j)\)。此時 \(\ell_n\) 是外接圓心在外之圓內接多邊形的最長邊長,不可能有其他邊一樣長,由指數增長特性,最終 \(\ell_n^j\) 的成長速度,會超過 \(\ell_1^j+\cdots+\ell_{n-1}^j\) 的總和。假定 \(g(j^*)=0\) 且 \(j^*\) 為 \(g\) 最小的根,此時 \(\ell_1^{j^*}+\cdots+\ell_{n-1}^{j^*}=\ell_{n-1}^{j^*}\),然而 \(j=j^*+\delta\) 且 \(\delta>0\) 時,左手邊最多成長 \(\ell_{n-1}^\delta\) 倍,而右手邊成長 \(\ell_n^\delta\),這代表 \(g(j^*+\delta)<g(j^*)=0\),不會再回頭了。讓我們取 \(p=j^*\),即可保證對所有正整數 \(j>0\),\((p-j)g(j)=(p-j)(\ell_1^j+\cdots+\ell_{n-1}^j-\ell_n^j)\ge0\) 均成立。再觀察由於多邊形的邊受三角不等式限制 \(\ell_1+\ell_2+\cdots+\ell_{n-1}>\ell_n\),這保證了 \(g(1)>0\) ,因此 \(p=j^*>1\) ,證得 \(\frac{c_1}{2}(p-1)(\ell_1+\ell_2+\cdots+\ell_{n-1}-\ell_n)r^{p-2}>0\),保證 \(r^p\cdot f_2(r)\) 在 \(r\ge \frac{\ell_n}{2}\) 時單調遞增。
綜合上述結論與「\(r^p\cdot f_2(r)\) 跟 \(f_2(r)\) 同號」,我們可知 \(f_2(r)\) 可以透過勘根定理,找出唯一根。要證明一性質成立比寫出會AC的程式碼困難許多,只要相信這題的根唯一,就可以進行二分法勘根。
題意是給定一個函數的遞迴定義,請計算特定的函數值。以下是命題者給的提示。
假設 \(p\) 代表一質數,則可藉由題敘可得到當 \(0 \leq x \leq i\) 時, \(f(i,x,p) \equiv \binom{i}{x}~(\mbox{mod } p)\)。
證明步驟:
題意是給定至多十萬個數字,以及總數至多十萬個的查詢(目前前K大的數字)與修改指令(將全部的數字對 X 做 XOR 後排序),請輸出所有查詢的結果。
命題者表示:「我覺得我那題看標程比較好懂就是…」
題意是給一棵樹和至多十萬個的查詢。每次詢問一個點集內任兩點的距離總和。
如果題目中只有一筆詢問,則可以輕易地用動態規劃解決。
考慮一個大小為 \(k\) 的詢問點集,我們其實可以把所有該詢問中關心的點抽出來,賦予適當的邊權後形成一棵等價的「虛樹」。而關心的點則由詢問點集與詢問點集中任兩點之 LCA 所組成。不難證明關心點集的大小不超過 \(2k\),因此每次在虛樹上做動態規劃即可。
基於 LCA 與 RMQ 的等價轉換,將詢問點集按照 DFS 序排序後,相鄰兩點之 LCA 集合即為任兩點之 LCA 集合,因此我們可以快速地找出關心點集。
本作法可以處理強迫在線版的題目。
由於本題並沒有強迫在線回答詢問,我們先存下所有詢問,之後使用常見的樹上計數技巧如啟發式合併或樹分治亦可以解決本題。