一种程序设计竞赛的训练方法（译）

Rating从1000到2400+

2019年5月7日

Masataka Yoneda/E869120

1. 自我介绍
3. 训练方法介绍
4.训练心理
5. 虚拟赛推荐
6. 未来愿景
7. 总结

1. 自我介绍

亲爱的CF社区：

2019年4月20日，在14场比赛后，我终于达到了grandmaster，rating 2426。在最后一场比赛之前，我很遗憾rating是2399，距离成为粉名只差1分。所以上一场比赛(Forethought Future Cup Elimination Round) 是我印象最深的比赛之一。感谢CF举办这些比赛，感谢友善、出色且给人留下深刻印象的CF社区接受我的博客。

如今，我也想给CF社区做一点贡献，因为我之前在CF社区收获了很多，心里十分感激。我思考了很长时间“如何给CF做贡献”，或者说以一种合适的方式给CF做贡献。我想到了：介绍一种从灰名到粉名的练习方法。

现在，我要解释如何成为一个红名大佬。

2017年7月，我写了一篇博客解释如何到紫名(http://codeforces.com/blog/entry/53341) 。凭借这篇博客，我得到了181个赞，但那里面有很多语法错误，而且还有几个地方没有解释清楚。我很抱歉自己不擅长英语，也不是一个很好的作者。这次的博客可能还是有一些错误，但我努力使它更易读易懂。感谢你的合作、陪伴。

这次，我要分几个步骤进行讲解，因为rating范围有好几个，大部分人并不能一步就从灰名到达粉名，我也不能。所以这次我要分成下面的四个步骤：

Rating \(1000 \to 1400\)，从灰名到青名
Rating \(1400 \to 1900\)，从青名到前10%的选手
Rating \(1900 \to 2200\)，从前10%选手到表现优异的Div1选手
Rating \(2200 \to 2400\)，从表现优异的Div1选手到粉名

另外，在解释如何练习之前，因为CF用户很多，其中一些并不知道其他的OJ，所以我想介绍一下其他的在线比赛网站（AtCoder、TopCoder等）。

还有，很高兴你们阅读我的博客。非常感谢CF。

永田正彦

## 2. 常识介绍——一些打比赛的网站

世界上有很多OJ。为了成为粉名，我切了很多OJ上的很多题目。这次，为了 explain the post sections，我想先介绍一些比赛。

2-1. Codeforces [http://codeforces.com/]

Codeforces是世界上最有名的OJ之一，目前有五千多题。

利用CF的最好方式之一是“题目Rating”。例如，1146H Satanic Panic 的Rating是2800，这意味着，如果你的rating大于等于2800，那么你应该在比赛中切掉这个题。

另外，CF分成三个部分（Div1、Div2、Div3）。

再往后，我会使用下面两种简称：

Div1A, Div2E等等：代表Div1的A题、Div2的E题。通常，第一题是最简单的，最后一题是最难的。
难度R2800什么的：“难度R2800”代表这题难度被标成2800。例如，1146G Zoning Restriction 难度R2600，1146A Love "A"难度R600。

2-2. AtCoder [https://atcoder.jp/]

AtCoder是一个“拥有很多好题”的比赛网站。这只是个人意见，但如果你想变强，就要刷AtCoder。

AtCoder有三种类型的比赛：

AtCoder Beginner Contest (ABC) : 有4道题。
- ABC难度一般为R500-R700-R900-R1400。
AtCoder Regular Contest (ARC) : 有4道题。通常ARC的前两题和ABC的后两题是相同的。
- ARC难度一般为R900-R1400-R2100-R2600，因比赛而异。
AtCoder Grand Contest (AGC) : 有6道题。
- AGC难度一般是 R1200- R1900- R2200- R2500-R3000-R3300

还有个很方便的网站——AtCoder problems（https://kenkoooo.com/atcoder#/table//）。

在这个网站，你可以看到自己AtCoder的切题列表，知道自己哪些题还没做，哪些题做了。AC的被标成绿色，尝试过但没AC的被标成黄色。

2-3. TopCoder

TopCoder也是一个著名的比赛网站。Single Round Match (SRM) 有两个部分：

Division 2：有三道题，R600-R1300-R2100，被称为Div2简单、Div2中等、Div2困难。
Division 1：有三道题，R1800-R2400-R3000，被称为Div1简单、Div1中等、Div1困难。

我为了到粉名，也用TopCoder训练。尽管主要是数学题，但都是好题（我尤其喜欢SRM600-699）。

2-4. 这部分的总结

我主要用3个OJ训练：Codeforces、AtCoder、TopCoder。如果你了解了这3个OJ，就可以去阅读下一个部分了。在这些比赛网站训练是很重要也很有效的，而且我觉得这是最快的进步方式。

在第3部分，我会写很多要点，但都只是我的个人观点，不信任我也是可以的。很多人遵循我的方法，取得了很大的进步，但也有很多人没遵循我的方法依然取得很大进步。用我的方法训练是挺好，但不一定对所有人都有效。

3. 训练方法介绍

可能有很多人读过我上一篇教程博客，但现在和两年前不一样了。这两年我有很多遗憾。很多事情我没做，但我在想，如果我做了，是不是可以进步更快？因此，这篇博客和我之前那篇有很多不同之处。

此外，在rating到达2200前和到达2200后，我的训练方式完全不同。

还有一件事，这篇博客只是我的个人观点，训练方法因人而异，所以我认为你不一定按照我的方法训练。但我觉得我的方法对一些人来说是最有效的。

如果你理解了这一点，就可以继续往下读了。进入正题……3、2、1，走起！

3-1. 训练技巧 rating 1000~1400

CF上有很多灰名、绿名，他们很想成为青名、蓝名，但依然在苦苦挣扎中。

尽管如此，到达青名（1400）只需要做到三点。

能够快速写出模拟题（5到10分钟内）
能够快速写出暴力（5到10分钟内）
能够在脑子里或草稿纸上把问题分情况讨论（例如，N=2、N=3、N>=4）

举个例子，在Codeforces Round #556中，如果你可以做到以上三点，就可以很惊喜地在Div2中达到200名，这是一个很夸张的例子。但在Codeforces Round #554 (Div. 2)中，你只能达到3400名，rating1250及以下的参赛者可以上分。

平均来说，如果你可以做到以上三点，rating就可以达到1400。

[[如何训练]]

首先，我建议你打ABC。

尽管CF上有很多好题，但如果你想更容易地练习编程，最好去刷AtCoder。

特别地，我推荐做ABC中的B题和C题。做B题可以学到如何更快地写模拟和暴力，做C题可以学到如何想题、如何用草稿纸更快地想出解决方案。

从ABC 042开始，出题人加入了英文题面。目前最新的一场是ABC 125，所以共有84场可做的ABC。如果你切了所有的B题和C题，就会学到很多，变得更强。

可以借助AtCoder problems的帮助刷AtCoder，你能从这个网站知道自己做了哪些题。

当你刷AtCoder时，有几点很重要：

当你想不出解决方案时，应该在思考B题15分钟、思考C题30分钟后再看题解。可悲的是，最近几场ABC没有英文题解，但你可以读标程（题解中很可能包含标程的链接）。
即使你AC了某道题，在习惯快速写代码前，还是可以通过阅读大佬的源代码学到一些东西。所以我建议看一些简单的源代码。
特别是当你做C题时，我推荐你用草稿纸辅助思考。不用纸的话，用白板打草稿也可以。

我是高中一个计算机社团的社长，有很多社员用这样的方法获得了进步。

3-2. 训练技巧 rating 1400~1900

CF上人数最多的rating区间是[1400, 1500]。他们都很想上分，但从1500开始上分比较困难，很多人放弃了。但也有很多人坚持训练，成功上分。

要达到1900，需要下面的技巧：

掌握并能够使用以下主要算法：
- 暴力
- 动态规划
- 深度优先搜索
- 广度优先搜索
- 迪杰斯特拉
- 树状数组
- 排列数、组合数
- 乘法逆元
- 位掩码
- 二分查找
注意：我认为在rating 1800前，线段树不是必须的。我上紫以后才学的线段树。
提高手速（例如，R1100的题目5分钟写好，R1400的题目10分钟写好）。手速在CF很重要，因为一般来说，如果题目难度范围很大，手速会在很大程度上影响rating。