※ 引述《smartboy (小光光)》之銘言： : 這回題目比往常多, 一共十題, 紅色跟綠色氣球各兩題 : (好像有分透不透明, 但看不太出來). : 這次比賽從比賽開始我就沒什麼時間概念, 沒去注意幾分開始, 也沒去看剩多少時間. : 一開始讀題分配, 我讀前三題. 高奕豪中間幾題, 王尹後幾題. : A 我只大概了解題目, 但跟 sample data 湊不起來. : B 跟 C 的題目很快就讀完, 一時不覺得能做. : 跟隊友了解一下其他題, E 是簡單題, 王尹就上機寫. 然後我看了 H 的題目. : 題目也滿容易理解的. 在王尹後, 高奕豪寫 I, 但寫一寫下來導些式子, 讓王尹上 H. : 我則是在紙上簡單規畫 C 的寫法. 然後我上 C, 寫得滿久的, 還沒有人能上, : 我也就上機 debug. 我寫出 C 後讓王尹上 F, 高奕豪的 I 跟王尹的 F 交錯. : 王尹看懂 A 的意思. 在王尹上 F 時, 我規畫了 D 的解法,並想了 B, J 兩題. : 前幾題對時我有看一下 scoreboard, 我們約在前十. : 當我們四題時 scoreboard 停止更新, 我們暫居第二. 停止更新後不久王尹對了 F. : 然後我寫 D, 第一次 time limit, 做了一些加速及 cut, 變成 wrong answer. : 在我修正期間, 王尹高奕豪兩人合力上機解 G. : 到比賽結束時 G 連 sample 還沒辦法對, 我也沒看出我的 bug 在哪. 我猜應該是終止條件的英文解讀問題. : 綜合起來, 這次的題目雖然有十題, 但多不是經典的演算法題目或其應用 : 滿多幾何、數學、枚舉一類的題目 : A 有些煩模擬題, 全場沒有人對. 我們這隊沒寫 : 一隊螞蟻在平面上依給定的軌跡(平行於兩軸)定速前進, : 若遇到路口或相撞, 依題目的 rule 決定 : 問走到終點的順序 Discrete event simulation (DES). 通常是用一個generic simulation engine處理事件. DES 包括一個event queue, 一個clock, 及一堆event insertion/deletion rules. : B 幾何題, 給平面上的多邊形(各邊平行於兩軸), : 問最大可以放多大的圓形在多邊形內 : 王尹提出類似基因演算法的做法, 撒點找出比較大的幾個, 把兩個大的中點當做新的點. : 這是假設最大的幾個圈會在一起. : 我想把圓的組成分 case 討論: 三點, 二點一邊, 二角邊一點, 二平行邊 : 應該是能慢慢做, 不過實在滿煩的 有沒有可能推論出圓心一定是 X.0 或 X.5? : C 給定方塊堆出來的形狀其六個投影面看到的顏色, 問最多可以有幾個方塊 : 最大 10x10x10 : 我的做法, 對於任一點是否滿足各方向的顏色條件, 若不符合則挖空, 直到穩定為止. : D 題目給一個字串 encode 的方式, 要我們 decode. : encode 方式有點像 Joseph problem : 原本是數幾人一殺, 改成數幾空格填一字. : 先把 string 用 (s,i) 填一次 (s 開始, 每數 i 個空格填一次). : 相同字串再用 (t,j) 填一次. 剩下的亂填. 問最長可能. 若多解得說有多解. : 我的想法是窮舉 (len,s,i,t,j), 一開始會 time limit exceeded. : 我改成 length 由大到小, 找到就跳出, : 還有檢查找出第一個 word 後, 字母數是否還夠用. 這樣速度就夠快了. : 不過還不肯定為何 wrong answer. 見前面. : E 最簡單的題目, 給兩個 set of date range, 問兩個 set 的差(相減). : 這題王尹做的, 窮舉每個日期. : 還有 cache 最後一個 constraint, 優先檢查, 藉此加速. : F 有些煩的依 rule search 題, : 給定拼圖的拼塊, 上頭有些字母, 剩下的透明. : 字母相疊或疊到透明的上面算分分數不同, 方塊 shift 多少疊合分數也不同. : 要求分數最高的拼法. 這題王尹寫的 : G 最後王尹跟高奕豪一起寫的. 但還差一些, 寫完但 sample 是錯的. 這題似乎不難, 但幾何條件可能很煩. 下次要把更多幾何公式加進 notebook. :-) (教練會議的共識是下次還會用 notebook) : H 簡單的幾合題, 王尹寫的. : 給 n<=100 條平面上的道路(線段). 要在上面種樹, 每棵樹間距至少 50 公尺. : 樹距離路口至少 25 公尺. 題目保證都是四叉路口, 也不會有精確度問題. : I 高奕豪寫的, 數學問題 : J 也是麻煩的幾何問題. 給平面上的雷達站(沒給位置)掃到幾架飛機, : 給雷達站掃描範圍圓形的其中兩點, 以及飛機座標. : 問被 k 個雷達站掃到的飛機有幾架 : 每個圈已知兩點, 依半徑做 binary search, 使用題目的 rule 做 tie break 希望各位在今年的分站賽及明年的決賽繼續努力. -- 台灣大學資訊工程系 劉邦鋒 -------------------------- 合理的作業是訓練，不合理的作業是磨練。 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.28.27