TIOJ 1284 賽車問題

Description

現在有 $n$ 輛往右邊跑的賽車，每一輛都有其固定的車速以及起始位置。
你是一位專業的攝影師，而你相信你的專業，順從你的渴望，你希望能夠抓準時機，一次把所有賽車通通照下來。
如果要把所有賽車通通照下來，那麼你的底片要夠長才行。
為了節省成本，你想要知道在所有時刻中，什麼時候最領先的車子跟最落後的車子的距離會最短。
手癢的你趕快來寫個程式求出最短距離吧！

Input Format

輸入的第一列有一個正整數 $n$ ($2\leq n\leq 100,000$)。
接下來有 $n$ 列，每列有兩個整數 $v_i, s_i$ 依序代表第 $i$ 輛賽車的車速(單位：公尺/秒)以及起始座標(向右為正，單位：公尺)。
($0\leq v_i, s_i\leq 1,000,000$)
噢對了，所有車子都位於不同的賽道，因此你不必考慮它們追撞的情形，也不用考慮車身的長度。
而且你可以假設所有車子的車速都不相同。

Output Format

請輸出所有時刻中(時間 $\geq 0$)，最前面的車子與最後面的車子之最小水平間距。
只要四捨五入輸出至小數以下第二位即可。

Sample Input

3
1 1
2 0
3 0

Sample Output

0.50

Solution

這題的 $n$ 實在太大，沒辦法枚舉所有的超車事件來求出答案。注意到答案只要求到小數下第 $2$ 位，可以考慮用近似解。設 $x_i(t)$ 為第 $i$ 台車在 $t$ 秒時的位置，則題目問的就是
\[f(t) := \max_{1 \leq i \leq n} x_i(t) - \min_{1 \leq i \leq n} x_i(t)\]
在 $t \geq 0$ 的最小值。觀察到 $x_i(t) = v_i(t) + s_i$ 既是 convex function 也是 concave function，所以
  1. $f_1(t) := \max_{1\leq i\leq n}x_i(t)$ 是 convex function。
  2. $f_2(t) := \min_{1\leq i\leq n}x_i(t)$ 是 concave function。
  3. $f(t) = f_1(t)-f_2(t)$ 是 convex function。
由 $0 \leq s_i \leq 10^6$ 與 $v_i$ 是整數，可知最小值必定能在 $t \in [0, 10^6]$ 找到。我們可以用三分搜尋法找出 minimizer，並在搜尋區間 $[l, r]$ 滿足 $r-l \leq \delta$ 時結束搜尋。最後，由 $0 \leq v_i \leq 10^6$，可知
\[|r-l| \leq \delta \Rightarrow |f(r)-f(l)| \leq 10^6\delta\]
由題目要求可知 $\delta$ 必須滿足 $10^6\delta < 0.005$，故可以取 $\delta = 10^{-10}$。這樣一來，三分搜次數就是 $T := \log_{3/2}10^{16} \approx 90.86$，而整體的時間複雜度是 $O(Tn)$，可在時間限制內解決。

我的 code：

留言

張貼留言

這個網誌中的熱門文章

2020 全國賽驗題心得

筆者參與了本屆全國賽的驗題。驗題工作包含修正題目敘述與訂定時間限制，並 總是要 於必要時重出測試資料，前後花了一個多月才完成。讀者可以把這篇文章當作上篇 題解 的幕後花絮，簡單了解比賽題目是怎麼產生的，以及有哪些有趣的事情發生。由於筆者花最多時間在驗 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...
閱讀完整內容

水母上 Divide-and-Conquer

圖片
一棵樹有「拔掉任一非葉節點便不連通」的良好性質，可以幫助我們用 DP 和 divide-and-conquer 解決問題，例如 POJ 1741 和 TIOJ 1647 。這篇假定你知道怎麼把 POJ 1741 做到 $O(n(\log n)^2)$ 的時間複雜度 (如果你不知道也沒關係，google "POJ 1741" 就有很多資料了 XD)。我們沿用 先前 的定義，把一張點數和邊數相等的連通近圖 ( pseudograph ) 稱作一隻水母。再次提醒，水母並不是正式名稱 (我找不到正式名稱 orz)。 考慮這個問題：給定一隻大小為 $n$ 的水母 $J = (V, E)$，邊有正權重，請求出 $J$ 的 $K$-近對個數。一個 $K$-近對的定義是距離不超過 $K$ 的 (無序) 點對。觀察到一隻水母其實是由頭部 (環) 和數條觸手 (樹) 組成。設頭部由點 $t_0, t_1, \ldots, t_{m-1}$ 組成，從 $t_i$ 長出的觸手為 $T_i$。我們把 $K$-近對 $(u, v)$ 分成兩種：$u, v$ 屬於同一條觸手 ($\alpha$ 型)、$u, v$ 屬於不同條觸手 ($\beta$ 型)。只要在每條觸手上跑 POJ 1741，就能求出 $\alpha$ 型 $K$-近對個數了。至於 $\beta$ 型，做法是對於每個點 $v$，統計有幾個點 $u$ 滿足 $u$ 和 $v$ 不在同一條觸手上 $u, v$ 的距離 $d(u, v) \leq K$ 我們用上圖來做說明。設邊 $(t_i, t_{i+1})$ 的權重為 $w_{i+1}$，$s_i := w_1 + \ldots + w_i$ 為「從 $t_0$ 開始，順著 $t_0, t_1, t_2, \ldots$ 的方向，走 $i$ 條邊的里程數」(為了方便，不該超過 $m-1$ 的那些索引值，一旦超過 $m-1$ 就自動對 $m$ 取模)。設 \[ \begin{cases} u \in T_j, d_u := d(u, t_j),\\ v \in T_i, d_v := d(v, t_i), \end{cases} \] 則 $d(u, v)$ 就是 $d_u+d_v+(s_i-s_j)$?! 當然我們沒有這麼好的事情，因為 有...
閱讀完整內容

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

筆者參與了這屆全國賽的驗題，也出了 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...
閱讀完整內容