【AtCoder】C++未経験から1年で入茶した話

0. はじめに

どうも、Yuulisです。
先日 2022/02/14に開催された、AtCoder Regular Contest 135をもって入茶することができたので、これまでを振り返って思うところなどをいろいろ書いていこうと思います。

1. 自己紹介

・高校1年生
・プログラミング歴 : 1年ぐらい
・AtCoder使用言語 : C++
・資格など : 基本情報技術者(FE), 数検2級, 英検準1級 etc.
・Unityで強化学習をして遊んでいる
・簡単なポートフォリオ ↓

2. AtCoderの茶色とはどのくらいのレベルなのか

AtCoder社長のchokudaiさんのブログ記事から引用します。

茶色　（Dランク Rating 400~799　上位50%）
茶色になる条件は、Ratingが400以上になることです。茶色で保証できる実力ですが、正直、AtCoder内ではあまり高いレベルではありません。ただ、ここにたどり着く前に辞めてしまう人が多いので、十分にやる気がある人であるとは言えるでしょう。

なお、他社転職サイトと比較すると、このレーティングでも上位1~2%の最高ランクに到達出来る人が数割いるため、一般的には十分高いレベルであると言えます。

個人的な印象としては、

情報系の学生が茶色であれば、ちゃんと勉強してるなって印象になる
派遣で来たプログラマがAtCoder茶色だったら結構安心する
茶色があればエンジニアとしてアルゴリズム面においての安心感があるかと言われたら、正直物足りない
みたいな印象があります。スキル的に確実に保証出来る点は、

標準入出力、if、forなどの単純な操作はできる
問題文を正しく理解し、計算量を考えない仕様通りの実装をすることが出来る
の２点です。ただし、完全に上の能力しか持っていないと茶色になることはできず、

MARCH理系学部以上に入れる程度の数学力や論理的思考力があり、数学的な工夫が必要な問題を正解出来る
典型アルゴリズムに関する知識を多く持ち、探索による全列挙や単純な動的計画法など、典型的な問題に正解することが出来る。
コーディングや読解速度が早く、単純な問題を早く正確に実装することが出来る
などの特徴を持っていなければ、茶色になることはできません。このレート帯に達する人は本当にバラバラなので、保証出来る点は少ないですが、何かしらの強みを持っていなければ、茶色に到達することはできません。

もちろん、保証出来る点が少ないと言っても、コーディング試験でおなじみFizzBuzzなんかは全員が当然一瞬で組める水準です。

出典 : AtCoder（競技プログラミング）の色・ランクと実力評価、問題例

要約すると、基本的なアルゴリズムぐらいは書けるようになったね・脱AtCoder初心者、ぐらいでしょうか。

3. 未経験から初ABC参加まで

3-1. AtCoder登録のきっかけ

競技プログラミングというものの存在は中学生ぐらいから知っていたのですが、高校受験もあり、そのころはScratchをちょこちょこ触っていたぐらいだったので、なかなか参加する気は起きませんでした。

しかし、高校受験終了後、なにか新しいことをしたいと思い、再び競技プログラミングの世界に興味が湧きました。

そこで、

この記事を参考に、とりあえずコンテストに参加してみよう、と思いました。

3-2. C++を選んだワケ

当時の私は特に「この言語なら自信をもって書ける！」というものはなかったので、正直どの言語を選んでも構文・仕様などの勉強が必要なことは変わりませんでした。

そこで、AtCoderの提出言語割合を調べた方がいたので、この方の記事を見たところ、

C++が圧倒的多数です。

解説の多くもC++で書かれていることが多いし、処理速度もトップクラスです。しかも、標準ライブラリが豊富。以上から、私はC++を選択しました。

だからと言って、無理に使い慣れていない言語で一から始める、といったことはしなくてよいでしょう。AtCoderで最も簡単とされているAtCoder Beginner Contest (ABC)のA問題を解くうえでも、if文や四則演算など、多少の知識は必要です。その部分の勉強から始めなければならないくらいなら、普段よく使っている言語でやってみるのが一番いいと思います。

3-3. いざ初陣！ → 爆死

登録したのが土曜日ということもあって、その日の21時から早速コンテストがありました。
果たして結果は...

やりました！灰コーダーになれました！
はい、レート1が付きました。

今思ってみても、C++がまともに書けないのによく参加したなぁ、とは思っています。あまりに無謀です。

ちなみにA問題はこんな感じ。

定価 $A$ 円の商品が $B$ 円で売られているとき、この商品の売値は定価の何パーセント引きですか？
答えを小数で出力せよ。想定解答との絶対誤差または相対誤差が$10^{−2}$以下であれば正解と判定される。
・$A$, $B$ は整数
・$1 \leq B \leq A \leq 10^{5}$

