はじめに
時期が少し前になりますが、AtCoderで入茶できました。
ここまでの精進の仕方を備忘録も兼ねて残しておこうと思います。ちなみにAtCoderではレートによって色分けされており以下のような分類となってます。
| レーティング | 色 |
|---|---|
| 2800+ | 赤 |
| 2400-2799 | 橙 |
| 2000-2399 | 黃 |
| 1600-1999 | 青 |
| 1200-1599 | 水 |
| 800-1199 | 緑 |
| 400-799 | 茶 |
| 1-399 | 灰 |
茶色のレベル感はAtCoder社社長の直大さんの記事から引用しておきます。
茶色になる条件は、Ratingが400以上になることです。茶色で保証できる実力ですが、正直、AtCoder内ではあまり高いレベルではありません。ただ、ここにたどり着く前に辞めてしまう人が多いので、十分にやる気がある人であるとは言えるでしょう。
なお、他社転職サイトと比較すると、このレーティングでも上位1~2%の最高ランクに到達出来る人が数割いるため、一般的には十分高いレベルであると言えます。個人的な印象としては、
- 情報系の学生が茶色であれば、ちゃんと勉強してるなって印象になる
- 派遣で来たプログラマがAtCoder茶色だったら結構安心する
- 茶色があればエンジニアとしてアルゴリズム面においての安心感があるかと言われたら、正直物足りない
みたいな印象があります。
AtCoder（競技プログラミング）の色・ランクと実力評価、問題例 - chokudaiのブログ
自己紹介
高校数学の教員をやってます。プログラミングは趣味でちょこちょこ触っていたんですが、競技プログラミングというものを知って「面白そう！」と始めてみました。エンジニア職にも興味があるので、一つ自分の基礎力を示すものになればという思いもあります。
pythonを主に触っていたので、「文法はとりあえずわかるし、いけるっしょ！」と思っていました。あの頃の自分を殴りたいですね。簡単な文法はわかれど、しっかりと理解出来ていなかったので躓きまくりました…。
茶色になるための方針
最速で茶色になるのに考えられる方針としては2つあります。
- A,B,C問題を出来る限り速く解く
- A,B,C,D問題を安定して解く
後者の4問安定までいくのは時間がかかるし勉強するものも増えるので、やはり前者の3問最速がオススメです。自分もこの方針を念頭に置いて過去問を解いていました。具体的には1問に取り組む時間を決めておいて制限時間を意識しながら練習しました。
モチベーションUPのためにユーザースクリプトを入れよう
兎にも角にもまず最初にユーザースクリプトを入れましょう。
Tampermonkey
ユーザースクリプトを実行するのに必須なものです。まず最初にインストールしましょう。
AtCoder Easy Test v2
アルゴリズムがサンプルに対して合ってるかどうかを１Clickで判定してくれます。個人的には、これがあるだけでモチベーションと作業効率が爆上がりです。 絶対AC（問題のテストケース全てクリアすること）してやろうという気になれるので競プロ始める方は入れましょう！このスクリプトの詳細はAtCoder Easy Test を支える技術 - Qiitaを見てください。
他にもかゆいところに手が届く素晴らしいユーザースクリプトが様々あります。是非調べてみてください。
やったことと期間
基本的には以下のようなことをやってました。問題を解くにあたっては、AtCoder ProblemsというAtCoderの過去問一覧サイトがあるのでそちらを使ってます。難易度などのパラメータ別にまとめたり、自分の成績や頑張りを可視化出来たりと本当に素晴らしいサイトなので、是非使いましょう！
| やったこと | 期間（だいたい） |
|---|---|
| B問題まで確実に解けるようひたすら問題を解く | １週間 |
| 計算量についての勉強 | ２〜３週間 |
| C問題集中特訓&主なアルゴリズムやデータ構造の勉強 | １ヶ月 |
| 茶色問題をdifficulty順に解く | １ヶ月 |
B問題まで確実に解けるようひたすら問題を解く
まずは競プロに慣れるということでB問題までを確実に解けるようにしました。Bまでは文法の確認問題などの基礎が問われるので一つ自分の基礎力の指標になります。最初、やりたいことはわかるんだけど上手くコードに出来ないということが多かったです。
計算量についての勉強
ある程度基礎問が解けるようになってくると、C問題にも手を出し始めました。そうして問題を進めていくと、今度は解答を提出した際にTLEするものが出てきました。TLEとはTime Limit Exceeded(実行制限時間超過) の略で、つまりはエラーです。競プロには実行時間制限というものがあり、制限時間内に自分の提出したアルゴリズムが解答を出力する必要があります。↓こんな感じに問題文に表記されています。
大体の問題は2sec、２秒と設定されていますね。ちなみにメモリの制限もあり、これをオーバーすることをMLE、メモリ制限超過(Memory Limit Exceeded) と言います。
TLEを回避するにあたって、アルゴリズムの計算量というものを理解する必要があります。「うええなんか難しそう」と当初思ってやる気が起きなかったのですが、少しやってみると意外とシンプルで早く取り組んでおけばと思いました…。ここでは説明を省きますがこの記事の最後に参考にしていた先人たちのわかりやすい記事リンクを貼っておきますので、是非参考にしてみてください！
C問題集中特訓&主なアルゴリズムやデータ構造の勉強
計算量もなんとなくわかってきたのでC問題だけをやるようにしていきました。AtCoder Problemsで最新の問題から順にCだけやっていく形です。しかしこの最新から順にというやり方は止めておけば良かったと思ってます。後述しますが、難易度順（difficulty順）の方が良いです。
Cをやっていくに従って、今度は解答に必要なアルゴリズムがわかっておらず全く解けないということが多々起きました。「こんなアルゴリズムがあるのか〜考えた人すごいなぁ」と感心してばかりの時期です。これでは先に進まないと思い、勉強しました。自分が知ってるアルゴリズムやデータ構造で入茶に必要かなと感じたのは以下になります。
| 入茶に必要なアルゴリズム・データ構造 |
|---|
| bit全探索 |
| 二部探索 |
| 深さ優先探索（DFS） |
| 幅優先探索（BFS） |
| 素因数分解 |
| 約数全列挙 |
| 累積和 |
とにかく探索系はやっておきましょう！ 理解できれば解ける問題がぐっと増えます。
茶diff問題をdifficulty順に解く
C問題まで安定して解けてきたところで茶diff（難易度が茶色レート帯）問題に集中しました。AtCoder ProblemsのTop画面からListタブを選択すると下にProblem Listというのがあります。ここでDifficulty Fromタブを選択し400 - というものを選択します。
その後、下のリストのDifficultyの項目をクリックし問題難易度を昇順にしていけば準備OKです。
出てきた順に問題をガンガン解いていきましょう！この方法をとったことでかなり自分のレベルアップに繋がったという実感があるので是非やってみてください。
わからないとき、出来るだけ考える？orすぐ解答をみる？
過去問をやっていてわからない問題にぶつかるとき、設けた制限時間を超えてずっと考えてました。でも、そうすると貴重な練習時間を浪費していることに気づきました。制限時間までに解けなければすぐ解法を確認しましょう。まずはアルゴリズムの書き方を覚えることが大事です。自分で書けなければすぐ真似すべし。
おわりに
なかなか最初は思うように解くことが出来ず、「こんな難しいの解けるようになるのか…？やっぱり頭の良い人だけ楽しめるものなのでは…？」なんて思ってました。でも、諦めるのも悔しかったので続けていたら少しずつ理解でき競プロというものに慣れていくことが出来ました。何事も続けて慣れていくことですね。今後は入緑目指して精進します。Twitterやっているので良ければ一緒に頑張りましょう！
参考にしてた記事
競技プログラミングを始めて、右も左もわからないときにお世話になった記事をまとめてみました。良ければ参考までに。
経験者に学ぶ
最初に知っておきたい知識
- Pythonで競プロをしよう！〜入門者が知っておくべきTips〜
-
Pythonで"in list"から"in set"に変えただけで爆速になった件とその理由 - Qiita
- listがsetよりなぜ遅いのかめちゃくちゃわかりやすい
- 競プロでも使える Python の便利な標準ライブラリ Tips - Syakoo's Lab
最初に知っておきたい計算量
C問題以上に立ち向かうため
-
貰う DP と配る DP | アルゴ式
- DP（動的計画法）は入茶のための優先順位が低いんですが、余力のある人はやっておいて損なし
-
2部グラフ判定問題 - 30歳で競プロに目覚めた霊長類のブログ
- 2部グラフとその実装がよく理解できた記事
-
アルゴリズムとデータ構造入門 | アルゴリズムロジック
- アルゴリズムの理解にちょくちょくお世話になった