エンジョイ勢

競プロなどのことについて書きます。

競プロを始める方へ〜競プロはじめの第一歩〜[AtCoder][競プロ]

はじめに

 こんにちは。灘中学新2年生(2021年時点)、水色コーダーのAtCoder:ID:T__T)です!4月ということでこれから後輩が沢山入ってくるだろうということもあり、競プロを始める際にまず何をすれば良いかを自分なりにまとめてみたいと思い、この記事を書いています。
 AtCoderって何?競プロって何?始めたばかりで何をすれば良いかわからない!という方にも分かりやすいものとなるよう、なるべく丁寧に書いているので(一日で書き上げてるなんて言えない)、是非ご覧ください。間違いなどがありましたら、TwitterのDMやコメントなどで教えてくださると幸いです!

AtCoder、競プロって一体何?

競プロって何?

 まず競プロ(競技プログラミング)というものが何か、Wiki先生に聞いてみましょう

競技プログラミングでは、参加者全員に同一の課題が出題され、より早く与えられた要求を満足するプログラムを正確に記述することを競う。コンピュータサイエンスや数学の知識を必要とする問題が多く、新卒学生の採用活動などに使われることもある。多くのコンテストでオンラインジャッジが採用されている。また、競技プログラミングに参加する人を「競技プログラマ」または「競プロer」と呼ぶことがある。

このように、与えられた問題をいかに早く正確に解くかというのが競技プログラミングです。難易度は幅広く、プログラミング言語を少し齧っただけでもできるようなものから、数学の知識や特別なアルゴリズム(普通にやると時間がかかるものを高速に計算したりするための考え方)を駆使しないと解けないものまで様々です。
 そこで「数学は苦手だし無理だ!」「プログラミングなんて難しそう」と思われる方もいるかもしれませんが、大丈夫です。僕も数学や算数は苦手な方ですが、しっかり精進すれば(競プロ界隈では、問題を解いたりすることを精進と言ったりします)問題なくカバーできます!
 その競技プログラミングが行われているサイトとして有名なものにはAtCoderCodeforcesTopcoderなどがあります。また、JOIなどをはじめとした情報オリンピックも基本的に競技プログラミングで競います。この記事では特にその中でも、日本で最もメジャーなAtCoderについて取り上げていきます。

AtCoderって何?

 先程紹介した通り、AtCoder競技プログラミングサイトの一つです。社長は高橋直大(chokudai)さんという方です。日本の会社なので、日本語で競プロに触れることができ、初めての方には打って付けであると思います。そんなAtCoderに取り組む上で重要なことをいくつか紹介します。

コンテスト

 AtCoderでは基本的に毎週土,日曜日の夜21時頃にコンテストというものが開かれ、毎回3000人から10000程度の競技プログラマーが参加します。コンテストは後述のレートというものに影響してきます。コンテストには主に4種類のものがあります。それぞれのコンテストにはスポンサーがつくこともあり、賞金が出ることもあります。AtCoderではコンテストには様々な言語で出られますが、特に人気なのはC++,Python,Ruby,Rustなどでしょうか。

ABC(AtCoder Beginner Contest)

 一番オーソドックスなコンテストです。はじめての方はまずこれに参加すると良いでしょう。基本的には難易度順にA~Fまでの問題があり、それぞれ100点~600点です。初めての方はまずA,B問題を解けるようになることを目的に、そこから順番に上を目指していくと良いでしょう。

ARC(AtCoder Regular Contest)

 これは中級者〜上級者まで向けのコンテストです。初めての方が参加するにはお勧めできませんが、ある程度実力がついてくるととても楽しいコンテストになること間違いなしでしょう。

AGC(AtCoder Grand Contest )

 これは完全に上級者向けのコンテストです。筆者もまだ参加したことがありません...このコンテストを楽しめるように実力をつけていきましょう。

AHC(AtCoder Heuristic Contest)

 これはまだ始まったばかりのコンテストで、少し特殊なコンテストです。マラソンと呼ばれることもあります。具体的には、問題としてゲームのようなものが与えられ、何時間から何週間という長い時間をかけて、そのゲームでなるべく高得点を取れるようなプログラムを書くことが要求されます。先程の3つとは大きく違いますが、初心者でも時間をかければ上位に食い込めるかもしれません。

レート

 レートはコンテストの成績(パフォーマンスと呼ばれ、レートと同じ様に数値化されます)を元に決まります。AtCoderではレートに応じて色というものが決められており、この色が上がることを一つの目標にしている人も多いです。色は
