美国计算机奥林匹克竞赛
美国计算机奥林匹克竞赛(USA Computing Olympiad,USACO)是美国一项面向中学生的信息学竞赛,首次举行于1993年。
题库训练
USACO提供一个题库可供全世界所有的信息学竞赛选手进行训练。题库共有6个chapter,为六档难度的试题。每一个chapter中一般有4~5个section,每一个section集中介绍某一类型的试题。在section的开头一般会有一篇算法介绍,然后有4~5道试题。每一道试题都可以提交USACO服务器评测。与一般的在线评测系统不同的是,USACO不仅会告诉你评测结果,还会提供给你所有的测试数据。另外,在通过一道题之后,还会提供USACO自己撰写的题解,只是在交上去之后,你的程序并不能被保存,所以不能从上面得到你的源代码。
USACO的训练题库具有非常强的顺序性。除非将某一个section中所有试题都通过,你无法得到下一个section的算法介绍和试题。这训练了信息学竞赛选手面对棘手的问题和错误时坚持不懈的品质,但也在某种程度上为选手造成了麻烦。
USACO极为重视对算法时间效率与优化水平的考察,很多试题必须要进行非常细致的优化才能够通过。几个典型的例子如Checker Challenge, Cryptcowgraphy, Latin等。
当选手完成所有6个chapter的训练之后,可以向USACO的总教练申请开放额外的训练页进行进一步的训练。
比赛
一般来说USACO在每年的12,1,2,3,4月份会组织月赛[1],一月一次。其中4月份的比赛是US Open (公开赛)。每一场月赛都会有4组构成,分别是铂金组,金组、银组、铜组,难度依次递减。进入更高一组一般有两种方式:在10月份的资格赛中取得较好的成绩,或者在某一次月赛中取得该组领先的地位。一般来说选手不会被降组。
通常情况下一次比赛的时间为3~4小时,选手需要完成3~4道题目。选手可以在该次月赛指定的时间范围(通常是4天,覆盖一个周末)中的任何一个时间打开题目,并在规定的时间内完成比赛并提交。注意先用一个帐户打开题目阅读,然后使用另一个帐户打开题目提交被明确定义为作弊,在比赛结束之前泄露、发布题目也应该被认为是不妥当的。
每一次比赛的官方版本为英语版。一般在比赛页面上还会出现其他语言的版本,它们是由已经参加本次月赛的选手进行翻译的。USACO规则明确声明它不对除英语外其他版本的正确性与准确性负责。因此选手应该尽可能使用英语版本。
月赛的题目与IOI试题类型大致相同,绝大多数为传统试题,但也在极少数情况下出现过提交答案类型试题。铂金组难度与中国省选、NOI相当,金组的试题的平均难度不及IOI试题,但比NOIP难度要高,部分试题可以达到甚至超过IOI试题的难度。银组试题与NOIP提高组的试题难度相当而略低,铜组试题难度与NOIP普及组难度大致相等,有的难度更低。
月赛结束后1~2天你可以通过电子邮箱收到你的程序的评测结果。同时在比赛相应的页面上你可以找到测试数据、题解、所有参赛选手的程序代码、所有参赛选手的成绩总表以及对比赛的简要分析、统计与总结。
注意事项
USACO规则中明确规定“直接输出答案”是作弊行为。换言之,选手在本机上计算得到答案,然后提交一个直接输出答案的程序是不被允许的(这种技术一般被称为“打表”)。但是这种行为在绝大多数中学信息学竞赛与大学程序设计竞赛中都是合法的。
根据USACO规则,程序的运行与结果必须完全是确定性的。换言之,在程序中使用时间函数初始化随机种子是不被允许的。
选手在参加比赛时可以使用书上、互联网上或者自己曾经写过的代码,无论代码是否是由选手自己写的。但是使用这些代码的时候选手必须将其明确注释出来,否则被认为是作弊。另外,除非特别声明,选手必须独立完成试题,任何其他人的帮助都是被禁止的。