AtCoder从小白到大神的进阶攻略

## 前言 现在全球最大的编程比赛记分网站非CodeForces和AtCoder莫属了，@[ezoixx130](https://www.luogu.org/space/show?uid=34886)大佬已经在去年介绍过CodeForces了（[传送门](https://www.luogu.org/blog/ezoixx130/codeforces-tutorial)），那么现在我们主要谈一下AtCoder。  ## 简介 AtCoder是日本最大的算法竞技网站，正式创立于2012年6月20日，由AtCoder Inc.运行并维护，其域名为[https://atcoder.jp/](https://atcoder.jp/)。提供编程在线比赛、过往比赛提交、在线评测等服务。 ## 使用 ### 首页  1. 顶部菜单栏功能： >| 名称 | 功能 | >| :----------- | :----------- | >| Logo图标及Home | 返回首页 | >| Contest | 比赛列表 | >| Ranking | 查看用户排名 | >| English | 选择语言 | >| 个人ID | 查看个人信息 | 2. 左侧列表： > * Contest >>**Permanent Contests** >>>此栏中列举的是正在进行的比赛，其中的practise contest长期进行，此比赛主要目的是熟悉AtCoder的评测系统，不计分不排名。如果你对AtCoder的评测方式一无所知，可在此比赛中练习。 >>**Upcoming Contests** >>>可以在此查看即将举行的比赛并报名。 >>**Recent Contests** >>>最近结束的十场比赛，按照时间排序。你可以随意打开任意一场比赛，无需报名即可做题。 > * Ranking >>榜中列举的是**活跃用户**前十名。如果长时间未参加AtCoder比赛，即使Rating未发生任何变化，账号也会被从Rank榜中移除。 3. 右侧列表： > * Information >>AtCoder基本信息、使用方式及答疑等。 > * 公告栏 >>通常情况下，在比赛开始的前一天，网站管理员会在此公告栏和CodeForces博客同时发布比赛公告以宣传比赛。[此为AtCoder Grand Contest 028位于Codeforces的宣传界面。](http://codeforces.com/blog/entry/62399) ### 比赛 1. 比赛类型： AtCoder官方比赛分为以下三种： > * AtCoder Beginner Contest (ABC) >>这是最频繁且最简单的入门赛，通常情况下每月至少举行2次。2019年4月27日（含）之前，每场比赛共4题，时长100分钟，满分1000分且Rating超过1199的选手不计Rating值。自2019年5月19日起改版升级为6道题目，时长不变，满分2100分且Rating值超过1999的选手不计Rating值。改版之后比赛质量和参加人数均有较大突破和提升。由于入门赛题目较简单，因此许多参赛者会选择倒序做题。赛题按照洛谷的难度评级约为红题~蓝题，本类比赛题目具有极强的教育意义，因此建议初学者或参加普及组的选手多参加此比赛以锻炼代码熟练度。 > * AtCoder Regular Contest (ARC) >>这是AtCoder的常规赛，共4道题目，时长100分钟，满分2100至2700不等，Rating超过2799的选手不计Rating值。特别地，本比赛一般与ABC同时进行，ABC的C、D题与本比赛前两题相同，因此ARC赛题通常编号为C~F，ABC编号A~D。与洛谷目前月赛模式相同。题目难度中等，赛题按照洛谷的难度评级约为黄题~紫题。按照AtCoder官网所述，此比赛原应比AGC更频繁，但是事实上自2018年9月29日的ARC103后此比赛便再未举行过。 > * AtCoder Grand Contest (AGC) >>这是AtCoder最优秀的比赛，题目全部聘请特级选手进行原创。通常情况下赛题具有较大的思维难度。每月一般会举行1次，6道题目，时长110分钟至150分钟不等，通常总分5600。所有选手均计Rating值。 2. 记分方式 >比赛题目一般不设部分分，AC则得全分，否则每次失败提交会罚时5分钟。最终排名以得分倒序统计，得分相同时按时间升序统计。[这是最近一道具有部分分的赛题。](https://atcoder.jp/contests/arc103/tasks/arc103_b) >同时每次比赛时都会根据排名得出一个表现分，表现分值与名次正相关，与个人Rating无关，但Rating的增长与否由表现分决定。 3. 比赛时间 >通常情况下，北京时间每周六或周日20时都会举行比赛。相对于CodeForces来说比赛时间更加友好。 4. 比赛界面 > > * 顶部菜单栏： >>| 名称 | 功能 | >>| :----------- | :----------- | >>| Top | 比赛信息首页 | >>| Tasks | 比赛题目列表 | >>| Clarifications | 提问答疑 | >>| Submit | 提交代码 | >>| Results | 比赛提交记录及得分 | >>| Standings | 比赛实时排名 | >>| Custom Test | 在线IDE | >>| Editorial | 赛后题解，[以AGC038的官方题解为例](https://img.atcoder.jp/agc038/editorial.pdf)，还是非常详细的 | >>| Discuss | CodeForces比赛讨论区 | > * 提交记录 >>提交代码后可在Results>My Submissions>Detail中实时查看每个测试点的运行结果，但不会显示测试点内容。 >> >>在比赛结束后可查看他人的提交记录且代码公开。 > * Standings >> >>在排名页面可显示所有人的做题状态，以便控制自己做题的速度，通常情况下比较强的大佬可在25分钟内AK ABC，45分钟ARC，70分钟AGC。 > * 注 >>1. AtCoder无社区功能，也就是说，在没有比赛进行时，是不可以发讨论寻求帮助的，但是可以在比赛对应的CodeForces宣传界面进行询问~~，有没有人回复那就是另一回事了~~。 >>2. **AtCoder评测机可能与其他OJ评测机不同，你的程序输出结束后不进行换行操作（'\n'或endl）可能会导致Wrong Answer。对于较新的题目，此Bug已修复，但是在提交较久远的题目时仍然会出现此情况。在洛谷有许多用户交题时经常因此爆零，请大家注意。~~洛谷是有多久没有更新AtCoder题库了啊?~~** 提交记录展示：[换行AC](https://atcoder.jp/contests/joi2012ho/submissions/7689629) [不换行WA](https://atcoder.jp/contests/joi2012ho/submissions/7689620)（本题洛谷题号为[AT929](https://www.luogu.org/problem/AT929)，[题面在此](https://www.ioi-jp.org/joi/2011/2012-ho-prob_and_sol/2012-ho.pdf#page=7)） 5. 比赛备用网址 >AtCoder的比赛不仅在主站中举行，在比赛副站中也同时进行，账号、提交记录、排名均同步。如果主站加载较慢或显示出错，那我们可以到比赛副站中参加。 >比赛副站网址可根据比赛名称构造，例如AGC038的比赛副站为[https://agc038.contest.atcoder.jp](https://agc038.contest.atcoder.jp)，其主站[https://atcoder.jp/contests/agc038](https://atcoder.jp/contests/agc038)。 ### Rating系统 不同的Rating等级对应着不同的ID颜色，ID会有八种正常颜色和两种特殊颜色。与CoderForces系统不同，Atcoder初始Rating值为0。 1. 正常颜色 >| 颜色 | Rating范围 | >| :----------- | :----------- | >| $\color{#d9d9d9}\text{灰色}$ | 0~399 | >| $\color{#d9c5b2}\text{棕色}$ | 400~799 | >| $\color{#b2d9b2}\text{绿色}$ | 800~1199 | >| $\color{#b2ecec}\text{蓝色}$ | 1200~1599 | >| $\color{#b2b2ff}\text{浅紫色}$ | 1600~1999 | >| $\color{#ececb2}\text{黄色}$ | 2000~2399 | >| $\color{#ffd9b2}\text{橙色}$ | 2400~2899 | >| $\color{#ffb2b2}\text{红色}$ | 2900+ | 2. 特殊颜色 >未参加任何比赛的ID会呈现$\color{#000000}\text{黑色}$，身为网站管理员的账户为$\color{#c000c0}\text{紫色}$。 3. Rating界面展示 > ### 个人信息  1. My Profile >查看个人信息，包含全站排名、Rating变化记录、参赛记录等数据。 2. General Settings >可更改昵称、绑定推特账号和CF账号、设置国籍、出生日期、工作地等个人信息。特别注意，登录时使用的用户名只允许更改一次，但比赛时显示的昵称允许修改多次。 3. Change Photo >修改个人头像。 4. Change Password >更改密码。 5. Manage Fav >在他人个人页面可点击五角星进行关注操作，关注后可以在此查看。注意手动同步本地与云端数据。 6. Sign Out >退出登录。 ### 语言切换 >为什么要着重说一下AtCoder网站的语言呢？ >与其它网站不同，AtCoder英文和日文界面中的功能是不完全相同的，即语言的切换会导致功能的变化。以下为日文网页，此网页与上文中英文首页图片在同一时间截图，我们可以发现，在左侧正在进行中的比赛中多了两场，在即将到来的比赛中多了一场，同时公告栏中的内容更加丰富，这些是针对日本选手特设的比赛和公告，在英文页中无法查看，但是在日文页中我们同样也可以参加。 >通常情况下，日文页的功能比英文页的功能更加丰富，某些比赛只可在日文页中进入查看题解。 > ### 脚本 一个知名的网站总是少不了各种各样的辅助脚本，现在我们着重介绍几个比较方便AtCoder使用的Tampermonkey脚本。 ~~什么？没有用过Tampermonkey？在浏览器扩展中心搜索并安装，打开[greasyfork.org](https://greasyfork.org)搜索你想要的网站脚本安装就可以使用了。~~ 1. [ac-predictor](https://greasyfork.org/zh-CN/scripts/369954-ac-predictor) >安装脚本后，可以发现在界面右侧多了一个侧栏向左伸展的按钮，点击即可使用其功能。 > > * Estimator >> 可根据表现分来计算Rating值，也可根据想到达的Rating值计算所需的表现分。 > * Predictor >> 在比赛页面点开侧栏还会出现Predictor，可输入本场比赛的排名算出表现分和Rating值。 > > * 丰富排名界面 >> 所有参赛者的表现分和预计Rating值都会在Standing界面显示。 > 2. [AtCoder Submission Status](https://greasyfork.org/zh-CN/scripts/383817-atcoder-submission-status) > >一目了然地显示AtCoder提交的答案测试数据的结果及数量。 3. [AtCoderDarkTheme](https://greasyfork.org/zh-CN/scripts/388076-atcoderdarktheme) > >为AtCoder提供夜间模式界面。非常遗憾的是，直到目前为止，还未有任何人为Atcoder写外挂CSS样式，因此目前夜间模式只能使用JavaScript脚本实现。 4. [AtCoderUserSearchForm](https://greasyfork.org/zh-CN/scripts/382092-atcoderusersearchform) >在顶栏添加用户搜索按钮，查找用户十分方便。 > 5. [AtCoderResultNotifier](https://greasyfork.org/zh-CN/scripts/371225-atcoderresultnotifier) >每当提交代码时，弹窗显示运行结果。 > >但由于网络对google的封锁，内联jQuery代码需要修改为可以正常使用的网站。 > >将其修改为[https://code.jquery.com/jquery-3.3.1.min.js](https://code.jquery.com/jquery-3.3.1.min.js)即可正常使用。 ## 例题选讲 ### [AtCoder Beginner Contest 112 C - Pyramid](https://atcoder.jp/contests/abc112/tasks/abc112_c) #### 题目描述 在古代的$Snuke$王国中，有一座用来加强$AtCoder \ \ Inc.$总裁$Takahashi$权威的金字塔。 金字塔的中心坐标为$(Cx,Cy)$，其高度为$H$。周围一点的坐标$(X,Y)$的高度为$max(H-|X-Cx|-|Y-Cy|,0)$。 探险家青木进行了一项调查，以确定这座金字塔的中心坐标和高度。结果，他获得了以下信息： $Cx$，$Cy$为$0$到$100$（含）之间的整数，$H$为不小于$1$的整数。 另外，他获得了$N$条信息。第$i$条信息是：“点$(xi,yi)$的高度是$hi$。” 这足以识别中心坐标和金字塔的高度。 通过上面的提示找到这些值。 #### 输入输出样例 ##### 输入#1 ``` 4 2 3 5 2 1 5 1 2 5 3 2 5 ``` ##### 输出#1 ``` 2 2 6 ``` ##### 样例解释 在这种情况下，中心坐标和高度可以标识为$(2,2)$和$6$。 ##### 输入#2 ``` 2 0 0 100 1 1 98 ``` ##### 输出#2 ``` 0 0 100 ``` ##### 样例解释 在这种情况下，中心坐标和高度可以标识为$(0,0)$和$100$。 请注意，已知$Cx$和$Cy$是$0$到$100$之间的整数。 ##### 输入#3 ``` 3 99 1 191 100 1 192 99 0 192 ``` ##### 输出#3 ``` 100 0 193 ``` #### 数据范围与限制 * $0≤N≤100$； * $0≤x_i,y_i≤100$； * $0≤h_i≤10^9$； * 输入的坐标不重复； * 中心坐标和高度可以被唯一确定。 ### 思路 通过观察题目，直觉就会告诉我们直接求解并没有那么容易，于是我们换种思维方式，即枚举所有可能的答案判断是否符合题意。 枚举$Cx$和$Cy$，通过已知的一点高度确定$H$，判断所有已知条件是否均符合要求。时间复杂度$Θ(n^2)$。 ### 代码 ```cpp #include<cstdio> #include<cmath> #include<iostream> using namespace std; int n,F,x[101],y[101],h[101]; inline bool check(int X,int Y,int H){ for(register int i=1;i<=n;i++)if((((H-abs(X-x[i])-abs(Y-y[i]))<0)?0:H-abs(X-x[i])-abs(Y-y[i]))!=h[i])return false; return true; } int main() { scanf("%d",&n); for(register int i=1; i<=n; i++) { scanf("%d%d%d",&x[i],&y[i],&h[i]); if(h[i]!=0)F=i; } for(register int i=0; i<=100; i++) { for(register int j=0; j<=100; j++) { if(check(i,j,abs(i-x[F])+abs(j-y[F])+h[F])){ cout<<i<<" "<<j<<" "<<(int)abs(i-x[F])+abs(j-y[F])+h[F]<<endl; return 0; } } } } ``` ------------ ### [AtCoder Regular Contest 103 E - Tr/ee](https://atcoder.jp/contests/arc103/tasks/arc103_c) #### 题目描述 你将得到一个长度为$n$的$01$字符串$s$。任务是判断是否存在满足以下条件的含$n$个顶点的树。 1. 顶点编号为$1,2,...,n$。 2. 边编号为$1,2,...,n-1$，且边$i$连接点$ui$和点$vi$。 3. 如果$s$中的第$i$个字符为$1$，则可以通过从树中删除一条边来获得大小为$i$的连通分量。 4. 如果$s$中的第$i$个字符为$0$，则无法通过从树中删除任何一条边来获得大小为$i$的连接分量。 如果存在这样一棵树，则构造一棵这样的树。否则输出$-1$。若数据多解，输出任意一种即可。 #### 输入输出样例 ##### 输入#1 ```cpp 1110 ``` ##### 输出#1 ```cpp 1 2 2 3 3 4 ``` ##### 输入#2 ```cpp 1010 ``` ##### 输出#2 ```cpp 1 2 1 3 1 4 ``` ##### 输入#3 ```cpp 1111 ``` ##### 输出#3 ```cpp -1 ``` #### 数据范围与限制 * $2≤n≤10^5$ #### 思路 显而易见，当且仅当满足以下三种情况时有解： * $s_1=1$（删掉任意叶节点即可得到仅含$1$点的连通分量）； * $s_n=0$（删掉任何一条边最大只能获得含$n-1$点的连通分量）； * $s_i=s_{n-i}$（两组连通分量互补）。 然后，我们可以通过画图发现，几个菊花图相连形成的树正是我们想要的答案，这种树又称作[毛毛虫树(Caterpillar Tree)](https://en.wikipedia.org/wiki/Caterpillar_tree)。 设字符串$s$中$1$的个数为$k$，构造$1$个长度为$k$的数组$x$满足$s_{x_i}=1$，那么我们所求的毛毛虫树满足以下性质。 * 毛毛虫身长为$k+1$，即树的直径为$k+1$； * 毛毛虫身体第$i(1<i≤k)$个点上长有$x_i-x_{i-1}-1$只脚。 #### 代码 ```cpp #include<iostream> #include<cstdio> using namespace std; string s; int cnt=1,root,lst; int main(){ cin>>s; if(s[0]=='0'||s[s.length()-1]=='1'){ puts("-1"); return 0; } for(register int i=0;i<(s.length()>>1);i++){ if(s[i]!=s[s.length()-i-2]){ puts("-1"); return 0; } } for(register int i=0;i<s.length();i++){ if(s[i]=='1'){ root=cnt; printf("%d %d\n",root,++cnt); if(lst)for(register int j=1;j<i+1-lst;j++)printf("%d %d\n",root,++cnt); lst=i+1; } } } ``` 通过这两道题我们可以大致了解AtCoder的赛题并不会考过于高深的算法，而是考思维难度较大的题目，这对我们的竞赛能力有莫大的帮助。 **如果上文中至少有一项内容令你感兴趣的话，那就赶快注册一个AtCoder账号，开启你的AK之旅吧！** **完结撒花，感谢大家，[私人博客中阅读依然顺畅哦](https://www.cnblogs.com/LHYLHY/articles/11572011.html)！** **如果文中有错误或疏漏请大家尽快指出，谢谢！**