2010试题回顾与竞赛特点分析—王宏0116-2 - 图文

2010试题回顾与竞赛特点分析

清华大学计算机系 王 宏

摘要：

1. 针对2010年国内外信息学奥赛主要赛事的题目与分类给出了粗略回顾和简要概括。 2. 结合IOI2010和其他赛事的部分统计数据和测试数据进行了归纳和分析。 3. 选择CEOI2010得分最低的两道题目进行讨论和交流。 4. 对备战IOI2011提出部分想法和建议。

2010主要赛事题目统计一览表

王宏、莫涛 等汇总

序号 1 2 3 4 5 6 7 8 NOI团体对抗赛 赛事 国内竞赛 NOI2010 英文题目/ 目录名 energy piano altitude plane trip nemo fourcolours galaxy go optimize product jewelry eight 中文题目 能量采集 超级钢琴 海拔 航空管制 旅行路线 成长快乐 四色地图 星际旅行 三国围棋擂台赛 性能优化 产品销售 珠宝商 8字玩具 重建计划 能量场 排序机 机器翻译 类型 传统 传统 传统 传统 传统 问题/主要方法/所用 时限s/命题或数据结构或考察要点 内存M 解作者 容斥原理，递推 线段树\\划分树\\RMQ 最小割，最短路 拓扑排序 基于连通性的状态压缩动态规划 计算几何 交互 1/512 2/512 2/512 1/512 10/512 胡伟栋 陈丹琦 俞华程 徐持衡 余林韵 唐文斌 周若凡 提交答案 构造、动态规划、贪心、- - 1/N 10/N 15/N 2/N 最大最小搜索，贪心 贪心 状态压缩动态规划 快速傅里叶变换 高逸涵 顾研 俞华程 陈丹琦 CTSC2010 (IOI2010 9 China Team Selection 10 11 Competition) 12 13 14 15 16 17 传统 传统 传统 传统 网络流，线段树优化 传统 树的分治、分块、数据结构 提交答案 构造，数据分析 18/N 漆子超 - 杨弋 唐文斌 冬令营 rebuild efield 传统 传统 传统 树的分治，参数搜索，线段树 计算几何、平面凸包 模拟 4/N 1/N 唐文斌 胡伟栋 NOIP2010 sort translate 提交答案 广搜、排序、堆、LCA 胡伟栋 1s/128M 韩家龙 - 18 19 20 21 22 23 24 序号 1 2 3 4 （提高组） tortoise prison flow two water missile sanguo 英文题目 乌龟棋 关罪犯 引水入城 数字统计 接水问题 导弹拦截 三国游戏 中文题目 推理 更冷更热 生活品质 语言 传统 传统 传统 传统 传统 传统 传统 类型 交互 交互 传统 交互 动态规划 二分答案，二分图判定 1/128 1/128 1/128 1/128 1/128 1/128 陈卓华 韩家龙 钟诚 陈卓华 陈卓华 钟诚 NOIP2010 （普及组） 贪心，动态规划 枚举，统计 模拟 排序，枚举 赛事 国际竞赛 IOI2010 问题/主要方法/ 基本数据结构 简单枚举 递推/二分检索/构造 二分答案+部分和枚举 检索/匹配/机器学习 贪心，图论 1/128 韩家龙 时限s/ 内存M 冯齐纬 吴翼 赖陆航 赖陆航 cluedo hottercolder quality of life languages 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 BOI2010 其它国际或地区赛 CEOI2010 APIO2010 memory traffic maze saveit commando patrol signaling 记忆 交通堵塞 迷宫 保存 特别行动队 巡逻 信号覆盖 联盟 算术 保镖 MP3播放器 身份证号码 高塔 犯罪组织 搭积木 印制电路板 储藏箱 糖果 采矿 交互 传统 提交答案 简单枚举 树型动态规划 搜索+调整 树形结构压缩 /解压缩 动态规划，凸性优化 树形动态规划 平面几何，排序，统计 最小割，网络流 解方程 贪心 单调性，线段树 枚举，哈希表 递推 二分答案，宽搜 状态压缩/搜索剪枝 动态规划/贪心 扫描+单调性 枚举，动态规划 分情况讨论，递推 1/N 1/N 2/N 2/256 0.3/256 0.7/256 0.5/256 0.8/256 1/256 1/64 1/64 1/64 0.1/64 2/64 - 吴翼 潘宇超 冯齐纬 潘宇超 肖汉骏 潘宇超 陈丹琦 交互 传统 传统 传统 传统 传统 传统 传统 传统 传统 传统 传统 传统 传统 传统 提交答案 alliances arithmetic bodyguards mp3player pin tower bears lego pcb bins candies mines

