AtCoderで水色になりました。いわゆる色変記事です。
本記事では以下の4点について書きます。
- 競プロをしていて良かったこと・できるようになったこと
- 勉強したこと・改善案
- レート推移や目標ラインの話
- 環境やマクロの紹介
最初に自己紹介すると、自分は情報系出身のSEで、現在は2年目です。
今年の頭に競プロをはじめ、先日水色になりました。
「プログラミング未経験から～」「50歳を超えて～」みたいな少数派ではないですし、「たったN回で達成！」「M年の苦闘の末に」みたいなドラマもありません。
普通に勉強しているエンジニアが競プロを半年間そこそこ頑張ったみたいな記事です。
バッググラウンドや参加回数については③で詳しく書きます。
なお、競技プログラミングについてザックリ知っている前提で書きます。
「競プロってなに？」「水色ってどのあたりなの？」という場合は
が良くまとまっています。
① 競プロをしていて良かったこと・できるようになったこと
※具体的に「○○法ができるようになった」というのは省略します（強いて挙げるのであれば、精選中級編100はほぼ出来るし、精選上級編50はほぼ出来ません）
灰色→茶色
毎日プログラムを書く習慣が付いた
競プロを始める前はプライベートでコードを書いていたのは週3～4で、理論系の技術書や重めの社会科学本を読んでいたら丸1週間コードを書かないこともありましたが、競プロを始めてからコードを書く頻度と量が大きく増えました。
今は週6.5くらいコードを書けていて、競プロ以外も含めると月100時間くらいはコードを書けています。
アプリ開発や低レイヤが趣味で元々毎日書いている人はいいですが、「書きたいものができた時や勉強したいものがある時に書く」というスタイルだと、量が不足しがちです。「丁度いい難度の問題が降ってきて、正解不正解のフィードバックをすぐに貰える」という環境は、多くのエンジニアにとってアウトプット量を増やす有効な手段です。
計算量の見積もりが実践的にできるようになった
サイエンスとしてのアルゴリズムは院まで単位を取っていたので「ストゥージソートの計算量がO(N^(log3/log1.5))であることを証明せよ」は出来ましたが、「現代の家庭用コンピュータが処理できるのは1秒間に10^9回くらい」みたいな具体的な知識がありませんでした。
競プロを始めたことで、コードを見てO(N^2)であることやO(N logN)に改善できることが分かるだけでなく、「たかだか1000件で0.01秒の改善は重要でない箇所だからO(N^2)でも問題はない」という実践的な判断が下せるようになりました。
C++を使えるようになった
これまで書き捨てのプログラムはほとんどPythonで書いていましたが、最近は（Pythonの方がライブラリが便利な場合を除き）C++を使うことが多いです。
茶色→緑色
日常のプログラムをアルゴリズムを用いて高速化できるようになった
競プロ経験は日常では「処理を高速化できる」よりも「複雑な処理でもパパっと正確に書ける」ことで発揮されることが多いですが、100万件以上のデータを扱う場合はアルゴリズム力が活きることもあります。
具体的にこの時期に書き直したコードでは、素集合データ構造（disjoint-set）を用いることで、以前は4時間半要していた処理（Webスクレイピングして取得した200万件のデータの前処理）が、1秒未満まで高速化されました。別の例としては、動的計画法（DP）を用いて処理を劇的に高速化したコードもあります。
書き捨てプログラムの許容範囲が拡大し、腰が軽くなった
コーディングが速くなり、やれることも増えたため、以前は「自作したら半日潰れそうだから週末気が向いたらやるか」とTODOリストに追加しそのまま賞味期限切れしていたようなタスクを、仕事を終えてから晩ご飯までの間にサクッと作成できるようになりました。
競プロコミュニティに所属した
Twitter上で様々なバッググラウンドを持つ競プロerと交流するようになりました。
情報系学生や若手エンジニアだけでなく、50代の方やIT企業の社長もいれば、非エンジニア職や超優秀な高校生も競技プログラミングをやっているため、タイムラインの多様性が増しました。
特に自分より若く優秀な10代が大勢いる環境というのはいい刺激になります。
緑色→水色
高度なアルゴリズムを理解するための土台ができてきた
検索エンジンやDBMSなどの内部で使用されている高度なアルゴリズムが技術書で出てきた時、その基礎となるアルゴリズムの知識を知っていることで、理解度や理解速度が上がります。
なかにはウェーブレット木のような（現時点では自力実装が困難なレベルの）極めて高度なデータ構造もありますが、どんな操作がどんな計算量でできて嬉しいとか、どれくらいのアルゴリズム力があればこれを内部まで理解して応用できそうかというのが何となく分かるようになりました。
「アルゴリズムが得意です」と言えるようになった
アルゴリズムにおける「苦手」がなくなることで、「得意です」と口に出しやすくなります。
水色になるためにはABCの4問目はほぼ100%、5問目もそこそこ解く必要があるので、不得意分野の克服が要求されます。特に4～5問目では典型アルゴリズムの組み合わせや応用が出てくるので、二分探索してダイクストラでも、平面走査してmultisetで貪欲でも、尺取りしていもす法でも、座圧してBITでも、DPを累積和で高速化でも、数学問題でも、アドホック考察問題でも、重実装問題でも、得意不得意のバラツキはあっても出題されたら何とかしないとレートが上がっていきません。
不安分野があると「AtCoder緑色だけど、DPとかよく分からないし、競プロが趣味とかアルゴリズムが得意って言いにくいな」と思いがちですが、典型知識に漏れがなくなることで自信が付きます。
高度なデータ構造を使えるようになった
BIT（fenwick-tree）やセグメント木のような便利なデータ構造を少し使えるようになり、新しい手札が増えました。
② 勉強したこと・改善案
共通
コンテストに出る
コンテストは都合の付く限り毎回出た方がいいです。1番経験値が溜まります。
特に最初の15回は出ないと（レート計算の都合上）レートが実力未満の表示になるので、出るのが大事です。
解説放送を観てupsolveする
コンテスト終了後は公式や有志ユーザによる解説が提供されます。
その中でも公式のYoutubeチャンネルが出している解説放送はとても質が高く分かりやすいと評判です。
自分がギリギリ解けなかった問題あたりまで観て、理解して解き直すと実力が付きます。
自分が解けた問題も、より楽に書ける方法やバグりにくい実装があるかもしれないので観た方がいいです。
（逆に、自分が解けなかった問題より更に先の問題の解説は、その時点の実力では理解も再現も困難なので、観るメリットはあまりないです）
ところでupsolveというのは「コンテスト終了後に（解説を読むなりして理解を深め）解く」という意味ですが、競プロ用語らしいです。
2.(competitive programming, neologism) To solve a problem after the end of a contest.
引用：https://ejje.weblio.jp/content/upsolve
灰色→茶色
[やったこと]
螺旋本
書籍『プログラミングコンテスト攻略のためのアルゴリズムとデータ構造』（通称螺旋本）を読み、一通り解きました。
競技プログラミングで典型の動的計画法やグラフアルゴリズムも学べますが、より広い範囲を扱った書籍です。
タイトルから連想されるほどには、良くも悪くも競技プログラミングにはフォーカスしていません。
具体的には、「各種ソートやスタック・キューなどの実装」のような、より基礎的かつ教育的な内容も多いですし、逆に水色になるまで一度も使用していない高度なライブラリを自作する章もあります。
書籍自体は素晴らしく、とても勉強になりました。
特に、「学部2,3年レベルのアルゴリズムの講義を履修した直後の長期休暇」であれば、この本こそぜひやるべきです。
しかし競技プログラミングを始めて真っ先に手を付けるコンテンツとしては最善ではなかったと思います。
Boot camp for Beginners（Easy）
AtCoderの過去問から100問ピックアップしたブートキャンプシリーズです。
Easyは難度的には序盤は灰色下位で、終盤は茶色下位のスロープです。
無理なく毎日何問か埋められ、かといって虚無すぎないほどよい難度で、毎日のルーティンやウォームアップ向けのコンテンツと言えます。
テーマ別だとどうしても解法のメタ情報が入るので、こういう問題集はありがたいですね。
100問というのも、モチベを保ちながら埋めきりやすいボリュームです。
これを解き切る頃には、C++の基本や初歩的な実装テクニックに、時間や脳のリソースを割かずに済むようになっていました。
[やると良かったこと]
AtCoder Programming Guide for beginners
AtCoderが提供するC++の学習教材です。
cout << "Hello, world!" << endl;から始まり、一般的なC++入門書に加えて競プロで役立つ機能まで学べます。
C++以外のプログラミング言語に慣れていてC++の入出力が何となく分かる人も、これを1周することを勧めます。
自分はこれを知らずにコンテストに出ていたので、C++的に冗長なコードを書いたり、初歩的なところで躓いてコンテスト中にググってして、時間をロスしていました。これを先にやっていたらあと半月早く茶色になれていたと思います。
「AtCoder上達のガイドライン【初級編】」を読む
AtCoderの説明から茶色になる方法まで、初学者に必要な情報がまとまっています。
茶色→緑色到達
残業が多かったことや、調子よく5回で緑に上がれたこともあり、この期間はあまり精進できませんでした。
[やったこと]
けんちょん本
書籍『問題解決力を鍛える！アルゴリズムとデータ構造』（通称けんちょん本）を読みました。問題はあまり解いてません。
上述の螺旋本が「自力で典型アルゴリズムを実装し、ライブラリを自作する」というコンセプトな一方で、けんちょん本は「未知の問題をどう考えアルゴリズムを設計するか」というコンセプトです。
扱っているテーマとしては、グラフとDPが詳しめです。ネットワークフローなど、（コンテストでは高難易度の問題でしか扱わないので）茶色で読んでもレートに貢献しないものもありますが、「こんな凄い操作がこんな直感的なアルゴリズムで出来るんだ！」と感動してモチベーションアップには繋がります。
[やると良かったこと]
Boot camp for Beginners（Medium）
上述のブートキャンプのMedium版です。
Mediumは難度的には序盤は茶色下位で、終盤は茶色最上位～緑色下位のスロープです。
自分は茶色のうちに30問、緑になってから70問解いていましたが、間に合うなら茶色で全部解きたかったです。
上位コンテストのARCやAGCのA問題が混じっており、考察力や実装力も養われます。
B-C問題を解く速度が上がるとD問題に割く時間が増えますし、ABC2完やARC0完といったコンテスト爆死のリスクをかなり減らせるので、緑パフォの安定感が増します。
アルゴ式
弱点分野の茶色レベルの集中強化に適しています。
特にDP入門に定評があります。また、アルゴリズムとデータ構造の基礎コンテンツも充実しているので、CSのバッググラウンドがない場合はアルゴ式でじっくり土台固めをするのも良さそうです。
緑色到達→緑色上位
[やったこと]
Boot camp for Beginners（Medium）
上述の通り、緑になってから70問埋めました。
精選100問
「分野別 初中級者が解くべき過去問精選100問」を3ヶ月くらい掛けてやりました。
これを解ききれば知識的には十分水色～青色相当に達する神コンテンツですが、カロリーは高めです。
緑で初見で解くにはレベルが高すぎる問題もいくつかあり、1時間くらい掛けてどうしようもなかったら解説を読んでいました。
AHCへの参加
AtCoder Heuristic Contestに参加しました。
ヒューリスティック系のコンテストに参加するのは、アルゴリズム系のレートを上げる上で必要ではないですが、こちらも楽しいので一度は出てみてほしいです。
[やると良かったこと]
Boot camp for Beginners（Hard）
Hardは難度的には序盤は緑色下位で、終盤は緑色最上位～水色下位のスロープです。
水色になった今も30問くらいしか解いていませんが、この難度帯であれば緑色下位で手を付けるのがベストだったかなと思います。
緑色上位→水色
[やったこと]
毎日バチャ
7月のコンテストがない日は毎日21時から行われる「まよコン」に参加していました。
まよコンは「毎日開催」「コンテストと同じ時間」「コンテストとほぼ同難易度」「水～青のユーザが多数参加する」バチャです。毎日コンテストに1回参加しているようなものなので、毎日出て復習をすれば経験値が確実に急激に溜まります。
競プロにおいてバチャは極めて有効な練習方法ですが、それならずっとバチャだけやっていればレートが上がり続けるかというと、そんなことはないはずです。
まず、次のレベルを目指すための下地が整っている必要があります。具体的には「あと1問が惜しくも解けない。前提知識は揃っているんだけど、コンテスト中に詰め切れない」という状態が望ましいと思います。（あるいは、バチャは早解き力を高める効果もあるので、早解きに課題を感じている場合も有効です）
また、毎日コンテストに100分参加し復習を80分程度行う生活を半永久的に続けるのは普通は困難なはずです。
自分の場合は、精選100を完走したことでレートを伸ばすための基礎知識がインプットされており、バチャを続ければ1ヶ月以内に水色に上がる手応えがあった（実際23日で水色到達）ので、努力強度を高める選択ができました。
この辺りは受験や資格試験の過去問演習と似たような使い方でいいと思います。
[やると良かったこと]
EDPC
動的計画法（DP）に特化した教材です。
7月で水色になれなければこれをやる予定でした。
なお、もう少し簡単な緑向きの問題集としてはDP入門45があるみたいです。
（更に入門的な教材はアルゴ式にまとまっています）
ACL Beginner Contest
AtCoder Libraryの練習用コンテストです。
同等のデータ構造を自作して持っていてもいいですが、結局ACLを使うのが楽かなと思います。
（内部理解のために一度自作しておくことは重要ですが）
水diffまでの頻出はmodint、dsu > fenwicktree > scc、segtreeだと思います。
③ レート推移や目標ラインの話
この記事は「1年目SEが半年でAtCoderで水色になりました！」という内容ですが、この再現性について書きます。
仮に自分と同等のバックグラウンドの人が同じくらい勉強時間を割き、②の内容を学習して毎回コンテストに参加した場合、9割くらいは半年間で水色になるかなと思います。
一方で、平均的な1年目冬のエンジニアが、予定のない休日にコンテストだけ出る行為を半年間続けても、茶色になれない可能性があります。
まず、勉強量です。
こちらは、レート推移とAtCoder Problemsで見られる集計です。
レートの上がり方や解いた問題の難易度に強いクセはないと思います。
485問中、7月に頑張って1/3くらいを解いていて、あとは5か月で概ね均等です。
競プロを始めてから半年間でどれくらいコミットしていたかですが、開かれたコンテストのうち、ABCは24/26回、ARCは9/10回参加しています。
勉強時間は、平日の仕事後と予定のない休日の勉強時間を月150時間として、コンテスト参加も含めると1/3くらいを競プロに充てていました。7月は2/3近く充てているので、合計で半年弱で250～300時間競プロしていたことになります。
次に、バックグラウンドです。
競プロのレート初速に関係あるそうなところだとこんな感じです。
- プログラミングは普通にできる（C++は初級）
- 情報科学で修士号を取っている（アルゴリズムではない）
- アルゴリズムは学部講義、院試、院講義で学んだが競プロとは毛色が異なる。たとえばダイクストラ法について
- 動きは分かるし計算量の証明もできる。優先度付きqueueを使うのは言われて思い出した
- 自力で何も見ずに実装したら1時間掛かってもバグを取り切れないレベル
- 負回路があると無限ループすることは分かるが、負辺があるだけで計算量壊れることは知らなかった
- 数学力は旧帝大工学部の中では平均くらい
- パズルや頭脳ゲームは結構得意（元U26日本代表）
- 独身で、コンテストのある土日21時～は自由に空けられることが多い
特別ハイスペックでも精進量が多い方でもないですが、そこそこ有利なバッググラウンドがあってそこそこ勉強して、半年掛かって水色は妥当かなという感触です。
もちろん、超優秀な東大生が長期休暇にのめり込んで2ヶ月くらいで青色に到達することもあれば、非エンジニアで家庭を持っている人が数年間掛けて緑色に到達することもあります。
自分が楽しめるペースだとどれくらいを目標にするのがいいかというのは個人差があり、始めてみなければ分かりません。
まずはコンテストに参加してみて、茶色を目標に取り組むのがいいと思います。
それでもあえて、初めてから半年間での目標の目安を提示するのであれば、こんな感じでしょうか（1年間ならプラス1色？）
- [茶色目標]
- プログラミングを始めたが明確に作りたいものがない人
- [緑色目標]
- 非情報系卒のエンジニア、アルゴリズムの単位を取って興味の湧いた学生
- [水色目標]
- 難関大の情報系学生、プログラミングがそこそこ出来るエンジニア
- [青色目標]
- 長期休暇を競プロに捧げられる情報系学生、灘開成筑駒の中でもプログラミングにハマれる中高生
- [黄色目標]
- アルゴリズム系研究室の学生、競技数学にトップレベルに強くプログラミングもできる高校生
- [橙色目標]
- 未来のチャンピオン
（※統計取らずにTwitterや他の色変記事を読んだ上での体感で書いていますし、僕自身が競プロを始めて半年なので、上下に1色以上ズレているかもしれません）
「家庭があって月2回しかコンテストに出られないし就業後に勉強する時間もほとんど取れないので2年プランで目指す」「リモート定時上がりなので頑張って3ヶ月で目指します」のような調整もアリだと思います。
なお、これらはあくまで初速の話で、「競プロ始めた職業エンジニアだけど全然レート上がらん、新人が半年で水色って言ってたのに騙された」とならないように書きました。
初速と最終的な到達点は異なります。参考資料として、「色と実力評価」「色と精進量」「大学ごとの色分布」のリンクを置いておきます。これらを見るに、橙赤レベルとなると分かりませんが、青黄は競プロを始めてからの努力次第で到達し得ると言えそうですし、少なくとも緑水は継続的な精進で到達可能と言えそうです。
④ 環境やマクロの紹介
プログラミング言語
自分はC++を使用しています。
AtCoder含め競技プログラミングでは多くの言語から選択できますが、C++がオススメです。
・競プロで1番使われており、人に質問できる機会や参考にできるコードが多い
・解説や競プロ書籍でもC++が1番多い
・ACL（AtCoderで使える公式ライブラリ）やユーザライブラリが充実している
・高速であり標準ライブラリも豊富で、単純に優秀（Pythonなどと比べ、定数倍高速化で苦労することが少ない）
などが理由です。
現時点でC++を使えないという場合でもC++を勧めます。特に情報系学生やエンジニアであれば、人生のどこかでC/C++を学ぶ可能性が高いので、競プロと一緒にC++も始めましょう。
もちろんC++以外のユーザーも多数おり、有志解説もあるため、
・非エンジニアで、人生でPython以外を使うことはない
・Rustに浸かりきっており、C++のコードを直視できない
・熟達した言語を使いたいし、解説のC++の翻訳は余裕なので不利にならない
などの理由で他言語を選択しても、問題が解けなくなるわけではありません（定数倍高速化の必要性や標準ライブラリの都合で、難度が変わることはあります）
エディタ、ビルド設定
VSCodeです。
Windows + WSL + VSCodeで、大体これです。
{
"version": "2.0.0",
"tasks": [
{
"label": "C/C++: g++-9 compile file",
"type": "shell",
"command": "/usr/bin/g++-9",
"args": [
"-std=gnu++17",
"-I",
"/mnt/c/Users/HOGEHOGE/CompetitiveProgramming/",
"-DLOCAL",
"-I",
"/mnt/c/Users/HOGEHOGE/CompetitiveProgramming/ac-library/",
"-Wall",
"-Wextra",
"-Wshadow",
"-Wconversion",
"-Wfloat-equal",
"-ftrapv",
"-fstack-protector-all",
"-fsanitize=address,undefined",
"-ggdb",
"${file}"
],
"problemMatcher": ["$gcc"],
"group": {
"kind": "build",
"isDefault": true
}
}
]
}
ビルド設定はこんな感じでした。特殊なことはしていないので解説は省略します。ACLを導入する方法やコンパイラオプションは適宜ググってみてください。
テンプレートファイル、マクロ
以下のファイルを「ひな形」というフォルダにA.cpp～G.cppまで用意し、コンテスト前にコピーしてフォルダ名を「ABC261」のように書き換えています（アナログ）
最初はllとrepマクロから導入しましたが、気づいたら膨張していました。
あまりにも膨大なテンプレートを用意している人もいれば、全部スニペットに入れている人もいて、好みが分かれるところです。
注釈コメントを付けておきます。
// ここは競プロではサボりがちです
#include <bits/stdc++.h>
using namespace std;
// デバッグ用マクロです。詳しくは https://blog.naskya.net/post/meu0vkh5cpl1/
#ifdef LOCAL
#include <debug_print.hpp>
#define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (static_cast<void>(0))
#endif
// 節操ないですが、競プロでは便利です。
using ll = long long;
using vi = vector<int>;
using vl = vector<long long>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vpii = vector<pair<int, int>>;
using vpll = vector<pair<long long, long long>>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<long long>>;
using vvc = vector<vector<char>>;
using vvb = vector<vector<bool>>;
using vvvi = vector<vector<vector<int>>>;
using pii = pair<int, int>;
// ACLです。使わない時はコメントアウトしています。導入方法はググってみてください。
// #include <atcoder/all>
// using namespace atcoder;
// 競プロerはrepマクロが大好き
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
// 無くても困らない
#define INFTY (1 << 30)
// 浮動小数点の誤差を考慮した等式ですが、使わずに済むなら使わない方が確実です
#define EPS (1e-7)
#define equal(a, b) (fabs((a) - (b)) < EPS)
// DPやlong longの最大値最小値更新で重宝します。
template <typename T>
inline bool chmax(T &a, T b) {
return ((a < b) ? (a = b, true) : (false));
}
template <typename T>
inline bool chmin(T &a, T b) {
return ((a > b) ? (a = b, true) : (false));
}
// 手元で複数ケースを同時に試したい時に、tsの値を増やして適当なファイルからリダイレクトするだけで済むので便利です
// ※解説放送をしているすぬけさんのパクリ
struct Solver {
void solve() {
/* input */
/* solve */
/* output */
}
};
int main() {
int ts = 1;
rep(ti, ts) {
Solver solver;
solver.solve();
}
return 0;
}
Chrome拡張
自分が使っているものは全部ここに載っていました。
特に「AtCoder Easy Test v2」と「Comfortable Atcoder」はレートに直結します。
ハード
ノートPC+外付けモニタ2枚のトリプルディスプレイです。
キーボードはノートPCを使っています。Kinesis Advantage2でも同じくらいのタイピング速度は出ますが、VSCodeのショートカットに慣れていないのと、ルーズリーフに机のスペースを使いたいので、競プロでは使っていません。
マウスは最近トラックボールマウスにしました、便利。
考察はA4のルーズリーフにボールペンで書きなぐっています。ボールペンは3色くらいあると便利。
おわり
競技プログラミングはSEにも役立ちますし、楽しいです。ぜひ。