はじめに

この記事では、世界的にも高い人気を誇る日本発の競技プログラミングサイトAtCoderを気軽に始める方法について説明します。競技プログラミングというとハードルが高く感じますが、簡単に言うとプログラミングで解くパズルのようなものです。数独や脳トレクイズくらいの感覚で捉えてください。

家で過ごす時間が増えるこのご時世、AtCoderは無料で遊べ、かつスキルも身につく最強の時間の使い方だと思います。競プロに興味はあるけれど最初の一歩を踏み出せずにいる方、何か新しいことを始めようと思ってる方、家で時間を持て余している方などなど…、ぜひこの記事を読んで興味を持ってもらえればと思います。

本記事の対象レベル

本記事は基礎的なプログラミングの知識ある方を想定しています。
基礎的なプログラミングの知識を確認したい方はAtCoder公式のプログラミングガイドを活用すると良いと思います。

C++入門 AtCoder Programming Guide for beginners (APG4b)

準備

まずは始めるための準備です。所要時間は10分程度です。

会員登録

AtCoderに参加するには会員登録が必要です。まずは会員登録しましょう。

入出力の練習

会員登録したらまずpractice contestの「A - Welcome to AtCoder」で入出力やコード提出の練習をします。ここは最初から答えを見てしまって構いません。この問題のコードをベースに他の問題に取り組むと良いでしょう。

ここで、問題を回答するにあたって言語を選択する必要があります。使い慣れた言語で構いませんが、個人的には(1)利用者数が多い(2)処理速度が速いという2つの理由でC++をおすすめします。AtCoderではコンテスト中でない限り他のユーザが提出したコードを見られるため、利用者数の多い言語を使うことで参考にできるコードが多くなります。

practice contestの「B - Interactive Sorting」はインタラクティブ形式の練習ですが、インタラクティブ形式の問題はあまり見かけないので飛ばしてしまって構いません。

動作確認環境の準備

より複雑な問題では、コード提出前の動作確認が必須になります。自分の使用する言語を手元のマシンで動作させる方法を確認しておきしましょう。

C++を使う場合、g++コンパイラがインストールされていれば以下のコマンドでコンパイルできるはずです。

$ g++ test.cpp

これによりtest.cppがコンパイルされ、同じフォルダに a.out が作成されます。以下のコマンドでa.outを実行できます。

$ ./a.out

AtCoderの問題では必ずサンプル入出力が用意されています。a.outを実行すると入力待機状態になるはずなので、サンプル入力を標準入力にコピペしましょう。プログラムの出力が対応するサンプル出力と同じなら動作確認完了です。いちいちサンプル入力をコピペするのが面倒であれば input.txt などにサンプル入力を保存しておいて以下のようにコマンドを実行しても構いません。

$ ./a.out < input.txt

これで準備は完了です。

AtCoder Beginner Contest の問題を解いてみる

さて、ここからが本番です。実は私は上記の準備の後、何から初めてよいかわからず１年くらい放置してしまっていました。そうならないために、準備完了の勢いのまま次に進みましょう。

まずは躊躇せずにAtCoder Beginner Contest (ABC)の過去問を解いてみましょう。過去に開催されたコンテストはコンテスト一覧ページから見ることができます。

ABCはAtCoderの中でも簡単な問題が出題されるコンテストで、難易度順に問題A~問題Fの6問で構成されています。問題Aは入出力の確認、問題Bは簡単な演算の確認程度です。問題Cからパズルっぽくなってきます。問題Cは問題文をアルゴリズムに変換できれば、総当たりのような愚直な実装で解ける問題が多いです。問題Dは計算量やメモリ量の制約のため、愚直な方法では解くことができず工夫が必要です。問題Eや問題Fは更に発展的な内容です。おそらく、最初は問題Cや問題Dで躓く方が多いのではないでしょうか。

最初は解くのが少し難しいくらいの難易度の問題をたくさん解けば良いと思います。試行錯誤の末に正解にたどり着いたときの達成感こそAtCoderの醍醐味だと思います。

