算法竞赛

2013年8月22日，Yandex Algorithm竞赛公开赛现场

算法竞赛（又称编程竞赛、信息学竞赛、程序设计竞赛），不同于黑客松是一项智力运动，通常在互联网上或局域网上举行，其内容包括参与者尝试根据提供的要求进行编程 。 参赛者被称为竞赛程序员 。算法竞赛得到了多家跨国软件和互联网公司的认可和支持，例如Google和Facebook。

算法竞赛通常涉及到主办方向参赛者提出一组逻辑或数学问题（参赛者的数量可能从几万到数千不等），并且要求参赛者编写能够解决每个问题的计算机程序。评测主要基于解决的问题数量和编写成功解决问题的程序所花费的时间，但也可能包括其他因素（产生的输出质量，执行时间，程序大小等）。

历史

已知的最古老的竞赛之一是国际大学生程序设计竞赛，该竞赛起源于1977年，2011年中参赛者范围已经扩大到88个国家/地区。自从2000年以来，它也同时与Internet的发展有了很强的联系。这促进了在网上举办比赛，同时也消除了地理性的问题。

概述

算法竞赛的目标是编制源代码，在有限的计算资源内来解决给出的问题。大部分的问题是属于数学问题或者逻辑学问题。它们通常属于下面几个类型中的一个：组合数学、数论、图论、几何（很多时候是计算几何）、字符串和数据结构。和人工智能相关的内容在某些比赛中也很会出现。

不论问题的类别，解决问题的过程都可以大致地分为两大步骤：构思一个算法，以及使用一个编程语言来实现算法（允许使用的语言每个竞赛都会不同，主要以C++，Java，Pascal等为主，但是IT企业的竞赛大多会使用该企业的常用语言）。

大多数竞赛中，选手只应该为每一题编写一个源程序，这个源程序的系统调用会受到限制。一般创建新进程，访问网络，操作无关文件等等都是不允许的。一般情况下，选手只能使用他/她所使用的语言的标准库（例如C++语言的STL）。

一道传统的题目由以下几个部分组成。下面使用大多数OJ使用的试机题目A+B问题来做简要的阐述：

试题组成

名称	概述	实例
题目描述	这个部分包括对需要求解的问题的描述，有时也会有一个题目背景。 一般问题并不会直接给出数学模型，而需要参赛者自己设计模型，进而求解。	给你两个数$A,B$，请求出$A+B$的值。
输入输出格式	这个部分描述了程序应当怎样读取数据和输出答案， 在交互式题目中，这个部分描述了程序应当怎样与交互系统进行交互。 在某些题目中，这个部分还会包含数据范围和限制。	输入格式 输入包含一行，为整数$A,B$。 输出格式 输出包含一行，为求得的答案。
输入输出样例	这个部分给出了一或多组正确的输入输出，选手可以用来简单地检验他们的程序。 但是这些数据往往非常简单，难以检查出选手程序中的所有错误，同时它们往往规模较小。	输入样例 ${\texttt {1}}$ ${\texttt {2}}$ 输出样例 ${\texttt {3}}$
数据范围	大部分的竞赛都会有这个部分，它描述题目的数据范围和特殊性质。最后的测试数据必定满足这一限制。 在如国际资讯奥林匹亚竞赛等有子任务的比赛中它会描述了各个子任务的数据范围和（如果有）特殊性质。如果选手不能解决整个问题，那么他们可以尝试只解决一部分测试数据以获得该子任务的分数。	对于 50% 的数据，保证 $1\leq A,B\leq 10^{6}$ 对于全部数据，保证$1\leq A,B\leq 10^{9}$。

试题

在一般的竞赛中，试题有以下几种。

• 传统题要求程序从输入读入一些数据，进行求解后输出，这是最常见的题目。

• 提交答案题会事先下发输入数据，选手需要通过任意方法（包括计算器、手算、编写程序等）进行求解，并提交答案文件。

• 交互题会让选手程序与交互系统进行交互，一般会通过输入输出或者调用给定函数库来实现。例如 NOI 2019. I 君的探险 （页面存档备份，存于互联网档案馆）

• 通信题要求选手编写两个相互协作的程序解决问题。例如 UER #8. 打雪仗 （页面存档备份，存于互联网档案馆）

赛制与测评

在大多数竞赛中，评测是通过主办者的计算机进行的，这通常称为裁判系统。裁判会对选手提交的代码通过一组（通常是秘密的）测试数据进行测试。测试方法是所谓的黑箱测试，也即，裁判不关心选手的程序是如何实现的，而只要求它能够在规定的限制内正确地解答出问题。

大多数竞赛中，选手在提交代码之后能够即时获取反馈，一般反馈分为以下几种：

