这回题目比往常多, 一共十题, 红色跟绿色气球各两题 (好像有分透不透明, 但看不太出来). 这次比赛从比赛开始我就没什麽时间概念, 没去注意几分开始, 也没去看剩多少时间. 一开始读题分配, 我读前三题. 高奕豪中间几题, 王尹後几题. 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