柊四千的倉庫

發表文章

110 學年度全國資訊學科能力競賽各題詳解

2月 05, 2022

筆者這次也參與了全國賽的驗題，這邊放一份另一位驗題者與筆者提供的詳解。題本的連結在這裡，pC / pE / pH / pI 的時間限制分別為 2.5s / 2.5s / 2.0s / 0.1s，其餘題目皆為 1.0s。另，讀者也能在這裡找到與下文基本相同的內容。 A. 髮廊服務優化問題 (barbershop) 有

$n$ 個人一起來店，第

$i$ 個人的服務時間為

$t_i$ 。每個客人等待時間是前面人

$+$ 自己服務時間總和，求等待時間總和的最小值。例如：三個人服務時間為

$2,1,3$ ，若服務順序為

$1,2,3$ 則等待時間總和為

$2 + (2+1) + (2+1+3) = 11$ 。等價題序：給一個陣列

$\mathbf{t} := \{t_i\}_{i=1}^n$ ，將

$\mathbf{t}$ 重新排列使得

$nt_1 + (n-1)t_2 + (n-2)t_3 + \ldots + t_n$ 最小。由上式不難得知，順序越前面被乘的係數就越大，所以可以貪心地將數字從小排到大。複雜度

$O(n \log n)$ 。 B. 校園公車 (bus) 給定由

$n$ 條線段組成的折線

$\mathbf{P} := \left\{ \overline{P_i P_{i+1}} \right\}_{i=1}^n$ 與一點

$O$ ，問

$O$ 到

$\mathbf{P}$ 的最短距離。先考慮這個問題：給定一線段

$\overline{PQ}$ 與一點

$O$ ，求

$O$ 到

$\overline{PQ}$ 的距離。首先我們作

$O$ 到

$\overline{PQ}$ 的垂足

$H$ ，並試著計算

$\overline{OH}$ 。注意

$\overline{OH}$ 其實就是

$\Delta OPQ$ 以

$\overline{PQ}$ 為底時的高，所以可以用下面的方法計算： Length_OH(O: Point, PQ: Segment): A ← ΔOPQ return 2A/|PQ|

$\Delta OPQ$ 可以用 Shoelace formula 計算。但事情沒有這麼簡單。

$O$ 到

$\overline{PQ}$ 的距離並不總是

$\overline{OH}$ ：當 $\angle OPQ...

閱讀完整內容

2020 全國賽驗題心得

1月 01, 2021

筆者參與了本屆全國賽的驗題。驗題工作包含修正題目敘述與訂定時間限制，並總是要於必要時重出測試資料，前後花了一個多月才完成。讀者可以把這篇文章當作上篇題解的幕後花絮，簡單了解比賽題目是怎麼產生的，以及有哪些有趣的事情發生。由於筆者花最多時間在驗 pG 上，pG 會佔大部分的篇幅，還請見諒。 A. 礦砂採集由於排序的

$\Theta(n\log n)$ 和 quickselect 的

$O(n)$ 以比賽來說難以區分，一開始就只預期參賽者用排序 AC。一度想過是否把

$n$ 的上限拉到

$10^5$ 卡

$\Theta(n^2)$ 排序，想說這題就是個簽到題就算了，可惜仍有參賽者未能拿到滿分。 B. 村莊與小徑看到 scoreborad 有人卡在最後一個 subtask，有點好奇究竟是單純的 bug 還是堅信 SPFA 的時間複雜度是

$O(kE)$ 而狂傳。大概在

$10$ 年前，筆者還在打 TOI 的時候，簡體中文網路上就流傳著 SPFA 時間複雜度只有

$O(2E)$ ，快到可以作為 general 最短路徑演算法的都市傳說。筆者並不清楚為什麼許多中國人認為 Dijkstra 比 SPFA 難寫（筆者覺得正好相反）導致即使可能 TLE 也要寫 SPFA，不過總之請記得，如果一個題目能用 DAG 上 DP 或 Dijkstra 過，請不要用 SPFA。 C. 樣本解析這題的交集關係部分寫得很繁瑣，但我們沒有辦法。本來打算用

$\subset$ 表示 proper subset，實際上也有

$\subseteq$ 這個符號，筆者認為就像

$<$ 和

$\leq$ 一樣，不應有混淆的空間；然而偏偏有些作者在用「

$A \subset B$ 」時，允許

$A = B$ ，可能導致參賽者混淆而放棄。也考慮過改用

$\subsetneq$ 符號，但這跟

$\lneq$ 一樣相對罕見，考慮參賽者都是高中生很可能看不懂，只好全部改用中文敘述。 D. 水果包裝筆者第一次看到題目後，在紙上推敲了許久（

