※ 引述《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