君は競技プログラミングを知っているか？私は知っています

この記事は、大阪工業大学 Advent Calendar 2023の13日目の記事です。
今回は以前投稿した記事で紹介した競技プログラミングについて詳しく紹介します。

競技プログラミングとは

プログラミング（主にアルゴリズムがメイン）についての問題が課されるのでそれを解いたスコアで競うものです。今回はAtCoderを例にして説明します。
2年生になるとデータ構造とアルゴリズムの授業で計算量の概念を習うと思いますが、難しい問題になるほど、計算量を制約内に収めるために、より高度なアルゴリズムを使ったコードを提出することが求めらます。

AtCoder

日本最高峰の競技プログラミングのオンラインコンテストサイトです。毎週初心者～中級者向けのコンテストが開催されています。コンテストの成績によってレーティングが変動するのですが、そのレーティングを使ってインターンに申し込んだり就活をすることもできます。

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

今回は僕がコンテストにどのように挑んでいるかを説明するので、それでコンテストの雰囲気やどんな問題が出題されるかをつかんでもらえると嬉しいです。

AtCoder Beginner Contest(通称ABC)

ほぼ毎週土曜日の21時から開催されるコンテストです。参加する（要アカウント作成）にはコンテストページに向かい参加登録ボタンを押します。

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

有名企業がコンテストのスポンサーとなっている回が多く、上位の成績を収めた人や抽選などで賞品がもらたりもします。僕も先日あった株式会社PFU主催のコンテストで学生応援賞に入選し高級キーボードのHHKB Studioがいただけることになっています（発送待ち）
参加登録ボタンを押すとページが遷移し、賞品の送付などのために個人情報が聞かれますが、面倒くさい場合や個人情報は入力したくない場合は何も記入せず一番下の参加登録ボタンを押してください。

参加登録ができると、レーティング変動ありで参加するか、レーティング変動なしで参加するか選ぶことができます。ここは好きな方を選んでください。

コンテスト開始時刻になると問題が公開されます。問題タブを開くとこのようなページに遷移するので問題（ABC330を例にしています）を解いていきましょう。問題は基本的に簡単なものからABCと並んでいるので頭から解くことをお勧めします。

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

ではA問題です。

問題文

$N$ 人の人
$1, 2, \dots, N$ がある試験を受け、人
$i$ は
$A_{i}$ 点を取りました。この試験では、
$L$ 点以上を取った人のみが合格となります。
$N$ 人のうち何人が合格したか求めてください。

制約
入力は全て整数

$1 \leq N \leq 100$

$1 \leq L \leq 1000$

$0 \leq A_{i} \leq 1000$

入力
入力は以下の形式で標準入力から与えられる。

$N$
$L$

$A_{1}$
$A 2$
$\dots$
$A_{N}$

出力
答えを整数として出力せよ。

このような問題となっています。幣学の学生なら必ず解けてほしい問題がＡ問題には配置されています。問題の構成は以下のようになっています。

問題文：問題の設定です。なるべく簡略に問題状況が書かれるので、ぱっと見で何言ってるかわかんないときがたまにあります。
制約：入力される数字や文字列の条件です。例えばこの問題だあと負の数が入力されたり、超大な数が入力されないということがわかるので、それの例外処理などは実装しなくてもいいよという意味合いを持ちます。
入力：入力される順序です。この例だとNとLが空白区切りで提供された後、
$A_{1}$ ~
$A_{n}$ が空白区切りで提供されることがわかります。
出力：最終的に欲しい答えの制約です。今回は整数で答えを出力することが求められています。

ではコーディングに移ります。言語や環境は自分の好きなものを使うのが一番ですが面倒くさい方は、AtCoderが実行を試す環境を用意してくれています。

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

使いたい言語を選択して、標準入力に与えらえたサンプル入力をコピー＆ペーストします。そのあと実行ボタンを押すと標準出力欄に出力が表示されます。答えが正常に出るコードが完成したら問題ページの一番下にある提出欄にコードを貼って提出ボタンを押すと提出になります。（ファイルを開くからソースコードファイルを提出することもできます）

提出されると自動で採点が始まりWaintingJudge(WJ)状態になります。少し待つと採点が終わり提出があっていたか間違っていたかの結果が返ってきます。正解であればAccepted(AC)という緑のマークになります。それ以外は何かしらの間違いを抱えていることになります。

結果の状態でよくみられるものは以下の通りです。