$30$ 分鐘有）才得出 greedy 結論，很意外這題的答題狀況這麼好，好奇到底有多少人是用猜的。不過有一等獎參賽者沒能拿到滿分，用心出

$n$ 的數量級

$10^5$ 的測資也有了價值 (? 原先這題

$n$ 的上限只到 $100...

閱讀完整內容

筆者參與了這屆全國賽的驗題，也出了 pD 與 pG 的所有測試資料。由於現場講解有些不夠明確，故在這邊放一份兩位驗題者與筆者提供的詳解。題本的連結在這裡，pE / pF / pG / pH 的時間限制分別為 2.0s / 2.3s / 6.5s / 0.1s，其餘題目皆為 1.0s。 A. 礦砂採集這題是很典型的連續背包問題。結論非常簡單：只要不斷貪婪地將單位重量價值最大的礦砂放進背包，直到背包已滿或所有礦砂均已被放入，就能最大化總價值。一個簡單的做法是將所有礦砂依照單位重量價值由大到小排序，依序放入背包直到滿即可。複雜度是

$O(n \log n)$ 。線性做法雖然並不是本題的考點，但有一個值得一提的

$O(n)$ 做法存在。以下為了方便說明，假定所有的

$x_i$ 均相異。隨機選擇一個礦砂

$i$ ，並將所有的礦砂分為單位價值

$\ge x_i$ 與

$< x_i$ 兩堆。分歧判斷：若單位價值

$\ge x_i$ 的礦砂可以塞滿背包，則將

$< x_i$ 的礦砂全刪除，並往大的

$x$ 找答案。反之則將價值

$\ge x_i$ 的礦砂全刪除，往小的

$x$ 找答案。搜尋完後得到的值代表「總價值最大時，背包中單位重量價值最小的礦砂」，再用這個價值去反求答案。演算法與 quickselect 非常相似，期望時間複雜度為

$O(n)$ 。 B. 村莊與小徑這題是一道最短路徑的問題，但給定的限制中有幾個點要注意：給定的圖是 DAG（有向無環圖）。邊權可能是負的。條件 1 保證這張圖存在拓樸排序，求解可用 top-down DP，或找出拓樸排序後用 bottom-up DP。 // ord = 拓樸排序的點順序 // fr[x] = 連到 x 的所有點 fill(dis, dis+n+ 1 , INF); dis[ 1 ] = 0 ; for ( int i= 1 ; i<=n; i++) { int p = ord[i]; // 找所有能連到 p 的點 j，更新 p 的最短距離 for (Edge j: fr[p]) dis[p] = m...

閱讀完整內容

模 p 下的平方根: Cipolla 演算法

10月 17, 2020

設

$p$ 為質數且

$a \in \mathbb{Z}$ 。考慮問題：是否存在

$r \in \mathbb{Z}$ 使得

$r^2 \equiv a\ (\operatorname{mod}p)$ ？如果這樣的

$r$ 存在，有沒有好的方法找？如果第一個問題的答案是肯定的且

$p\nmid a$ ，我們說

$a$ 是

$p$ 的二次剩餘 (quadratic residue)；如果第一個問題的答案是否定的，則說

$a$ 是

$p$ 的二次非剩餘 (quadratic nonresidue)。當

$p = 2$ 或

$a \equiv 0$ 時上面兩個問題都是 trivial；以下假定

$p \geq 3$ 且

$a \not\equiv 0$ 。透過觀察

$x^2-r^2 = (x-r)(x+r)$ 且

$r \neq -r$ ，我們發現

$a$ 可以寫成

$r^2$ 若且唯若方程式

$x^2-a = 0$ 在

$\mathbb{Z}_p$ 下恰有兩相異根。這代表恰有

$\frac{p-1}{2}$ 個

$\mathbb{Z}_p^\times$ (

$\mathbb{Z}_p$ 的乘法群) 裡的元素能被開根號，而另外

$\frac{p-1}{2}$ 個

$\mathbb{Z}_p^\times$ 裡的元素不能被開根號。又，費馬小定理指出，對於所有的

$x \in \mathbb{Z}_p^\times$ ，均有

$x^{p-1} -1 = (x^\frac{p-1}{2}-1)(x^\frac{p-1}{2}+1) = 0$ 若

$a = r^2$ ，則

$a^\frac{p-1}{2}-1 = r^{p-1}-1 = 0$ 。因為方程式

$x^\frac{p-1}{2}-1 = 0$ 最多只能有

$\frac{p-1}{2}$ 個根，我們得到了以下的定理： [定理] 設

$p \geq 3$ 為一奇質數且

$a \in \mathbb{Z}_p^\times$ ，則

$a$ 是

$p$ 的二次剩餘若且唯若

$a^\frac{p-1}{2} = 1$ 。

$a$ 是

$p$ 的二次非剩餘若且唯若

$a^\frac{p-1}{2} = -1$ 。至此第一個問題

$O(\log p)$ 時間複雜度圓滿解決。為了接下來的討論方便，這邊介紹勒讓德符號 (Le...

閱讀完整內容

(Debug) TIOJ 1752 妹妹的汽水

7月 03, 2018

Description 雖然經歷了這場讓人魂飛魄散的事件，但是經過護士姊姊細心診斷確定他的人及屬性都沒受創之後，妁艷回到了家。隔天去了學校，學習了更多技能之後發現身體感覺並沒有什麼異狀。可是體內感覺卻有股蠢蠢欲動的力量……。回到了家，突然想到昨天妹妹借的書還沒還給他，就去找妹妹。可是，妁艷在門外叫了好幾聲都沒反應，他就逕自進入妹妹的房間。「喔哈哈！」進來之後發現妹妹不在，妁艷不自覺的笑了。他開始尋找目標物，從書櫃、抽屜、書包、床鋪、衣櫃等等地方仔細搜索之後，終於在書桌上找到了那本書。「奇怪？」書上放著一張紙條，使妁艷有點疑惑，上面寫著：「

$2, 3, 5, 7, 11, 13, 17, \ldots$ 。」聰明的妁艷當然一看又知道是一串質數。找的口有點渴的妁艷，拿起桌上喝了一半的汽水準備一飲而盡，猛然發現蓋子竟然打不開，而且瓶蓋上還印了一個正整數

$n$ 和一個質數

$p$ ，仔細一看他才發現紙上還寫了：「打開汽水需要找出第

$p$ 個冒出的泡泡編號。」為了喝到汽水，妁艷研究出了這種汽水冒泡的規律。泡泡原本的順序是

$n$ 到

$1$ ，也就是

$n, n-1, n-2, \ldots, 3, 2, 1$ 。從時間

$t=0$ 開始每秒會有些泡泡跟其他泡泡位置交換。奇妙的是，它們都遵守第

$t$ 秒內時只有被編號第

$t$ 個質數

$q$ 整除的泡泡才可能變位置。第

$t$ 秒內，對第

$i$ 個被

$q$ 整除的泡泡編號

$a$ 會跟第

$i+1$ 個被

$q$ 整除的泡泡編號

$b$ 比大小，如果

$a$ 大於

$b$ ，泡泡

$a$ 和

$b$ 就會交換位置，

$a$ 繼續跟第

$i+2$ 個比，否則用

$b$ 跟第

$i+2$ 個比。泡泡最後的位置順序的倒序就是冒泡順序。例如

$n=8$ ，

$t=0$ 時，順序是

$8, 7, 6, 5, 4, 3, 2, 1$ 。

$t=1$ 時，順序是

$6, 7, 4, 5, 2, 3, 8, 1$ 。(

$8$ 跟

$6$ 換、

$8$ 跟

$4$ 換、

$8$ 跟

$2$ 換且

$2, 4, 6, 8$ 都被

$2$ 整除)

$t=2$ 時，順序是

$3, 7, 4, 5, 2, 6, 8, 1$ 。(

$6$ 跟

$3$ 換且

$3, 6$ 都被

$3$ 整除) ...

閱讀完整內容

NTUJ 1697 Ancestors

6月 30, 2018

Description You will be given a connected undirected tree. Each node will have an associated integer that we will call its value. We also define the value of a subset of nodes as the sum of values of the nodes in the subset. Consider the subsets of nodes of this tree whose size is between

$1$ and

$K$ , inclusive, and satisfy the property that within each subset no node is an ancestor of another. We will call these subsets the

$K$ -anti-ancestral subsets of the tree. Your task is, given the tree, to find the

$K$ -anti-ancestral subset of maximum value. As an example, consider the tree below. Each node is named with a capital letter and the value of each node is the integer below the letter: Suppose

$K = 3$ . Then the subset of nodes

$\{A\}, \{B, E\}, \{C, E\}, \{D, G\}$ and

$\{B, E, F\}$ are some of the

$K$ -anti-ancestral subsets of the tree, because they all have between

$1$ and

$K = 3$ nodes and within each subset there doesn't exist a pair of nodes such that one is ...

閱讀完整內容

搜尋此網誌

柊四千的倉庫

發表文章

由14個點組成的5-正則圖必不是平面圖

110 學年度全國資訊學科能力競賽各題詳解

2020 全國賽驗題心得

109 學年度全國資訊學科能力競賽各題詳解

模 p 下的平方根: Cipolla 演算法

(Debug) TIOJ 1752 妹妹的汽水

NTUJ 1697 Ancestors