• AC (Accepted)：通过，选手程序完成了任务。
• PE (Presentation Error)：输出格式错误，选手程序输出答案正确，但是格式错误（例如，行中间出现空格），在某些竞赛中被视作 WA。
• WA (Wrong Answer）：答案错误，选手程序尽管成功运行，但并没有成功求解问题。
• TLE (Time Limit Exceeded)：超出时间限制，选手程序运行时超出了题目给出的时间限制。
• MLE (Memory Limit Exceeded)：超出空间限制，选手程序所使用的空间超过了题目给出的内存限制。在极少数竞赛中（例如USACO）被视作 RE。
• RE/RTE (Runtime Error) ：运行时错误，选手程序崩溃。
• OLE (Output Limit Exceeded) ：输出超过限制，选手程序输出了过多内容。
• CE (Compile Error) ：编译出错，选手程序没有成功编译。
• IE/SE (Internal Error/System Error) ：内部错误，评测系统出错。这时选手应当报告比赛主办方。某些平台细分为多种 （例如 Compilation Failed 编译器错误， Denial of Judgement 拒绝评测，Judgement Failed 评测失败，Checker Crashed 比较器崩溃等）。

另一些竞赛 （例如NOI）不提供即时反馈。系统在竞赛结束后会统一评测。

有些竞赛只有“对”和“不对”之分，没有部分分。例如ICPC。而另一些竞赛会按照测试点或者子任务分别给分。有时，还会按照解的优劣性进行部分给分。

对于传统题，一般判断答案正确的方法是在过滤行末空格和文末回车之后逐行比对，但是，有的题目会使用特制的比较器来进行测评。对于其他类型的题目则一般通过比较器进行给分。

大多数竞赛要求选手程序从标准输入读入数据，将答案写到标准输出，而早期竞赛和NOI系列赛则要求选手从给定的输入文件读入数据，将答案写到输出文件。

主要竞赛

比赛分为短期和长期两种。

短期

中国

• NOI - 中国 自 1984 年起举办的竞赛。

香港

• 香港电脑奥林匹克 - 香港 自 1997 年起举办的竞赛

台湾

• 高级中学数理及资讯学科能力竞赛 - 台湾 自 1999 年起举办的竞赛
• 台湾国际奥林匹亚竞赛 - 台湾用于选拔国际资讯奥林匹亚选手的比赛，由国立台湾师范大学资讯工程学系主办

国际/其他地区

• 国际大学生程序设计竞赛 (ICPC) - 历史最悠久的竞赛之一，由大学生三个人组队参加；
• CodeChef - 从2009年起，每个月会有两场短竞赛 和每年一场的CodeChef SnackDown；
• Codeforces Round - 一般是两小时，每星期举行；
• Facebook Hacker Cup - 由 Facebook 提供和支持的竞赛；
• HackerRank - 数种竞赛；
• Google Code Jam - 由 Google 提供和支持的竞赛
• IEEEXtreme Programming Competition - IEEE为其学生会员举办的竞赛。
• 国际信息学奥林匹克 - 面向中学生的最古老竞赛之一。

上述大多数竞赛都按轮举行，在NOI, IOI, ICPC等竞赛中，获得好成绩的选手可以获得金牌、银牌或铜牌。

长期

• HackerRank Week of Code
• Topcoder 马拉松

在线资源

有许多在线评测系统可以提供训练资源。以下仅列出较常见的评测系统。

非中国地区

• Codechef是印度的在线评测系统，也提供比赛。
• AtCoder是日本的在线评测系统，提供比赛。
• Codeforces是俄罗斯的评测系统，提供比赛。
• UVa是西班牙的评测系统，收录了大量 ICPC 的真题，题目质量较高。现在已经去掉了这个名称而直接叫做Online Judge。
• SPOJ是波兰的评测系统。
• SZKOPUL收录了波兰信息学奥林匹克的很多试题。

中国地区

• POJ是北京大学的评测系统。收录了不少亚洲区 ICPC 真题。
• ZOJ是浙江大学的评测系统。
• LibreOJ是由网名 Menci 的 OI 选手维护的在线评测系统，理念是自由开放。
• UOJ是由网名 vfleaking 的 OI 选手维护的在线评测系统，理念是接受一切试题的评测。
• 评测鸭是由王逸松开发的评测系统，能够将时间计算精确到纳秒。
• 洛谷是上海洛谷网络科技有限公司的评测系统，提供收费的网校服务。
• 香港电脑奥林匹克竞赛网上评测系统 (HKOI Online Judge) 原为集训队的训练平台，现已开放予全港中学使用。
• AcWing 是北京睿新奇知科技有限公司旗下品牌，拥有优秀的算法在线课堂，以及 AC Saber。

台湾地区

• Zerojudge是台湾最大的评测系统，题目来源较为广泛。
• Green Judge是由台中女中建立的评测系统，以新手向题目为主
• TIOJ是建国中学的评测系统。