⚠記事の内容は学生個人の見解であり、所属する学科組織を代表するものではありません。
はじめに
Advent Calendar３日目です！！
二日目はねふ君(@nefu_chem)の, 不確定性原理をもちいて鉛筆が立っていられる秒数を見積もるという話でしたね. とても面白かったです.
さて, 今回は少し物理とは離れて, 最近僕がハマっている競技プログラミングについて布教しようかなと思います（僕自身強くはないのでよくない記述があるかもしれませんがご了承ください）.
競技プログラミングとは？
競技プログラミング（競プロ）とは, とても簡単に言うと、制限時間内に与えられたいくつかの問題をプログラミングを用いて解き, それのパフォーマンス（より早くより多くの問題を解くほど偉い）を競う遊びです.
日本の中で最も有名な競技プログラミングサイトにAtCoder（アットコーダーと読みます）というものがあります. 今回はAtCoderを軸に競技プログラミングについて説明していこうと思います.
実際の問題を見てみよう！
競技プログラミングではどのような問題が出題されるのか実際に見てみましょう. 以下はAtCoder Biginner Contest 329（ABC 329）のA問題です.
ABC 328 A - Not Too Hard (100 点)
問題文
$N$問の問題が出題されるプログラミングコンテストがあります. $i = 1,2,\cdots,N$について, $i$問目の配点は$S_i$です.
配点が$X$以下である問題すべての配点の合計を出力してください.
制約
- 入力される値はすべて整数
- $4 \leq N \leq 8$
- $100\leq S_i \leq 675$
- $100 \leq X \leq 675$
入力
入力は以下の形式で標準入力で与えられる.
$N\ \ X$
$S_1\ \ S_2\ \ \cdots\ \ S_N$
この問題はif文とfor文（ループ）を書くことができれば正解できるでしょう. 以下は実装例です（言語はC++です）.
#include <bits/stdc++.h>
using namespace std;
int main(){
//とりあえずここから読みましょう.
int N, X; //N, Xは整数であると宣言します.
cin >> N >> X; //N, Xの入力を受け取ります.
int ans = 0; //このansにX以下の配点を足していきます.
for(int i = 0; i < N; i++){ //N回ループします.
int S;
cin >> S; //i番目の点数の入力を受け取ります.
if(S <= X){ //もしSがX以下なら
ans += S; //ansにSを足します.
}
}
cout << ans << endl; //ansを出力します.
return 0; //これは最初は気にしなくてもいいです.
}
このように, ABCのA, B問題は問題文に書かれていることをそのままプログラミング言語に表現すれば解ける問題が多いですが、C問題以降になると考察が必要だったり, アルゴリズムを用いないと解けない, つまり, 効率の良いプログラムを組まないと正解できないような問題が出てきます. これは計算量, 実行時間というものが深く関係しています.
実行時間について
コンピューターはとてつもない早さで計算しているように見えますが（実際とてつもない早さではあるが)、あまりに計算量が多いと実行時間は長くなります. AtCoderでは実行時間が2秒を超えるとTLE（Time Limit Exceeded : 実行時間制限超過）となり, これは不正解扱いとなります. C++では2秒で約$10^8$回の計算をすることができるので, この計算量を超えないようなプログラムを考える必要があります.
では, 実際に実行時間を考慮しないと解けない問題を見てみましょう.
ABC 085 C - Otoshidama
問題文
日本でよく使われる紙幣は,$10000$円札, $5000$円札, $1000$円札です. 以下, 「お札」とはこれらのみを指します.
青橋くんが言うには, 彼が祖父から受け取ったお年玉袋にはお札が$N$枚入っていて, 合計で$Y$円だったそうですが, 嘘かもしれません. このような状況がありうるか判定し, ありうる場合はお年玉袋の中身の候補を一つ見つけてください. また, ありえない場合は -1 -1 -1 と出力してください. なお、彼の祖父は十分裕福であり, お年玉袋は十分大きかったものとします.
制約
- $1 \leq N \leq 2000$
- $1000\leq Y \leq 2\times 10^7$
- $N$は整数である.
- $Y$は$1000$の倍数である.
入力
入力は以下の形式で標準入力で与えられる.
$N\ \ Y$
まずは計算量を気にせずに考えてみましょう. これは枚数が$N$になるような全てのお札の使い方を全探索して, $Y$と一致するものがあればそれを出力し, すべて探してもなければ -1 -1 -1を出力するというプログラムを書けばよいです. しかし, ここで制約を見てみると, $N$は最大で2000なので計算量は最大で約$2000^3 = 8\times10^9$回かかってしまい, TLEとなります（こういった解法を$O(N^3)$の解法と言ったりします）.
さて, ここからが競プロの醍醐味です. 考察をしてみましょう. いま, 使えるお札の枚数は$N$枚と決まっています. なので, 10000円札と5000円札を使う枚数さえ決めれば, 1000円札を使う枚数は自動的に定まります. つまり, 1000円札に関するループは削減できるので, 計算量は約$2000^2 = 4\times10^6$回に短縮することができました. (実装例(C++))
コンテストについて
AtCoderは基本的に毎週土曜日（たまに日曜のこともあります）のPM9:00から100分間のAtCoder Biginner Contest（通称ABC）を開催しています. ABCはA問題からG問題の全7問から構成されていて, アルファベットが進むほど問題も難しくなります.
他にもARC, AGCといったコンテストもありますが基本形はABCと同じで, 難易度がより高くなっています. こちらは不定期の開催となっています.
コンテストに参加するとレーティングが付きます（Unrated参加すればレーティングを変化させずにコンテストに参加することもできます）. このレーティングを上げるために競プロをやっているといっても過言ではありません()
レーティングについて
AtCoderのレーティングは次のように色分けされています. 1
| レーティング | 色 | 位置 | 評価 |
|---|---|---|---|
| 1 ~ 399 | 灰色 | 上位100% | |
| 400 ~ 799 | 茶色 | 上位50% | 学生なら優秀だが, エンジニアとしては物足りない. |
| 800 ~ 1199 | 緑色 | 上位30% | 学生なら超優秀. エンジニアとしても安心感がある. |
| 1200 ~ 1599 | 水色 | 上位15% | 半数以上のIT企業において, アルゴリズム能力についてはカンスト. |
| 1600 ~ 1999 | 青色 | 上位7% | 8割以上のIT企業において, アルゴリズム力はカンスト. |
| 2000 ~ 2399 | 黄色 | 上位3% | 研究職・研究開発などや, 高度なアルゴリズムを要求される開発現場で重宝される. |
| 2400 ~ 2799 | 橙色 | 上位1% | 研究開発やアルゴリズムが大切な会社でしかこの力を活かせない. |
| 2800以上 | 赤色 | 上位0.3% | (chokudaiさんが言うには)化け物. |
ちなみに僕のレーティングは茶色なのですが, あまり自分では優秀だなと実感はしていません. みっちり取り組めば三か月ぐらいで到達できるレベルかなと思います.
緑色に行こうと思うとしっかり基本的なアルゴリズムを学ばないといけないなと思います. それ以降のレベル感は僕にはまだ想像できていません.
教材の紹介
競プロの教材はネットにごろごろ転がっています. いい時代ですね.
初心者(灰色)向け
-
C++入門 AtCoder Programming Guide for beginners (APG4b)
AtCoder公式の教材です. これをやればC++の基本的な書き方を身に着けることができるでしょう. とりあえずは第二章まで読んで少し練習すればABCのA, B問題はだいたい解けるようになります. -
レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【初級編：競プロを始めよう】
本記事を書くにあたりこの記事を参考にしました. とても詳しい内容になっているので本記事を読んだ後にこの記事を読んでもらえると楽にAtCoderに入門できるかなと思います. -
AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～
中級者～上級者(茶色以上)向け - レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】
これ以外にもAtCoderの問題にはほとんど全てに解説がありますし, YouTubeの公式チャンネルでも解説放送が配信されています.
書籍での有名な教材として『プログラミングコンテストチャレンジブック（通称蟻本）』も挙げておきます.
習うより慣れろ！！
習ってるだけでは最初はやっぱりすぐ飽きが来てしまいますし2, 自分で考察するという競プロの醍醐味が損なわれてしまいます. なので, 基本的な部分が書けるようになったらコンテストに参加してみることをお勧めします. この記事の投稿日(2023/12/03)のちょうど一週間後の日曜日（土曜日ではないことに注意して下さい）にABC 332が開催されます. ぜひこの一週間でプログラミングを学んでみて参加しましょう！
プログラミングの腕に自信があるという方は, 土曜日に難易度が高めのARC 169が開催されるのでこちらにも参加してみましょう！
おわりに
競技プログラミングの興味が湧いてきたでしょうか. 競プロは楽しいだけでなく, 自分のスキル向上にも繋がりますし就職で有利になることもあるので, ぜひこの機会に始めてみて下さい！！
僕は12/08にも記事を出します. 書くのをさぼっていたので現在絶賛執筆中です(汗).
まだまだアドベントカレンダーは続くので楽しんでいきましょう！
-
AtCoder株式会社の社長であるchokudaiさんのブログを参考にしました. ↩
-
実際僕は三年前に始めたのですが, 始めて四か月ほどで飽きてしまいました...... ↩