※ 引述《smartboy (小光光)》之铭言： : Name Solved Score A B C D E F G H att/solv : 1 Wall 6 703 2/152 1/192 1/45 2/52 2/127 1/75 0/-- 0/-- 9/6 : 2 Better 6 1220 1/153 6/270 1/237 4/99 1/111 1/190 0/-- 1/-- 15/6 : 3 Escape 5 757 1/139 4/-- 1/71 2/43 3/166 3/238 1/-- 0/-- 15/5 : 4 NoName 4 464 2/261 1/-- 1/45 0/-- 1/58 1/80 0/-- 1/-- 7/4 : 5 ( ] 4 1119 0/-- 1/-- 4/244 2/239 1/237 2/299 0/-- 0/-- 10/4 : 6 Somi 3 734 0/-- 0/-- 1/71 5/250 0/-- 6/233 0/-- 0/-- 12/3 : 7 XDman 2 425 5/-- 0/-- 12/-- 3/271 4/-- 1/114 0/-- 0/-- 25/2 : 8 Mictor 1 180 0/-- 0/-- 2/160 0/-- 0/-- 0/-- 0/-- 0/-- 2/1 : 9 YSL 0 0 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/0 : Summary 11/139/4 23/45/7 12/58/5 1/--/9 95/31 : 13/192/2 18/43/6 15/75/7 2/--/0 这次是用 ACM ICPC 2001 Asia region, Taejon site (韩国) 练习 资料可以在网站上找到, 包括 test data, 以及当时的 standing http://icpc.baylor.edu/past/icpc2002/regionals/Taejon01/ http://cs.kaist.ac.kr/~acmicpc/standing.html 当时最多五题, 也就是说模拟赛的队伍跟当时比较成绩还不错 (当然不排除当时他们可能也有 rejudge 之类的事发生) 以下是我对这次模拟赛的一些 random note, * 比赛进行 ( ] 队在比赛开始一两个小时後才开始写, 因此 penalty 比较高 YSL 弃赛 比赛进行到一半, C 跟 F 两题 rejudge pc^2 server 是地下室的 acmclub server, 比赛中因不明原因 reboot 使得 submit/judge 停摆了约三四分钟 * 题目 详解就请各位发挥了 B 用 greedy 解, 谁能证明一下呢 F 似乎有两种 greedy 法, 其中一种做法跟 B 很像, 另一种据 ledia 说这题刚好符合某些条件, 刚好可以用 A, D, E, 大致上不难 G 我觉得善用 computational geometry 里常用的 doubly-connected edge list 就不难了, 只是我看大部分人都不熟这东西 H 是 vertex covering (NP-C 问题) 的一个变形, 我不确定还是不是那麽难, 各位可以验证一下. 我印象中我两年前写这题用的方法就是用递回穷举做的. 不过我一时想不起来当时可有什麽比较好的写法可供大家参考. * 解题流程与策略 由於 C F 两题 judge answer 有误, 打乱了不少队伍的解题过程, 我觉得可惜, 练习品质因此差了点. 不过反过来说让大家练习怎麽应付不完美的比赛. 每个比赛的队伍都很可能遇到类似的状况 - 明明程式看起来是对的, 不知为何 judge reply wrong answer. 无论是真的有 bug 或 judge 错了, 队伍仍要继续往前进, 也许是拨出一部份人力解新的题目, 或完全放下卡住的题目, 冲新的问题. 甚至你认为原来写法的确很容易错, 也许可以重写. 就是不要卡住不知道该怎麽办. 还有一个我常常提醒的是接近比赛尾声时, 常发现一队三人会有闲置的人力, 他可能就开始上网/打混/做其他事, 而非帮忙解题. 无论是题目快解完没新题目, 或时间快到放弃其他题, 都不应该浪费人力. 请发挥你们的想像力, 替闲置人力找到他可以帮上忙的地方, 把最後几题冲出来. 以我今天跟比赛同学讲的例子, 一个人正在写最後一题, 一个人帮忙看/讨论, 一个人不知道干麻, 我觉得你可以帮忙看, 若自己写程式比较快, 也许抢过来, 或是自己独立在纸上写 code, 或切一小块模组来纸上写, 或帮忙生些 test case 若写完马上可以派上用场. 种种可能. 另一个例子, 有一队在冲他们的最後一题, 在 debug, 一人 online debug, 另两人帮不上忙. 你们也许可以考虑彼此解释 code, 或印几分大家帮忙看, 其他人若也会写, 可以在纸上重写, 写完後再上机, 把 online debug 的人 offline. 回到这次比赛, 解出第一题简单题的时间应该可以更快些, 这可能就要各队自己检讨问题出在哪, 题目看太慢不懂, 判断错难度, 想错解法, 不熟悉要用的算法, 还是沟通不良, 等等. * judge 一开始由 smileshou 辛苦帮忙 judge, 後来他帮忙买大家的晚餐, 由我接手 judge 工作. 我稍微描述一下我觉得 judge 要注意的事, 供往後模拟赛的 judge 参考. 最理想状况是题目出得很完美, 现场 judge 只要利用设定好的 autojudge 就一切 ok, 这很难发生, (我猜测)也因此 pc^2 系统从以前到现在都设计成半自动 judge. judge 最好能在 judge 前先读过题目, 对题目及解法有一定了解, 譬如哪几题比较难, 哪几题复杂容易错, 那几题可能会执行比较久, 哪几题 case 比较多. 这样 judge 过程中, 比较容易注意到问题, 举个例子, 如发现大家全都超时, 究竟题目本身性质如此, 还是要去检查 input format 跟题目上说的是否相同. 最好的情况当然是出题者自己担任该题的 judge 工作. 比赛中 judge, 无论是对是错或其他情况, 除了用 autojudge 工具, 仍应用眼睛看一看, 譬如今天 pc^2 diff 说 wrong answer, 我用眼睛看起来一样, 才知道是 judge answer 多了空白, 与题目叙述不同. 对於不同的错误, judge 应尽量给与精确的回应, 譬如是 time too long, 还是 wrong answer 要分清楚. 可是反过来说, 比赛选手要有心理准备 judge reply 可能不是很精确, 至少比赛经验有时 reply 不太可信. judge 除了每个 submit 看, 也要注意整体状况, 譬如某一题一直没人对, 或简单题很多人错, 都有可能是 judge testdata 有问题. 若 submit queue 不会太长, 我 judge 时也喜欢随意打开各队程式看一看, 看看他是不是用了我预期的解法, 或他写了什麽特别的 code, 是否掉到某陷井. 这也有一点点观摩学习的效果. 譬如今天我就利用这样, 知道 team Wall B 题的解法(我本来没想出来), 也发现 F 题有我预期之外的解法, 而且 code 跟 B 题几乎相同. 以上种种都是希望 judge 能尽早发现问题及时修正/rejudge, 虽然大家都很讨厌比赛中 rejudge, 但总胜过赛後才找到/还没找到问题 模拟赛的品质, 在决定用哪套题目後, 就完全仰赖 judge 的表现. 各位要是有机会当 judge, 希望能多注意. -- "声音是声音, icon 是 icon, 用 icon 来表示声音的结果, 就是不知道哪个是声音, 哪个是 icon. " 小光光 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 61.70.142.187