這回題目比往常多, 一共十題, 紅色跟綠色氣球各兩題
(好像有分透不透明, 但看不太出來).
這次比賽從比賽開始我就沒什麼時間概念, 沒去注意幾分開始, 也沒去看剩多少時間.
一開始讀題分配, 我讀前三題. 高奕豪中間幾題, 王尹後幾題.
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