[UVa] Sixth Contest of Newbies

Links：

• 賽事題目 / Scoreboard
• UVa OJ 題目 (UVa 11909~11914)

余以為絕對是值得花時間做的一SET題目...

題目質素高
時限相當緊
Test Data 亦相當狠 (很多 set...)
(題目也相當 "陰"...)

雖然具備基本知識，理論上新手都可以解出起碼三題
不過... 這都包含相當多細節，不是一般的題目呀...

---

題解概要：

A: Soya Milk - 簡單2D幾何
分兩種情況：水平線 touch length/height

B: Closest Fractions - 枚舉
Contest 時 RP較高
預處理GCD後 O(1000^2) 暴試 0.9xx sec 水過了

陰位：題目要求輸出 exactly 10個有效數字
具體方法... 把input以string讀入，然後直接輸出

C: Farther or Closer - 模擬 / 窮舉
O(100^3) 檢查已知資訊... 在剩下的 choice 當中依給定算法選 最大/最小

題目提到 "which works quite pleasingly in many cases"

Debug 時發現其中一組隨機數據跑了好多個 iteration... 此項資訊直接幫助了 Debug...

D: Chutes and Ladders - 期望值 → 高斯消元

1. BFS 判定第一個輸出 以及 "Bad die!"
2. 定義 X[i] := 在第 i 格抵達終點的期望步數
   高斯消元 求解
   

小心的細節包括:

• 出題者 Hint → 擲出 Dice 其中一面的 probability 有可能是 0
• "If a move takes the player beyond the square 100, this move is ignored and the token is not moved."

由於做過極之類似的題目 (POJ 3756)

便一眼看出是 Gaussian Elimination
(但要小心處理的地方很多... 所以contest 時毅然放棄)

(從出題者 implementation 的 runtime 看... 或者他有其它解法)

E: Tape Recording - (經典?)動規
較慢的 O(N^3) 動規

1. (先把離散化時間點)
   把節目按完結時間遞升排列
2. 定義：DP[K][TimeA][TimeB] :=
   用 Tape A 的 [0..TimeA] 及 Tape B 的 [0..TimeB] 時間
   錄影第 {1,2...K} 當中某些節目
   所得到之 Maximum Fun

另一個可行算法是 最小費用最大流

陰位：節目時間可以超過 00:00 (其實自己大意)
但從 runtime 看我的 implementation 貌似很慢... 存在更好的算法吧?

F - An Amazing Race - 狀態DP + 字典序最小最短路
題目包含相當多的細節

Contest 時一個地方想錯了：當需要由 P住Q 時
必然是選取 P往Q 的「字典序最小最短路」 (下簡稱為「最短路」)

1. 二分查找 D 的 minimum value：
   D := "maximum distance between two consecutively visited water-supplying spots"
2. 計算所有 P→Q 的「最短路」：
   條件：「最短路」需要乎合 "maximum distance between two consecutively visited water-supplying spots" <= D
3. 動規：
   DP[Set][X] := 以 S 為起點，已經過 Set 當中的 Vertex，目前身處 Vertex X 的「最短路」
   (Set 為 vertex集 的 subset)

1. 可以用 圖遍歷 / 類似 MST 的方法求出
2. 可以由 BFS → Floyd 求出
3. 是經典 DP：用 exponential memory/時間 解 TSP 問題

狀態DP 部份 或可以 最短路算法 取代

WA的朋友或可以參考以下的 Case:

• ##T##
  A###B
  ##S##