Re: world final 賽記
※ 引述《pangfeng (Ikari Gendou)》之銘言：
: ※ 引述《smartboy (小光光)》之銘言：
: : B 幾何題, 給平面上的多邊形(各邊平行於兩軸),
: : 問最大可以放多大的圓形在多邊形內
: : 王尹提出類似基因演算法的做法, 撒點找出比較大的幾個, 把兩個大的中點當做新的點.
: : 這是假設最大的幾個圈會在一起.
: : 我想把圓的組成分 case 討論: 三點, 二點一邊, 二角邊一點, 二平行邊
: : 應該是能慢慢做, 不過實在滿煩的
: 有沒有可能推論出圓心一定是 X.0 或 X.5?
No.
(0,0)
+------+
| |
| + |
+------+ 其中 + 那點的位置在 (a,a)
設圓心在 (r,r)
則 sqrt(2)*r + r = sqrt(2)*a
r = (2-sqrt(2))*a
: : 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.
: 見前面.
(前面)
: : 到比賽結束時 G 連 sample 還沒辦法對, 我也沒看出我的 bug 在哪.
: 我猜應該是終止條件的英文解讀問題.
事實上我沒明講, 是希望有人會去看看題目之類的 ;)
在比賽時我就把題目讀了三四遍, 深怕漏掉什麼條件沒看到
比完賽我繼續拿 source code 反覆閱讀想看出問題在哪,
也解釋給隊友聽.
比完賽隔天睡前再讀一次, 覺得有句的英文意思我不太肯定.
Input for the last test case is followed by a line consisting of
letter X.
比賽當時我覺得要一行剛好是 "X" 才結束.
重看幾遍, 那 "AAAXAAA" 呢, "XXX" 呢
若問題真出在這裡, 真是太可惜了.
在賽後的檢討, 我覺得最後半小時兩人寫新題目,原來的人 debug 這策略不夠好.
也許該改成一人寫新題, 另一個人幫忙我 double check 我這題, 比較好.
(不過我們三人組隊賽前練習, 比較少練習到有人幫我 debug 這部分)
不過, 事後看來, 若真的是 input 問題, 恐怕當時有人幫忙看也看不出來.
: : G 最後王尹跟高奕豪一起寫的. 但還差一些, 寫完但 sample 是錯的.
感覺起來, 最後一小時連寫兩題, 一題寫完, 一題只差一點,
速度比我想像中還快一些 :)
前幾題花的時間略多了點.
: 這題似乎不難, 但幾何條件可能很煩. 下次要把更多幾何公式加進 notebook. :-)
: (教練會議的共識是下次還會用 notebook)
--
"聲音是聲音, icon 是 icon, 用 icon 來表示聲音的結果,
就是不知道哪個是聲音, 哪個是 icon. "
小光光
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.82
討論串 (同標題文章)