黒色・・・コンテスト未参加
灰色・・・レート0~399
茶色・・・レート400~799
緑色・・・レート800~1199
水色・・・レート1200~1599(筆者はここ!)
青色・・・レート1600~1999
黄色・・・レート2000~2399
橙色・・・レート2400~2799
赤色・・・レート2800~
というふうになっています。そしてこれは間違いなく、精進をすれば水色までは確実に到達できます。まずは茶色、緑色、、とどんどん上を目指して行ってください!

AtCoderで競プロを始めよう!

1.アカウント登録

 まず最初に、アカウント登録を行いましょう。国や誕生年、所属などは後から変えられるので一旦適当でもいいとは思うのですが、ユーザー名は一度しか変えられないためよく考えて決めましょう。

2.プログラミング言語を学ぼう!

 AtCoderは様々な言語で取り組むことが可能ですが、ここではC++の使用をオススメします。なぜならC++は非常に高速であるため、高難易度問題などでも対応しやすいから、そして何よりAtCoder社がAPG4bというC++の解説を用意してくれているからです。
 APG4bは4章構成になっています。AtCoder Beginner Contest のA,B問題を解くための知識は基本的に1章に、C問題を解くための知識は基本的に2章に、D問題以降を解くための知識は3~4章に乗っています。勿論、言語を理解したからといって全て解ける訳はありません。しかし、2章までの知識は、いわゆる「精進」を進めていく上でも最低限必要になるので、しっかり学びましょう!もし他の言語でやるという方もAPG4bの2章にあたるレベルまではまず最低限身につけましょう。

3.「精進」をしよう!

  AtCoderで強くなるためには「精進」が必須です。競プロ界隈では、問題を解いたりアルゴリズムを学んだりして練習することを精進と言ったりします。個人的には、水色になるところまでは精進をすれば到達できると思います。さて、その精進はどのように進めて行けば良いのでしょうか?そこでまず、精進を進める上で非常に重要なコンテンツ、AtCoderProblemsを紹介します。

AtCoderProblems

 AtCoderに取り組む上で不可欠なコンテンツとして、AtCoderProblemsというものがあります。このAtCoderProblemsには様々な素晴らしい機能があるのですが、その中でも、特に重要なものを紹介したいと思います。

Diffculty(diff)

 AtCoderProblemsの問題一覧ページを見ると、問題名の横に色のついた円があると思います。そこにカーソルをかざすと次の様になります。
これがDiffculty(diff)と呼ばれるもので、難しさの指標として利用されています。これは、レートXの人の50%が解ける時にdiffがXになります。diffはレートと同じ様に色をつけて茶diffとか灰diffとか呼ばれることもあります。ある程度プログラミング言語を学んだ方は、ABCのA,B問題の灰diffから順番に、自分にあったレベルの問題を解いていきましょう。

Table,List,User

 これらはProblemsのテキストボックスにユーザーIDを入れると見れるもので、精進の進捗を見ることができます。
例えばTableでは自分がAC(正解すること)した問題、WAなど不正解したままの問題、解いていない問題などを色分けしてくれます。 他にもUserでは自分が解いた問題の数をdiffごとにまとめてくれたり様々な情報がまとめられています。

Traning

 これはAtCoderProblemsでAccountにログインすると見れるものです。初めての方は何を解いてわからない!という方も多いと思います。そこで役に立つのがこのTraningです。初めての方は、まずこのTraningのEasy100問に載っている問題を解いていくことをオススメします。個人的にはこのEasyが簡単に思えてくる頃には茶色コーダになれると思っています。簡単に思えてきたらMedium、Hardと難問にチャレンジしていきましょう。(僕はほとんどこのTraninngの問題だけで緑コーダーになりました)

実際に問題を解いていこう!

 競プロではやはり一番大事なのは問題を解くことです。ちなみにAtCoderでは正解することをAC、間違うことをWA、実行制限時間オーバーすることをTLE、なんらかのエラーが起きること(例えば0除算や配列外参照)をREと表現します。たくさんACすることを目指しましょう。そこでここでは初めての方が問題を解くさいのことついてアドバイスしていきたいと思います。

問題を解く時の環境

 問題を解くときは直接提出欄にコードを書き込むのは基本的にやめましょう。まず、コードテストや自分の環境(VScodeなど)でコードを書いて、サンプルケースが合うかを確かめてから提出欄にコピー&ペーストして提出しましょう。僕の場合は2画面にして片方を問題、もう片方をコードテストやVScodeなどにしています。  また、難しい問題では考察が必要になることも多いのでなんらかの書き殴るものを用意することもオススメします。自分なりの競プロ環境を作り上げていきましょう!

