這回題目比往常多, 一共十題, 紅色跟綠色氣球各兩題 (好像有分透不透明, 但看不太出來). 這次比賽從比賽開始我就沒什麼時間概念, 沒去注意幾分開始, 也沒去看剩多少時間. 一開始讀題分配, 我讀前三題. 高奕豪中間幾題, 王尹後幾題. 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 決定 問走到終點的順序 B 幾何題, 給平面上的多邊形(各邊平行於兩軸), 問最大可以放多大的圓形在多邊形內 王尹提出類似基因演算法的做法, 撒點找出比較大的幾個, 把兩個大的中點當做新的點. 這是假設最大的幾個圈會在一起. 我想把圓的組成分 case 討論: 三點, 二點一邊, 二角邊一點, 二平行邊 應該是能慢慢做, 不過實在滿煩的 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 是錯的. H 簡單的幾合題, 王尹寫的. 給 n<=100 條平面上的道路(線段). 要在上面種樹, 每棵樹間距至少 50 公尺. 樹距離路口至少 25 公尺. 題目保證都是四叉路口, 也不會有精確度問題. I 高奕豪寫的, 數學問題 J 也是麻煩的幾何問題. 給平面上的雷達站(沒給位置)掃到幾架飛機, 給雷達站掃描範圍圓形的其中兩點, 以及飛機座標. 問被 k 個雷達站掃到的飛機有幾架 每個圈已知兩點, 依半徑做 binary search, 使用題目的 rule 做 tie break -- "聲音是聲音, icon 是 icon, 用 icon 來表示聲音的結果, 就是不知道哪個是聲音, 哪個是 icon. " 小光光 --

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