关于题目方法与分类比例

从上表简单统计可以得出，2010年主要竞赛的题目中， 涉及图论、网络流方面的题目约占1/5，所占比重有所降低。 应用动态规划思想、状态压缩动态规划的题目占到接近1/4

涉及线段树等数据结构的题目约占1/4（国内的前3个主要竞赛的比例更高）， 应用或部分应用贪心策略求解的题目高于1/5。

几何类或涉及计算几何方面知识的题目也占有相当比重。

由于有些题目可能同时使用多种策略或同属多种类型，所以上述题目分类在统计上会有一些重复，但从中大致可以看出2010年信息学竞赛题目的主要类型或方法分类。

关于三种类型题目的分布

信息学奥赛题目的另一种普遍认可的分类方式，是将题目按照传统型（提交源程序, batch tasks）、提交答案型 (output-only tasks) 和交互式 (reactive tasks) 三大类题目划分。从上表统计可以得出，2010年国内竞赛除NOIP2010外，其他几次国内重要赛事的题目都至少覆盖了两种类型（NOI、CTSC、冬令营这3次赛事共有3道提交答案型的题目）。

尤其值得关注的是，IOI2010共8道题，其中有5道交互式试题，另有1道提交答案型的题目，传统型题目只有2道。 即传统/提交答案/交互式试题的比例为 2:1:5, 这种情形前所未有。

相对而言，2010年另几次主要的国际竞赛题目类型比较单一，APIO2010只有3道试题，全部为传统型题目。CEOI2010共6道题也全部为传统型题目，BOI2010共6道题也只有1道提交答案的题目，其余均为传统型题目。

对于一个优秀选手而言，在保持传统型题目解题优势的基础上，应有针对性地进行传统型之外其他两种类型题目的特殊训练，以全面适应各种类型题目的要求。2010年国内外赛事也已证明，在提交答案型和交互式题目上选手的得分能力（包括所花费的时间），对最后的竞赛结果将产生重要影响和制约作用。

几个值得关注的问题

IOI的竞赛规则统计数据有几点值得我们关注：

1．沿用在线提交实时测试反馈的方式：根据竞赛规则和题目中规定，IOI2010仍然沿用了

可以进行在线提交，在正式测试数据上进行测评的方式，选手还能及时得到反馈的测试结果与说明。使用token可以在赛场上即时测试题目的全部测试数据，即在赛场上便可清楚知道自己的具体得分。这种在线提交实时测试反馈的方式是在IOI2007大赛中首次采用的，对于防止选手因看错题目或题意理解偏差而出现的意外失误具有非常积极的意义，但同时对承办地的硬件设施（在线测试的机器台数）、选手的心理素质也提出了更高的要求。根据组委会提供的数据，绝大部分选手都能充分利用这次比赛提供的这一有利条件。

2．题目的总体难度（包括测试数据的难度）并未明显增大：由于部分竞赛提供在线提交实

时测试反馈的方式，与往届相比，IOI2010的平均得分较高。选手得分差距很小。从金牌686（25人，半数过700，最高778）、银牌620（53人）和铜牌538（74人）的获奖分数线亦能说明这一点。同时零分选手的人数很少（11），不到选手总数的4%，以上数据充分说明IOI2010题目的总体难度（包括测试数据的难度）并不高。

3. IOI2010的提交方式与内容也值得关注：

（1）从过去提交一个完整的程序，变为仅需要写一个过程；

（2）与过去孤立的单组测试数据不同，每个题目采用subtask的评分方式，几乎所有的测试数据都是分组捆绑的，除特殊规定外，subtask的结果只有全对和全错两种方式，这对题目成绩的区分度产生很大的影响；

4. 题目类型的开放性使得一些传统强队选手失去了优势（经过严格的解题训练，算法技巧

应用熟练，知识点宽而深的选手），增加了比赛的偶然性，降低了强弱之间的差距。

5. 针对承办国以往命题的特点，如何更有针对性的训练，强化薄弱环节，做到提前适应、早做准备，提高应变能力。IOI2011在泰国举行。