問題でつまった時

 最初の頃は問題で詰まることがたくさんあると思います。そしてそれは恐らく知識が足りないことによるものです。ですから僕は、最初の頃はある程度考えてわからなかったらすぐ解答をみてじっくり理解につとめるべきであると思います。解けなくて苦しいこともあるかもしれませんが、精進を重ねていけば解けるようになります。どんどん新しい知識を蓄えていきましょう。

4.コンテストに出場してみよう!

 ある程度問題が解けるぞというレベルに到達したらコンテストに出場しましょう。最初のコンテストにはABCをオススメします。(ARCだと虐殺される可能性があります。)

コンテスト中の立ち回りについて

 初めての人はA問題から順番に解いていくのが良いでしょう。最初は全然解けなくても何も問題はないので楽しむことを大切にしましょう。ただし注意して欲しいのがなるべくペナルティを出さない(問題を間違えない)ということです。なぜなら、ペナルティを出すと解いた時間に5分が加算されるからです。たった5分と思うかもしれませんがそのたった5分が結果に悪影響を出すこともあります。しっかりとサンプルケースが合うかを確認してから提出しましょう。30秒のチェックを怠って5分失ってしまってはもったいないです。コンテストでは早く解くということは難しい問題を解くのと同じくらい大切になってきます。だからこそ急がば回れの姿勢で行ったほうがいいと僕は思います。
.
.
.
.
これ以降の内容は僕の入緑記事に載っている内容と同じものです。

入茶を目指そう!!

コンテストにて

一概には言えませんが一般的なABCコンテストにおいて、3完(A問題、B問題、C問題)を安定してそれなりに早いスピードで解くことができると入茶することができると思います。ARCコンテストは、基本的にはA問題が解ければ入茶には十分だと思います。早解きというのは意外に重要で、解くスピードでパフォーマンス(各コンテストでの成績がこのレートのレベルということを表す)が800近く変わるなんてこともザラです。順位表観戦などで時間を潰してしまわないようにしましょう。diffは灰diff、簡単めの茶diffが解けるようになると入茶の可能性はグンと高まるでしょう。

どんな問題を解けば良いか

A問題が解けない人

まずA問題が解けない人は、そもそもの言語に対する理解が浅すぎる可能性があります。言語をしっかり学んだ上で、問題文に書いてあることをしっかり実装できるように練習しましょう。

B問題が解けない人(diffが50~200程度の問題)

B問題が解けない人は、競プロの問題に慣れられていない可能性が高いです。先ほど紹介したAtCoder ProblemsのTrainingのEasyを解くことで競プロの問題にある程度慣れ親しめると思います。

C問題が解けない人(diffが300~600程度の問題)

C問題が解けない人は、愚直に実装はできるものの、少し考えなければいけない問題や、アルゴリズム、典型問題などが解けない可能性が高いです。 先ほどのTrainingのEasyに加えてMediumにもチャレンジしてみるといいでしょう。

入茶に必要なアルゴリズム・考え方

1.累積和

まず最低限考え方を身につけて欲しいのが累積和です。累積和は簡単にいうと配列上の要素の和を速く求められるアルゴリズムです。どういうものかは、けんちょんさんの記事累積和を何も考えずに書けるようにする! #AtCoder - Qiita に詳しいと思います。身につけてない方は是非読んでみてください。

2.計算量

(時間)計算量というのは、そのプログラミングの実行速度がどれくらいになるかを大まかに見積もることのできるものです。計算量を身につけると、その問題が問題文に書いてあるとおり実装すればいいのか、それとも工夫しなければいけないのかが大まかに見積もることができるようになります。C問題などになると愚直に解くだけでなく、計算量を考慮しないといけない問題も多くあります。詳しくはこれまたけんちょんさんの記事計算量オーダーの求め方を総整理! 〜 どこから log が出て来るか 〜 #新人プログラマ応援 - Qiitaを是非読んでみてください。

入茶するためにはあまり特殊なアルゴリズムなどは必要ありません。それよりも、競プロに慣れることができるまで問題を解いてみましょう!

入緑を目指そう!!

コンテストにて

一概には言えませんが一般的なABCコンテストにおいて、4完(A問題、B問題、C問題、D問題)を安定してそれなりに早いスピードで解くことができると入緑することができると思います。ARCコンテストは、基本的にはA問題,B問題が解ければ入緑には十分だと思います。緑下位diffが安定して解けるようになることと、灰・茶diffをいかにハイスピードで解くかということが重要になってきます。

