競プロやろうぜ！ - 競技プログラミングの概要と始め方

はじめに

この記事は モニクル Advent Calendar 2023 の 11日目の記事です。
筆者はコーポレートエンジニアとして勤務していますが、スキルセットとしてはコーポレートIT寄りのものが多く、プログラミングスキルの高い社内のエンジニアメンバーたちの仕事をいつも尊敬の眼差しで見ております。
モニクルに入社する少し前よりプログラミングのスキルを高める目的で競技プログラミングを始めてみましたが、ことのほかハマってしまい、今では自分の趣味の一つになりました。
この記事では競技プログラミングの概要と始め方を説明し、同志が増えたらいいなという思いで書きました！

競技プログラミング（競プロ）とは何か

競技プログラミングとは、プログラマーの論理的思考、アルゴリズム知識、コーディング能力を試すもので、参加者は与えられた問題に対して最も効率的かつ正確な回答を時間制限内でコーディングして提出するコンテスト形式の競技です。競技プログラミングはプログラミングスキルを向上させるだけでなく、アルゴリズムとデータ構造に対する深い理解を促進します。

国内外のコンテストサイト

競技プログラミングコンテストが行われているサイトはいくつかあります。発祥は海外のサイトですが、国内でもメジャーなサイトがいくつかあり、英語が苦手でも参加する事ができます。
国内外でメジャーなサイトは下記の様なサイトがあります。
次項以降では、国内で最も参加者の多いと思われるAtCoderを例にとります。

国内のコンテストサイト

• AtCoder

• yukicoder

国外のコンテストサイト

• Codeforces

• TopCoder

AtCoderについて

日本発のプログラミングコンテストサイトです。英語と日本語の両方で問題が提供されており、毎週コンテストが開催されています。
コンテストにはいくつか種類がありますが、まずは参加人数が多く、初級者向けのコンテストとなるAtCoder Beginner Contest (通称ABC)に参加するのが良いかと思います。ABCは毎週土曜日の21:00に開始し（偶に日曜開催の時もあるようです）、100分の間に難易度別に分かれたA～G（Exが追加されている回もあります）の問題を解いていきます。各問題に配点があり、正解数と正解タイムにより順位が決まります。

一番難易度の低いA問題では簡単なif文やfor文が理解できれば解けるレベルでプログラム初心者向け、C～D問題になると、二分探索、動的計画法、深さ優先探索といったアルゴリズムに対する理解が必要になってきます。F～G難易度になると高度な数学の知識も求められるようになります。

最近では企業がスポンサードしている事も多く、賞金が獲得できるチャンスもあります！
下記は過去行われたABCコンテストの一覧ですが、2023年12月現在、いろいろな企業がスポンサードしていることが分かります。

Contest Archive - AtCoder

参加可能な言語について

下記が使用できる言語の一覧ですが、多数の言語があり、自分の得意な言語で参加可能です！
筆者は言語の勉強も兼ねてTypeScriptで参加していますが、C++、Python、Javaでの参加者が多いようです。GoやRust、Haskellはもちろん、PascalやCOBOL、なでしこ（懐かしい・・・）といった言語もサポートされています。

使用できる言語とライブラリの一覧

AtCoderにおける色について

AtCoderでは、参加者のスキルレベルを表す色があります。コンテストにRatedという区分で参加すると、順位によってレートが上下し、レートごとに色付けがされます。下から順に灰色、茶色、緑色、水色、青色、黄色、橙色、赤色となり、通称レッドコーダーと言われる赤色のユーザーは100人ほど（上位0.3%）しかいません。
下記はAtCoder社の社長であるchokudai（高橋直大）さんによる各色のスキルレベルについての説明です。

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

簡単な問題のサンプル

AtCoderの問題は、基本的にすべて標準入力より入力を受け取って処理を行い、標準出力に対して出力を返す形式です。
AtCoderにユーザー登録後、練習コンテストのページよりサンプルを見ることができますが、下記に引用します。

問題文
高橋君はデータの加工が行いたいです。
整数 a,b,cと、文字列 s が与えられます。
a+b+c の計算結果と、文字列 s を並べて表示しなさい。

入力は以下の形式で与えられる。
a b
c
s

出力
a+b+c と s を空白区切りで 1 行に出力せよ。

https://atcoder.jp/contests/practice

入力例

1
2 3
test

出力例

6 test

1+2+3 は 6 なので、上記のように出力します。

AtCoderの環境設定をして練習コンテストに参加してみる（VSCode+TypeScript）

環境設定

※Windows11+WSL2上でVSCodeとNode.jsの環境は構築済みのものとします

AtCoder用のディレクトリを作り、そこでnpmプロジェクトの初期化とTypeScript、nodeの型定義ファイルのインストールを行い、tsconfigの初期化を行います。

npm init -y
npm -i -D typescript @types/node
tsc --init

VSCodeを開き、tsconfig.jsonの内容を下記のように書き換えます。

{
  "compilerOptions": {
    "incremental": true,
    "target": "esnext",
    "lib": ["esnext"],
    "module": "commonjs",
    "sourceMap": true,
    "esModuleInterop": true,
    "forceConsistentCasingInFileNames": true,
    "strict": true,
    "skipLibCheck": true,
    "outDir": "./dist"
  }
}

次に、VSCode上でデバックする設定を行います。「.vscode/launch.json」というファイルを作成し、下記内容を張り付けます。

