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

前言

现在全球最大的编程比赛记分网站非CodeForces和AtCoder莫属了，@ezoixx130大佬已经在去年介绍过CodeForces了（传送门），那么现在我们主要谈一下AtCoder。

简介

使用

首页

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的宣传界面。

比赛

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分钟。最终排名以得分倒序统计，得分相同时按时间升序统计。这是最近一道具有部分分的赛题。

同时每次比赛时都会根据排名得出一个表现分，表现分值与名次正相关，与个人Rating无关，但Rating的增长与否由表现分决定。

3. 比赛时间

通常情况下，北京时间每周六或周日20时都会举行比赛。相对于CodeForces来说比赛时间更加友好。

4. 比赛界面

• 顶部菜单栏：

名称	功能
Top	比赛信息首页
Tasks	比赛题目列表
Clarifications	提问答疑
Submit	提交代码
Results	比赛提交记录及得分
Standings	比赛实时排名
Custom Test	在线IDE
Editorial	赛后题解，以AGC038的官方题解为例，还是非常详细的
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 不换行WA（本题洛谷题号为AT929，题面在此）

5. 比赛备用网址

AtCoder的比赛不仅在主站中举行，在比赛副站中也同时进行，账号、提交记录、排名均同步。如果主站加载较慢或显示出错，那我们可以到比赛副站中参加。

比赛副站网址可根据比赛名称构造，例如AGC038的比赛副站为https://agc038.contest.atcoder.jp，其主站https://atcoder.jp/contests/agc038。

Rating系统

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英文和日文界面中的功能是不完全相同的，即语言的切换会导致功能的变化。以下为日文网页，此网页与上文中英文首页图片在同一时间截图，我们可以发现，在左侧正在进行中的比赛中多了两场，在即将到来的比赛中多了一场，同时公告栏中的内容更加丰富，这些是针对日本选手特设的比赛和公告，在英文页中无法查看，但是在日文页中我们同样也可以参加。

通常情况下，日文页的功能比英文页的功能更加丰富，某些比赛只可在日文页中进入查看题解。

脚本

1. ac-predictor

安装脚本后，可以发现在界面右侧多了一个侧栏向左伸展的按钮，点击即可使用其功能。

• Estimator

可根据表现分来计算Rating值，也可根据想到达的Rating值计算所需的表现分。

• Predictor

在比赛页面点开侧栏还会出现Predictor，可输入本场比赛的排名算出表现分和Rating值。

• 丰富排名界面

所有参赛者的表现分和预计Rating值都会在Standing界面显示。

2. AtCoder Submission Status

一目了然地显示AtCoder提交的答案测试数据的结果及数量。

3. AtCoderDarkTheme

为AtCoder提供夜间模式界面。非常遗憾的是，直到目前为止，还未有任何人为Atcoder写外挂CSS样式，因此目前夜间模式只能使用JavaScript脚本实现。

4. AtCoderUserSearchForm

在顶栏添加用户搜索按钮，查找用户十分方便。

5. AtCoderResultNotifier

每当提交代码时，弹窗显示运行结果。

但由于网络对google的封锁，内联jQuery代码需要修改为可以正常使用的网站。 将其修改为https://code.jquery.com/jquery-3.3.1.min.js即可正常使用。

例题选讲

AtCoder Beginner Contest 112 C - Pyramid

题目描述

输入输出样例

输入#1

4
2 3 5
2 1 5
1 2 5
3 2 5

输出#1

2 2 6

样例解释

输入#2

2
0 0 100
1 1 98

输出#2

0 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$；
• 输入的坐标不重复；
• 中心坐标和高度可以被唯一确定。

思路

代码

#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

题目描述

1. 顶点编号为$1,2,...,n$。
2. 边编号为$1,2,...,n-1$，且边$i$连接点$ui$和点$vi$。
3. 如果$s$中的第$i$个字符为$1$，则可以通过从树中删除一条边来获得大小为$i$的连通分量。
4. 如果$s$中的第$i$个字符为$0$，则无法通过从树中删除任何一条边来获得大小为$i$的连接分量。

输入输出样例

输入#1

1110

输出#1

1 2
2 3
3 4

输入#2

1010

输出#2

1 2
1 3
1 4

输入#3

1111

输出#3

-1

数据范围与限制

• $2≤n≤10^5$

思路

• $s_1=1$（删掉任意叶节点即可得到仅含$1$点的连通分量）；
• $s_n=0$（删掉任何一条边最大只能获得含$n-1$点的连通分量）；
• $s_i=s_{n-i}$（两组连通分量互补）。

• 毛毛虫身长为$k+1$，即树的直径为$k+1$；
• 毛毛虫身体第$i(1<i≤k)$个点上长有$x_i-x_{i-1}-1$只脚。

代码

#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;
		}
	}
}