WJ(Waiting Judge)採点待ちです。
AC(Accepted)正解のことです。
WA(Wrong Answer)不正解のことです。
RE(Range Error)ゼロ割などをするとでます。
TLE(Time Limit Exceeded)ソースコードの実行時間が実行時間制限を超えると出ます、計算量を改善しましょう。
CE(Compile Error)コンパイルエラーです。ソースコードや提出言語が正しく選択できているか確認しましょう。

このような問題をたくさん解いていくことで、よりよい成績を狙うのがコンテストの一連の流れです。興味を持った人はぜひ一度トライしてみてください。DかE問題あたりまでであれば僕が解けていることが多いので、コンテストが終わった後にわからなかった問題など質問してくれれば喜んで答えます。

初心者はなにからはじめればいいか

これは初心者のなかで大きな課題であると思います。正直コンテストに参加してわからなかった問題やアルゴリズムを復習・追加学習を重ねて強くなっていくのが一般的な定石ではあると思います。しかし言語についてあまり知識がなかったり、アルゴリズムについての知識やデータ構造についての知識がないと解説をただ読んで理解してというのは、本当の初心者に対しては少々難しいような気もします。そこで何をしていけばいいかというのを紹介します。

定期的にコンテストに出る：これが一番大事だと思います。模試を受けるのと同じで定期的に自分の実力を測りましょう。
AtCoder Programming Guide for Beginners(APG4b)：AtCoderが用意しているC++のチュートリアルです。僕もこれをやって始めました。すべてやる必要はないですが2章と3章はB問題やC問題を解く足がかりになるのでおすすめです。
アルゴ式：解説が丁寧なアルゴリズムのサイトです。C++に加えてPythonの解説もあります。
Paiza：多言語の入門をしたいなら選択肢になるのではないでしょうか。Paiza自体にもスキルチェックといった競技プログラミングと似たようなシステムがあります。
競技プログラミング学生プロジェクト：多分僕が代表（でいいよね？）の学生プロジェクトです。近いうちに募集をかけますが、初心者向けの環境構築から始める講習会を予定しています。良かったら参加してね。

競技プログラミング学生プロジェクト

宣伝なんですが許して、、、

ACM国際大学対抗プログラミングコンテスト(通称ICPC) の国内予選に参加をする学生プロジェクトです。3人1組でチームを組んで作業を分担しつつ問題を解くコンテストです。国内予選は学内から参加できます。【実際に出される問題】

上位の成績を収める（大体上から50~70番目くらい？）と横浜で開催されるアジア大会横浜地区の上位大会に進出できます。僕はこの大会の進出を目指しています。チームメンバーを募集しています（）

初心者向けに環境構築から始める講習会（オンライン（録画？）と対面のハイブリッド予定）や、中級者向けに高度なアルゴリズムを勉強して教えあう勉強会などをやりたいな～とざっくり考えています。
人が集まれば、アルゴリズムだけでなく、ヒューリスティックコンテストや、ゲームAIを作成するCodinGameや機械学習コンペティションのKaggleなども楽しくできたらなーと画策しているので、興味ある人は僕に声をかけるか、募集があったときに参加してもらえると嬉しいです。
とにかく外部で行われているコンテストに積極的に参加して、どこかで結果が残すことを目標としたいです。

その他コンテストサイト

Codeforces：ロシアの競技プログラミングサイトです。多分現状で世界最大規模かな？
YukiCoder：有志の方が運営しているサイトです。好きに作問した問題を投下できるので結構活発です。
AOJ：会津大学のオンラインジャッジシステムです。
CodinGame：ゲームAIを開発してたたかわせてランキングするコンテストサイトです。
Kaggle：いわずと知れた機械学習のコンテストサイトです。

Heuristic

アルゴリズム興味ない人はこっちはどうでしょうか。ヒューリスティックコンテストは完全な正解がない・もしくは完全な正解を得るのが難しい問題に対してより良い解を得るためのプログラムを考えるコンテストです。例えば巡回セールスマン問題をご存知でしょうか。この問題を解くためのアルゴリズムで多項式時間のものはありません。
これ以外にも全部の組み合わせを試せば正確な解がわかるけど、実際にすべての組み合わせをためすと時間が膨大にかかってしまったり、すべてを試す余裕がないといった課題を解くコンテストが存在します。こういったコンテストはコンテスト期間が長いので特定の時間に時間を作るのが難しいといった人にもお勧めできます。

だいぶ長くなってしまったと思うのですがこの辺で締めたいと思います。万人が楽しめるようなものではないとは思いますが、すくなくとも僕は楽しめているので仲間が増やせたらいいなと思います。
わからないことや聞きたいことがあれば、ぜひ気軽に声をかけて下さい。