AcWing
  • 首页
  • 课程
  • 题库
  • 更多
    • 竞赛
    • 题解
    • 分享
    • 问答
    • 应用
    • 校园
  • 关闭
    历史记录
    清除记录
    猜你想搜
    AcWing热点
  • App
  • 登录/注册

【开坑持续翻译向】IOI金牌爷手把手教你从零开始上红名【上中下级篇】

作者: 作者的头像   怜爱 ,  2022-02-12 12:41:41 ,  所有人可见 ,  阅读 1647


34


31

本篇是Masataka Yoneda(AKA E869120),IOI 18 ~20年的金牌。Codeforces最高2909,AtCoder最高2935,原文发表在Qiita。分别用上中下级篇,其中下级篇内容可能比较简单,受众面狭窄,我会放在最后再翻译。

如果你对本文感兴趣,建议收藏+催更。
没什么人看就鸽了。每天坚持写一点。

值得一提的是E869120本月刚结束东京大学一年级的学习,同时出版了算法与数学这本现在在日本亚马逊排行榜刷屏的书,从0开始讲述了一些和数学有一定关系的基本算法。译者也购入了,虽然内容还是比较面向初学者(甚至比我还菜的初学者),但是我本来就比较菜所以真的学了不少东西。图文并茂,内容详实,如果有机会引进,一定是值得推荐初学OI的学生阅读的好书。

那么我们开始吧ovo

上级篇:目标是红名选手!

近年来,(日本OI界)以Atcoder为中心的算法竞赛越来越火热了。同时各大企业也开始在AtCoder招人(AtCoderJobs),算法实力检测这种类似的考试也开始涌现。

这些人中,很多人都想知道一件事:为什么怎么学都没法成为最顶尖的算法竞赛选手捏?相信,不管什么级别的算法竞赛选手都会有这种烦恼吧。

  1. 一开始啥都不知道做什么的初学者会有
  2. 为了制霸各种算法竞赛的高手也会有
  3. 公司里,学校里的算法竞赛的教练也会有

因此,我写下了这篇文章。为了达到算法竞赛高水平,你需要学习什么,你需要怎么练习。成为一份从低到高,由浅入深的算法竞赛指南,这就是本文最大的目的。

3-0 简单介绍一下上级篇

上级篇是针对想成为AtCoder黄名(2000+,对应CF2200+),以及橙名(2400,对应CF2522+)阶段的选手的进步指南。

Rating 颜色 相对排名 简单评价
2800+ 红名 前0.2%
2400-2799 橙名 前0.6%
2000-2399 黄名 前2% 算法岗位,算法研究生都可以很好地胜任
1600-1999 青名 前5% 几乎所有的IT企业的算法工作都可以胜任
1200-1599 水名 前10% 大部分的IT企业的算法工作都可以胜任
800-1199 绿名 前20% 作为软件开发岗很不错了
400-799 茶名 前35% 普通学生来说蛮不错了
1-300 灰名 前100%

注:右边的评价来自于AtCoder的老版chokudai的博客

38.PNG

3-1 成为黄名选手的6个要求

为了在AtCoder里成为黄名,你需要达到2000分(CF2200分左右。

  1. 在AtCoder Beginner Contest里稳定切掉5题。
  2. 在AtCoder Beginner Conetst里半数情况切掉6题
  3. 简单的问题(500分内)尽快解决。
  4. 根据相关数据,A题1分内,B题2分内,C题5分内,D题10分内,E题20分内比较合理。
  5. 理论上你最好在40分钟内切掉5题。
  6. AGC之类对数学要求比较高的比赛里,最好能切掉2题。

这是在竞赛里黄名选手的平均表现。为了保持这个表现,你需要做到以下6点。当然水色选手要做到的4点你也要做到(中级篇内容)

条件1

挑战程序设计竞赛(AKA蚁书)上面记载的大部分算法和数据结构都要理解。具体来说,需要了解以下23个算法和5个数据结构。

中级篇2-1节里的12个算法和3个数据结构

枚举 二分搜索 深度优先搜索 广度优先搜索
动态规划 Dijkstra Floyd Kruskal
线性筛 快速幂 逆元 前缀和·差分
图论 树 并查集

中级篇没有提到但是挑战里写过的11个算法。

离散化 分治 矩阵乘
博弈论(原文是Grundy数) 字符串哈希 分块
最小割 二分图判定 二分图匹配

中级篇没有提到但是挑战里写过的2个数据结构。

树状数组 线段树与懒标记
条件2

条件1介绍的算法和数据结构,在各种比赛里学会使用,同时将本文介绍的算法和数据结构熟练掌握,变成自己的东西。

条件3

有一定的数学能力。

在AtCoder里,不仅仅考验你能否灵活使用各种算法的能力,也频繁出现了大量的数学问题(和中级篇2-3里95-100的问题一样),问题也越来越难和多样。因此,为了成为黄名选手,要多多做一些数学题。

条件4

25行左右的程序,基本Bug Free写出来。

60行左右的程序,基本很快地写出来,出了BUG也能在10分钟内解决。

实际上,60行左右的程序,能够30分钟内写完并且de完bug,是大概率能AK掉ABC的。

条件5

打字速度要快!经验来讲,1分钟要350个字符才够用。

实际上,一些高排名选手里也有打字很慢的人(200个字符左右),但是想在ABC里拿到好成绩,打字速度实在太重要了。

比如说AtCoder 148里,30分钟AK和40分钟AK,差距250以上的表现分。

条件6

一般来说,AtCoder的过去的题目要做1000题以上。

补充

以上的6个条件满足了的话,ABC的E问题基本难不倒你。F问题的话,如果是超过250人做出来的场次,你应该也能做出来才对。

顺便一提,最近15场ABC(141~155),F问题做出来的超过250人的场次有7场。因此AK掉ABC的概率应该是3-5成。

满足了6个条件,再练练数学能力,AGC的问题解决出来的概率应该会慢慢增加。

3-2 如何成为黄名选手

为了成为黄名选手。你应该按顺序做以下7点。

  1. 掌握11个全新的算法。
  2. 学会2个新的数据结构。
  3. 去解决TopCoder SRM的问题,锻炼数学能力。
  4. 去解决JOI(日本信奥)的题目,锻炼能力。
  5. 解决以前Contest的题目
  6. 多多VP找感觉。
  7. 练打字速度。

我会按顺序讲解没一点

3-2-1学习全新的11个算法。

枚举 二分搜索 深度优先搜索 广度优先搜索
动态规划 Dijkstra Floyd Kruskal
线性筛 快速幂 逆元 前缀和·差分
图论 树 并查集

中级篇没有提到但是挑战里写过的11个算法。

离散化 分治 矩阵乘
博弈论(原文是Grundy数) 字符串哈希 分块
最小割 二分图判定 二分图匹配

中级篇没有提到但是挑战里写过的2个数据结构。

树状数组 线段树与懒标记
离散化

4 评论


用户头像
wimg6_   2024-08-15 21:41         踩      回复

催更


用户头像
Rainwang   2024-01-23 17:30         踩      回复

催更


用户头像
NoNameQWQ   2023-11-19 21:15         踩      回复

催更!


用户头像
trh0630   2023-06-03 19:18         踩      回复

好难


App 内打开
你确定删除吗?
1024
x

© 2018-2025 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息