どんな問題を解けば良いか

基本的には茶diff、それが解けるようになってきたら緑diffを解くという流れでいいと思います。綺麗に解けなかった問題は、解説を見て、綺麗に解く方法を知ることも多いにプラスになると思います。精進する問題がわからなければ、AtCoder ProblemsのTrainingのMedium、Hardを解けばいいと思います。ちなみにHardは僕は90問ぐらいしか埋められていません()(埋めろ矢)。

入緑に必要なアルゴリズム・考え方

1.累積和・いもす法

茶色コーダーの方なら累積和は使えると思いますが、いもす法は履修できてなかったり、本番で使えないという人が多いのではないでしょうか?ですが入緑するためには是非身につけて欲しいアルゴリズムです。これは名前の元にもなっているいもす法 - いもす研 (imos laboratory)を是非ご覧ください。

2.DFS BFSなど...(グラフ)

僕もとても苦手ではあるのですが、入緑するためにはグラフ問題が解けなくてはいけません。(悲しい)まず最低限、DFS,BFSは身につけましょう。これまたけんちょんさんの記事
DFS (深さ優先探索) 超入門! 〜 グラフ・アルゴリズムの世界への入口 〜【前編】 #AtCoder - Qiita
BFS (幅優先探索) 超入門! 〜 キューを鮮やかに使いこなす 〜 #AtCoder - Qiita
を読んでみると良いと思います。また、ワーシャルフロイド法をはじめとした、他のグラフ探索アルゴリズムに関しても、問題に出てくるたびで良いので学習していきましょう!僕もグラフについてはまだまだ知らないことだらけなので学んでいきたいです。

3.二分探索

二分探索も使えるようになっておくと良いと思います。二分探索はO(log N)で指定した値を見つけることができます。C++STLvectorで二分探索を行う場合 index(何番目か)を求めるにはbeginを引きます。また、イテレーターの値が欲しい場合は*(イテレーター)をやると良い感じに値が得られます。僕も詳しい中身などは知らないのですが、良い感じの記事を見つけられていないので、見つけられたら追記します。

4.bit全探索

bit全探索は緑diff以降では特に良く使うアルゴリズムです。簡単にいうと000...0~111...1の2桁数個の数列を生成できるアルゴリズムです。計算量は基本 O(N*2N)です。例えばNコの箱があってそこにボールを 入れるor入れない を全通り調べよう!などという時に使えます。これはAPG4bをみるとわかると思いますAC - 3.05.ビット演算この記事の中でbit全探索について述べているので、履修してない人は読んでみてください。

5.DP=動的計画法(簡単なもの)

DPは難しいやつはことごとく難しいです、、ですがDPの考え方自体はシンプルなもので、1次元DPと呼ばれるものはDPのDと言われることもあるD問題でよく出ます。要は前の結果を利用して次の結果を求めるということです(雑) 。詳しくはまたまたまたけんちょんさんの典型的な DP (動的計画法) のパターンを整理 Part 1 ~ ナップサック DP 編 ~ #機械学習 - Qiitaなどを読んでみると良いと思います。

6.MOD(modinv modpowなど)

競プロではよく109+7などでMODを取る問題が出てきます。MODの足し算やただの掛け算ならば良いのですが、割り算や何乗もするのは少しややこしいです。正直考えてどうこうなるものでもない気もします(一部の天才は除くのかもしれない)。ですから、MODについてしっかり学習しておくことは大切になるでしょう。そこでまたまたけんちょんさんが神記事を書いてくれているので是非チェックしてみてください。
「998244353 で割ったあまり」の求め方を総特集! 〜 逆元から離散対数まで 〜 #競技プログラミング - Qiita

7.その他

ここに書ききれてないアルゴリズムもたくさんあります。(例えばしゃくとり法など)ただし、アルゴリズムの数は膨大なので、問題を解くたびに新しい知識を吸収していくことも大切になると思います。何が言いたいかというと、精進大事。 また、競プロでは数学というものの影響も大きいと思います。例えばmodinvを求めるのには何だかよくわからない数学を使います。また、場合の数や確率の問題でも数学が必須となるでしょう。特に何をやれということはないかもしれないですが、数学も適度に精進しましょう。僕も頑張ります。

最後に

 AtCoderは本当に楽しいです。また、普通のゲームをするよりかはよっぽど有益なコンテンツであると思います。気軽に始めてみてください!極度精進!!
※訂正・質問などございましたらコメントやTwitterのDMなどでお知らせくだいましたら幸いです。お願いいたします。