こんにちは!AtCoderではSa15MiyagiJapanというユーザーネームで活動している北杜七星と申します。
今回は、競技プログラミングサイト「AtCoder」で緑色になったので、色変記事として、これまでの取り組みについて話そうと思います。
目次
本記事の想定読者
プログラミング未経験者~AtCoder灰色~茶色の方を想定しています。
自己紹介
- 通信制高校2年次(体調不良で全日制から転校,AJLには前籍校で参加)
- 理系,情報工学志望
- AtCoder歴4か月
- 数学は少し得意 数Ⅲ未修得
- 競技数学サイトOnlineMathContestで緑色
- 始めた当時プログラミング未経験
- 言語はC++で参加(競プロには使わないがJSを勉強中)
競技プログラミングとは?(未経験者向け)
競技プログラミングは、ある課題を解く正しいプログラムを作成し提出する競技です。提出したプログラムは複数のテストケースが与えられ、全てのケースで実行時間制限内に正しい答えを出力すると正解と判定されます。(より最適解に近い解を出すことを目指すコンテストも存在します。これをヒューリスティックコンテストなどと呼びますが、本題からずれるので詳細は割愛します。)
競技プログラミングのコンテストは数多く存在しますが、日本ではAtCoderというサイトが有名です。AtCoderで毎週土曜日夜に開催されるAtCoder Beginner Contest(以下ABC)では、標準入出力と単純な条件分岐で解ける問題から、高度なアルゴリズムを使いこなすことが求められる問題まで幅広い難易度の問題が出題され、国内外から1万人ほどが参加しています。
AtCoderではコンテストの参加者の実力がレートという数値で表現され、さらに400刻みで色分けされています。
- 2800~∞ 赤色
- 2400~2799 橙色
- 2000~2399 黄色
- 1600~1999 青色
- 1200~1599 水色
- 800~1199 緑色
- 400~799 茶色
- 0~399 灰色
ちなみに黄色以上の参加者はABCではレートが変動しなくなり、ARC(Regular Contest)やAGC(Grand Contest)に参加しないとレートが上げられません。
AtCoderの参加者の多くは、ひとつ上の色を目指して取り組んでいます。
今回の"入緑記事"というのも、茶色から緑色になって(入緑して)執筆する記事という意味です。
AtCoder緑色のレベル感
ABC398終了時点でAtCoderには121874人のアクティブユーザー(直近2年にレートが変動した参加者)がいます。
そのうち緑色以上の参加者は18857人です。また、水色以上の参加者は9299人です。つまり、 AtCoderで緑色のユーザーは7.8%存在し、全体の上位15.4% であることがわかります。
しかし、AtCoderでは参加回数が非常に少ないユーザーが多く存在し、またそのような参加者にはレートに大きな下方修正がかかります。
そこで、参加回数(レート変動回数)14回以上の参加者に絞ったデータも紹介します。この条件では全体の参加者は30800人で、緑色以上の参加者は14225人、水色以上の参加者は7402人存在します。つまり、ある程度の回数(ABCに毎週参加して3~4か月)以上AtCoderに参加しているユーザーの中では、緑色は 22.1%存在し、全体の上位46.1% であることが分かります。もちろん、 コンテスト時間だけでも20時間以上費やすほど競技プログラミングにはまった人の中の割合 なので、一般人の中の上位46.1%とはまた話が違うことには留意してくさい。
少し過去のデータではありますが、参加回数による補正を抜いた内部レートでの分布も参考にするとよいと思います。(AtCoder社長 chokudaiさんの2022年6月のポスト)
ちょっと内部レートを計算したのでメモ。前計算した時とそんなに変わってないので、最近の分布変化はあんまりないのかな……? pic.twitter.com/lP9n5kIjDT
— chokudai(高橋 直大)@AtCoder (@chokudai) June 15, 2022
緑色の人が実際にどのようなことができるのかについては以下の記事を参照してください。
また、相応しい動画があるので勝手に宣伝します。
入茶までの取り組み
私が入茶までやったことは主に次の4つです。
- APG4b(C++入門教材) 3.03.STLのコンテナ まで
- 環境構築(VisualStudio→VSCode+WSL)
- AtCoder Daily Training(ADT)の参加
- ABCの参加
ADTで演習しつつ、プログラミングに慣れ、多少計算量を意識することで達成できました。
詳しくは私の入茶記事をご覧ください。
入緑までの取り組み
入茶してから入緑するまでの2か月、次のことに取り組んでいました。
- APG4b 3.04.構造体
- AtCoder Daily Training(ADT)の参加
- ABCに参加する
- ARC(Div.2)に参加する
- yukicoderに参加する
- A埋め(虚無埋め)
- C問題までを対象とした精進
- 鉄則本 1.4二進法まで
- ABC典型アルゴリズムの学習
- (番外)AHCに参加する
それぞれについて説明します。
APG4b 3.04構造体
AtCoder Programming Guide for beginners(APG4b)は、各節に用意された練習問題を解きながら、C++の基礎文法を学ぶことができます。この教材はプログラミング未経験者がAtCoderに参加するハードルを下げてくれています。実際、この教材が存在しなかったら私は競技プログラミングを始めてないです。
AtCoderを始めて1週間で3.03 STLのコンテナまで学習しましたが、そのあとはずっと放置していて、その後は3月に3.04 構造体を学習しましたのみです。
3章以降の重要度はそこまでですが、やって損はない教材だと思います。私も気分転換で進めていく予定です。
APG4bはPython版も存在し、2章まで公開されています。プログラミング未経験者の方は、APG4bPythonのトップページの"競技プログラミングで使用する言語選択に悩む人への助言"を読んだうえで好きな言語を選択するとよいと思います。
AtCoder Daily Training(ADT)の参加
AtCoderでは毎週火、水、木曜日に3回ずつ週9回、AtCoder Daily Training(ADT)という過去問を活用した練習用のコンテストが開催されています。
プログラミング未経験者の方はいきなりコンテストに参加するのは緊張すると思います。これのEasyに出てみて難易度感をある程度掴んでおくとよいと思います。
私はALL(ABCのA~F問題から出題)に出ています。1月は11回、2月は4回参加しました。2月は忙しかったこともあり参加回数が減っています。
ADTに参加することで過去問を解く時間を強制的に確保できる、コンテスト形式で行われるので集中できるという点で非常に有効な手段です。今後も積極的に参加していくつもりです。これから入緑を目指す方にもおすすめします。
ABCに参加する
レーティングを直接的に上げる唯一の方法がRatedでコンテストに参加することです。A問題しか解けなくても積極的に参加しましょう。
必ず青いボタンを押しましょう。 白いボタンを押すと爆発します。
私は入茶から入緑まで毎週ABCに参加しました。コンテスト後は解説放送を見る、Xで他の参加者の解法を知る、解けなかった問題を解いてみるといった復習の時間を設けます。
ARC(Div.2)に参加する
AtCoder Regular Contest(Div.2) (ARCDiv.2)は水色から黄色の参加者がレーティング変動の対象となるコンテストです。一見灰色や茶色の参加者には関係ないように見えます。
ARCは問題の傾向がABCと異なり、思考力を問う問題が多く出題されます。これがなかなか面白かったりするので気分転換に出てみるのは十分アリです。
400~500点の問題は茶色の参加者にも十分正解を狙える問題があります。私は4回ARC(Div2)に出てそのうち3回で1問正解しています。
さらに上級者向けとなるARC(Div.1)やAGCはかなり難しいですが気になったら覗いてみるのもよいでしょう。
中高生向けの話(折り畳み)
皆さんはAtCoder Junior League(AJL)に参加していますか?
4月からはAJL2025夏が始まります。
AJLはAtCoderの中高生の参加者で学校ランキング、学年個人ランキングを競います。中高生の参加者のモチベーションのひとつとなっています。
このランキングのスコアは参加したコンテストのパフォーマンスで計算されます。実は、このランキングのスコアは1問以上正解さえすればRatedであるか関係なく計算されるということがポイントです。
ARCやAGCで運よく1問でも解くことができれば、場合によってはAJLスコアを大きく積み増すことができるかもしれません。夢がありませんか?
実際にAGCで黄diffを通し、10万点近いスコアを持ち帰った緑コーダーもいます。
折り畳みここまで
yukicoder contestに参加する
AtCoder以外にも競技プログラミングサイトがあります。yukicoderはそのひとつです。
AtCoderのようなレーティングは存在しませんが、金曜日を中心にコンテストが開催されており、多くの作問者による多様な問題を解くことができます。気分転換にいかがでしょうか?
第1回 岩井星人アンソロジープログラミングコンテスト、yukicoder contest 458、yukicoder score contest 10(ヒューリスティック形式)に参加しました。
A埋め(虚無埋め)
ABCのA問題をABC212~261の50問埋めました。たまにWAを食らったり、学びがある問題もないわけではなかったですが、あまり実力が上がる気はしないです。実力より低い過去問を解くことはたまに虚無埋めと呼ばれます。
もちろんプログラミング未経験者の方はA問題からスタートしましょう。慣れてしまえば一問5分以内で解けるようになります。
C問題までを対象とした精進
AtCoder Problemsで未ACのA10問、B10問、C5問、D1問、E1問のバーチャルコンテストを組んで精進しようとしてみましたが一周目の23問目を解いたところで止まっています。なので実質C問題までの精進です。さぼり過ぎですね...
次組む時はD問題、E問題の比率を上げる予定です。
鉄則本 1.4二進法まで
競技プログラミングの書籍として有名な鉄則本を買いましたが1章すら終わっていません。今後進めていくことになります。
緑を目指す人にとっても役立つ書籍であることは間違いないので持っている方は進める方がよいと思います。筆者のさぼってる点を真似しないでください。
ABC典型アルゴリズムの学習
鉄則本もしてない、精進量も少ないとなると典型アルゴリズムはどこで学習しているのでしょうか。ADTやABCのコンテスト中です。必死にネット検索を行い使えそうなアルゴリズムを調べます。
コンテスト中は集中しているので時間対効果は良いですがこれもあまり真似しない方がよいです。先に知ることに越したことはないです。
現在扱えるアルゴリズム等を次に示します。
- 多重ループ
- bit全探索
- 幅優先探索
- 深さ優先探索
- 順列全探索
- 再帰関数
- 1次元DP
- しゃくとり法
- 連想配列
- 優先度付きキュー
- 累積和
書いたことはあるけど不安
- 二分探索
- 2次元DP, ナップザック問題
- エラストテネスの篩
- Union-Find
- ダイクストラ法
ちなみにテンプレートはほとんど用意してないです。実装するときに過去の提出からコピペして持ってくるか、一から実装しています。これはテンプレの作り方がよく分からないからです。
以下の雛型で実装しています。
//範囲外参照を教えてくれる 提出時コメントアウトを忘れると最悪TLEする.
#define _GLIBCXX_DEBUG
//GCCの一括インクルード 競プロならではの書き方.
#include <bits/stdc++.h>
//std::cin が cinで書けるようになる. これも競プロならでは.
using namespace std;
//いわゆるrepマクロ カウンタ変数のミスを減らせる.
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
//std::sort()やstd::reverse()の引数に.
#define all(a) (a).begin(), (a).end()
//長いので省略.
using ll = long long;
//それぞれ2^30, 2^60より大きい.
const ll INF32 = 2e9;
const ll INF64 = 4e18;
//YesNo判定問題で使う.
void printYN(bool ok){
if(ok)cout << "Yes" << endl;
else cout << "No" << endl;
return;
}
int main() {
return 0;
}
(番外)AHCに参加する
実はAtCoderのレーティングは2種類存在します。ひとつはABC, ARC, AGCで変動するアルゴリズムのレーティングで、もうひとつがAtCoder Heuristic Contest(AHC)で変動するヒューリスティックのレーティングです。
AHCはより最適解に近い解を出すことを目指すコンテストです。コンテスト時間は短いもので4時間、長いもので10日間に及びます。初心者から上級者まで同じ問題に取り組みます。出力形式さえ満たしていれば正解と判定されいくらかの点数が貰えます。そこから少しずつ改善を繰り返しスコアを伸ばすことがAHCの楽しいところです。まずは正解するだけでも気軽に参加してみてはいかがでしょうか。
私はAHC041~044に参加し、レーティングは1164になりました。入水まであと少しです!
あとがき
レーティング推移を見てみると、ABC396まで若干失速気味だったのがABC397,398で大きく伸ばして入緑まで至っています。ひとつ心当たりがあるとすれば、ABC397の週にはADTに7回参加したことです。問題に向き合う時間を多く確保するのは本当に大事だと感じました。
競技プログラミングは敷居が低く、プログラミング未経験者でも取り組みやすい内容です。本記事が、少しでも競技プログラミングに興味を持つきっかけになれば嬉しいです。
また、現在灰色や茶色の方がこれから緑色を目指す参考になると幸いです。
AJL2025夏が終わるまでの入水を目指します!入水記事でお会いしましょう!