{
  "version": "0.2.0",
  "configurations": [
    {
      "type": "node",
      "request": "launch",
      "name": "Launch Program",
      "skipFiles": ["<node_internals>/**"],
      "program": "${workspaceFolder}/main.ts",
      "console": "integratedTerminal",
      "preLaunchTask": "Compile"
    }
  ]
}

同様に「.vscode/tasks.json」というファイルを作成し、下記内容を張り付けます。

{
	"version": "2.0.0",
	"tasks": [
		{
			"type": "typescript",
			"tsconfig": "tsconfig.json",
			"problemMatcher": [
				"$tsc"
			],
			"group": "build",
			"label": "Compile"
		}
	]
}

これでデバックする環境が整いました。

サンプル問題を解いてみる

ディレクトリ直下にmain.tsというファイルを作り、下記コードを貼り付けます。これでreadLine()を呼ぶ度に標準入力からのデータが返ってきます。

import * as fs from "fs";

const input = fs.readFileSync("/dev/stdin", "utf8").split("\n");
let inputIndex = 0;

const readLine = () => input[inputIndex++];

前項の練習コンテストの問題を解くコードを組みます。
下記のコードが回答例です。

import * as fs from "fs";

const input = fs.readFileSync("/dev/stdin", "utf8").split("\n");
let inputIndex = 0;

const readLine = () => input[inputIndex++];

//標準入力より1行読み込み、変数にセットする
const a = parseInt(readLine());
//2行目の入力を変数にセットする
const [b, c] = readLine().split(" ").map(Number);
//3行目の入力を変数にセットする
const s = readLine();

const sum = a + b + c;
//a+b+c と s を空白区切りで 1 行に出力
console.log(sum + " " + s);

F5キーを押して実行してみると、ターミナル画面で入力待ちとなるので、入力例の入力を入れてみます。Ctrl+Dで標準入力を閉じることが出来ます。

VSCodeのターミナル画面

出力結果を見て、想定される出力例と合っていることが確認出来たら、ソースコードの提出を行います。コンテストのページより問題を開くと、下の方に提出スペースがあるので、提出言語を選択し、ソースコードを張り付けて提出します。

提出画面

提出ボタンを押すとジャッジ画面に遷移します。ここでは入力例以外にも様々なパターンでのテストが行われます。出題例以外にも、数字がすごく大きい場合や、問題での境界値ぎりぎりの値など、きちんと考慮したプログラムを組んでいないと、テストが失敗してしまします。テストがすべてパスした場合は「AC」となり得点になります。通らなかったテストケースがある場合は「WA」、決められた実行時間内に処理が終わらなかった場合は「TLE」となります。

テストがすべて通ったのでACです！

以上が問題を解く一連の流れになります。簡単ですね！今週のコンテストから参加できそうな気がしてきましたね！

初心者向け問題集

ここまで読んで、コンテストに参加してみようかな、でもいきなりはちょっと・・・と思った場合にはAtCoder Beginners Selectionという初心者向け問題集があり、こちらでいくつかの問題を解くと、何となく雰囲気に慣れることが出来るかなと思います。何問かこなして、デバックの流れや提出、ジャッジの仕組みを見ておくと、本番でもスムーズに取り組めるかなと思います！

AtCoder Beginners Selection - AtCoder

ツールやサイト

コンテストに慣れてきたら、AtCoderをより便利に利用するためのツールやサイトがあるので、それらを利用するともっと競プロが楽しめるようになります。以下はいくつかの例です。

• AtCoder Problems: AtCoderの過去問を解くことができるサイトです。問題の難易度ごとに分類されており、練習に最適です。また、他のユーザーの解答を参考にすることもできます。

• atcoder-cli: AtCoder CLI（Command Line Interface）はコマンドラインを用いてテンプレートを用いたソースファイルの作成、テストケースのダウンロードやテスト、解答の提出などが行えます。

アルゴリズムについての書籍

競プロでレートを上げるには、コーディングの速度も重要ですがアルゴリズムやデータ構造への理解が必要になってきます。アルゴリズムについて学ぶための書籍もあります。以下はいくつかのおすすめの書籍です。

• 競技プログラミングの鉄則 ~アルゴリズム力と思考力を高める77の技術~: 通称「鉄則本」と呼ばれ、競プロにおいて必要な技術を体系的に学ぶことができます。例題や演習問題も入っているので手を動かしながら理解することが出来ます。

競技プログラミングの鉄則 ~アルゴリズム力と思考力を高める77の技術~ (Compass Booksシリーズ)

• 問題解決力を鍛える!アルゴリズムとデータ構造: すみません、筆者はまだ未購入なのですが、上記鉄則本と共に競プロの実力を伸ばすために必要なアルゴリズムとデータ構造を丁寧に学べる書籍としてとても評判が良いので紹介させていただきました。通称「けんちょん本」と呼ばれています。

問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)

さいごに

少しでも競プロの世界に興味が持てたならば、ぜひ一度コンテストに参加してみてはいかがでしょうか？毎週土曜日21:00開始のAtCoder Beginner Contestでお待ちしています！
下記は筆者のAtCoderページです。

itaosan - AtCoder

※追記
記事を書き上げた後に、AtCoder公式より公式情報まとめサイトオープンのお知らせが出たことに気づきました！😇
始め方から上達への方法など、すごく充実している感じなので、こちらをよく読むと良いかと思います！！！

【お知らせ】AtCoderの公式情報まとめサイト「AtCoderInfo」がオープンしました！随時情報を更新していきます！ https://t.co/HzT7ykrTvO

— AtCoder (@atcoder) December 9, 2023