十分考えてわからなければ解答を見てしまいましょう。最近の問題にはYouTubeの動画解説が用意されています。また、他のユーザの提出コードを見て参考にすることもできます。こんな考え方があるのか、またはこんな実装方法があるのかと驚くことが多く、とても刺激的です。最近、私が特に衝撃を受けたのはABC161のD問題「D - Lunlun Number」です。散々悩んだ末、回答を見たときは目からウロコでした。興味のある方は是非挑戦してみて下さい。

過去問に慣れてきたら本番のABCに挑戦してみましょう。コンテストの予定も過去問と同様コンテスト一覧ページに掲載されます。ABCは土曜か日曜の21:00~22:40の100分間開催さることが多いようです。本番のコンテストについては下記のような記事に詳しくまとめられています。

AtCoder コンテストについての tips
AtCoder Beginner Contest初参加してみた

AtCoderの問題を解くためのTips

AtCoderを始めとした競プロでは、知っておくと便利はお約束や逆に知らないとハマりがちな落とし穴があります。

大きい数字はlong long (C++)

競プロではintでは収まりきらない大きな数字が頻出します。アルゴリズムに自信があるのに一部の入力に対してWrong Answerになるときはintがオーバーフローしている可能性があります。大きい数字のときはlong longを使うと良いでしょう。以下のようにtypedefして使うことが多いようです。

typedef long long ll;
ll a;

bits/stdc++.hを使う (C++)

C++を使うのであれば、競プロで頻繁に活躍するvector、queue、mapなどのクラスを一括でインクルードできる<bits/stdc++.h>が便利です。AtCoder公式のAPG4bの「bits/stdc++.h の利用」でも使用が推奨されています。提出コードを見ると、ほとんどC++ユーザこれを使っている印象です。

#include <bits/stdc++.h>

〜　Macユーザのための参考情報　〜
私はMacを使っていますが、Macでは<bits/stdc++.h>がデフォルトでインクルードできないという問題があります。同様の問題を抱えている方は以下の記事を参考にして下さい。

Mac ユーザーのための c++ <bits/stdc++.h> インクルード方法
 Visual studio codeで競プロ環境構築[mac OS]

計算量を意識

AtCoderの問題にはすべての入力値に値の範囲が指定されています。特にABCのD問題以降はこの制約に応じてアルゴリズムの計算量を意識する必要があります。例えば$N\leq10^6$のとき、計算量$O(N^2)$では実行時間制限を超過（Time Limit Error: TLE）してしまうので、計算量$O(N\log{N})$など効率の良いアルゴリズムを考えなくてはなりません。問題文を見た時点で求められる計算量を見積もることができれば、何も考えずに実装してTLEして別アルゴリズムを検討する、という出戻りを減らすことができます。詳しくは後述の蟻本や下記の記事が参考になります。

レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【初級編：競プロを始めよう】
「1-1. 競プロとは何か」　→　「どんな問題が出されるか(2)」

1000000007で割ったあまり

ABC160 Fのように「〜を1000000007で割ったあまりを求めよ。」という問題があります。これは組み合わせの問題などで答えがオーバーフローしないようにするための工夫です。何も知らないと1000000007になにか意味があるのかと勘ぐってしまいますが、実際にはただの大きい素数です。難しく感じますが一度理解して計算方法に慣れてしまえば問題ありません。通常の整数型と同様に四則演算するだけで自動で余りを計算してくれる専用のクラスを用意している方もいます。詳しくは以下のような解説記事を見て下さい。

フェルマーの小定理を用いたCombination(組み合わせ)計算
 【競プロライブラリ】mint(modint)で学ぶC++

AtCoderをより楽しむための蟻本

蟻本とは「プログラミングコンテストチャレンジブック」の通称で、競プロ界隈で有名な参考書です。深さ優先探索、幅優先探索、動的計画法、データ構造、グラフ…といった競プロで頻出するテクニックが体系的に解説されています。少し難しめですが、この本に書かれているテクニックをマスターすればAtCoderをより楽しむことができ、さらにプログラマとしても一段レベルアップできると思います。

(マイナビBooksより)