Re: world final 賽記
※ 引述《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
討論串 (同標題文章)