まあ、いきなりつまづきやすい小数出力の問題に当たったことも不運でしたけどね...

必死こいてググりまくって、71:05かかってACできました。

4. 入茶するまでやったこと

4-1. まずはC++の基本を身に付ける

当時はC++を全く触ったことがない状態だったので、まずは基本的な文法を身に付けるところから始めました。
幸いなことに、AtCoderにはC++を基礎から学ぶことができる教材が用意されています。AtCoder Programming Guide for beginners (通称APG4b)です。

この教材のいいところは、プログラムの説明だけではなく、その練習問題と自動採点システムがあることです。

この教材には、標準入出力から変数型、if文、for文、配列、C++の標準ライブラリの機能まで、C++でAtCoderを戦っていくために必須な知識はつくと思います。
1回で理解できなくてもいいので、C++が初めてという方は、まずはこの教材に取り組んでみることをおすすめします。

4-2. 毎日AtCoderに触れる！

最も大切だと思うのがこれ。
英語のリスニングなどでもそうですが、できるだけ毎日触れることは感覚を鈍らせないためにも重要だと思います。

非公式ですが、AtCoderの過去問がまとまっているサイト、AtCoder Problemsというところがあります。

ここを活用し、AtCoder Beginner Contest(通称ABC)のA~C問題1回分をできるだけ毎日(最近5、6か月のことですが)解いていました。

レートが50ぐらいになるまでは、A問題を多く解き、とにかくAtCoderの出題形式に慣れることを目的としていました。
レートが100前後までは、A、B問題を中心に、20分で2完を目標に、早解きをしていました。
これ以降は、C問題も積極的に解いて、データ構造やアルゴリズムの活用法を身に付けるようにしています。ABはだいたい15分で確実に解けるようにしておきたいところ。

解いた問題の総数をグラフで確認したい場合は、AtCoder Scoresの精進グラフを使うといいかと思います。

4-3. 学んだアルゴリズム

自分用のライブラリとして保存してある、または解いた問題に出てきたもの。
理解度↓
◎ : ほぼ確実に実装できる
〇 : 理解してる・実装は可能(バグらせる危険アリ)
△ : 理解・実装に不安/不可能

アルゴリズム	理解度	使用頻度
階乗	◎	高
基数変換	◎	高
文字列の回文判定	◎	高
最大公約数・最小公倍数	◎	高
線形全探索	〇	高
累積和	〇	中
平方数判定	◎	中
素数判定	◎	中
約数列挙	◎	中
二分探索	〇	中
順列全探索	〇	中
bit全探索	△	中
幅優先探索(BFS)	△	中
深さ優先探索(DFS)	△	中
再帰	△	中
動的計画法(DP)	△	中
2のべき乗判定	◎	低
各桁の和	◎	低
座標圧縮	△	低
メモ化再帰	△	低

正直、DPやBFS・DFSなどの高度なアルゴリズムは、茶色になるためには必要ないと思っています。それよりも、数をこなして様々な問題形式に触れ、早く解けるようにすることの方がレートを伸ばすためには大切です。

また、最近は累積和や順列全探索(next_permutation)を使う問題を目にすることが増えてきたように思います。

4-4. 学んだデータ構造

A~C問題を解くうえで必要になったデータ構造。
理解度↓
◎ : ほぼ確実に実装できる
〇 : 理解してる・実装は可能(バグらせる危険アリ)
△ : 理解・実装に不安/不可能

データ構造	理解度	使用頻度
int, long long	◎	高
string, char	◎	高
vector	◎	高
pair	◎	中
set(unordered_set, multiset)	〇	中
map(unordered_map)	〇	中
mint(ACLの機能)	〇	中
tuple	〇	低
stack	△	低
queue	〇	低
priority_queue	〇	低
dequeue	△	低
union-find	△	低

こちらは、できるだけ多く使えるようにしておくと、考察の幅も広がっていくと思います。特に、mapやsetはC問題で頻出です。

個人的には、
・pair型のsortに比較関数を使えるようにしておく
・string⇔intの行き来
・アルファベットの操作
をマスターしておくと、ABを早解きするのに便利かもしれないと思っています。

5. AtCoder Problems データ詳細

AtCoder Problemsはまだまだ使いこなせていないので、これから頑張っていきたいところ。


※AtCoder Grand Contestは解いていません。

6. まとめ

茶色になるために必要だと思うことをまとめておきます。
・ABCに毎週参加する(ARCやAGCは出ても0完になりがちなので、モチベ維持が難しい)
・過去問(A~C問題)をできるだけ毎日解く
・アルゴリズムは最低限、データ構造はたくさん持っておくと安心
・レートが上がらなくてもあきらめない

これから入茶を目指す方の参考になれば幸いです。

次の目標は。高校卒業までに入緑かな。