はじめに
この記事は@drkenさん主催,「競技プログラミングを始めたばかりの人に伝えたいことアドベントカレンダー」3日目の記事です.
挨拶
こんにちは.こんばんは.Ruteです.(Twitter @rute_not_route)
私は現在大学3年生で, 競技プログラミングのコンテストに初めて参加してから2年8ヶ月の期間が経過しています.
AtCoderコンテストの参加回数は2021年12月3日現在105回です.
本記事では, これからAtCoder Beginner Contest(以降ABCと略します)に参加される皆さんに,ABCの取り組み方を説明したいと思います.
目次
| 章 | タイトル |
|---|---|
| 1 | はじめに:競技プログラミングとは |
| 2 | ABCへの参加方法:アカウント作成から競技開始前まで |
| 3 | ABCに挑戦！:競技開始から競技終了前まで |
| 4 | ABC終了後に取り組むこと:競技終了後 |
| 5 | ABCの対策方法(初心者向け) |
| 6 | おわりに:競プロ人口を増やしたい |
第1章 はじめに:競技プログラミングとは
この章では,競技プログラミングというものを知らない方向けに,競技プログラミング, それからABCについて説明します.
1.1 競技プログラミングとは
競技プログラミングとは,
参加者全員に同一の課題が出題され, より早く与えられた要求を満足するプログラムを正確に記述することを競う競技です.
(Wikpediaの文章より)
文章だけだと分かりづらい, という方もいると思います.
イラストで表すと,こんな感じです.
たとえば,以下のような問題が出題されます.
2つの整数$A,B$が与えられます. $A + B$の計算結果を出力して下さい.
例えばPython3という言語では, 以下のソースコードを記述することによりこの問題を解くことが出来ます.
ソースコード例
```python A,B = map(int,input().split()) print(A+B) ```第2章 ABCへの参加方法:アカウント作成から競技開始前まで
この章では,主にアカウント作成から競技開始前までの部分を説明します.
この章を読むことにより,ABC初参加への準備が整うようになります.
ABCに初めて参加する際に, 3つ行って頂きたいことがあります！
- AtCoderアカウントの作成
- ABC の参加登録
- Twitter アカウントの保有
2.1 AtCoderアカウントの作成
まずは,AtCoderアカウントの作成を行いましょう.
まずは,AtCoderの公式サイトの参加登録のボタンを押してみましょう.
すると,以下の様な画面が表示されます.
ここに,必要事項を記入して新規登録のボタンを押します.
ユーザ名, メールアドレス, パスワード, 国と地域 は必須入力項目です.
また, ユーザ名は登録すると基本的には1度しか変更が出来ないので考えてから登録して下さい.
これで,AtCoderアカウントの作成が完了しました.
2.2 ABC の参加登録
AtCoderへの登録が終わったら,ABCが開催されるページに移動しましょう.
AtCoderのコンテスト情報ページは主に2種類あるので,両方の画面でどこをクリックすればいいのかを画像で説明します.
参加登録の画面(2種類)
 すると, このような画面が表示されると思います.
次に, 青枠白抜き文字で表示されている参加登録ボタンを押しましょう.
この画面が表示されれば, 参加登録が完了したということになります.
Rated参加ボタン, Unrated参加ボタンについて
12/3以降に開催されるABCを含むコンテストページでは, これに加え「Rated参加ボタン」「Unrated参加ボタン」が追加されます.
Rated参加ボタンは, クリックすることによりこれまでのABCと同様Rated(レーティング変動がある)による参加となります.
Unrated参加ボタンは, クリックすることによりUnrated(レーティング変動がない)による参加となります.
睡眠不足や体調不良により本来のパフォーマンスを発揮できない場合は, こちらを選ぶようにしましょう.
なお,参加登録をした後にUnratedからRated, またはRatedからUnrated に変更したい場合は 参加登録をし直してからもう一度該当するボタンをクリックするようにしましょう.
変更はコンテスト開始後行うことができないので注意してください.
また, コンテスト開始5分後までに「Rated参加登録ボタン」をクリックしなければ, 自動的にUnratedになることにも気をつけて下さい.
また,この変更に伴って注意して欲しい点があります.
Rated参加ボタンをクリックした場合,
・ソースコードの提出をコンテスト時間中に行わなかった場合
・コンテスト期間中に問題を1問も閲覧しなかった場合
でもRatedになる点に注意して下さい.
例えば, 当日急な用事が入ってコンテストに参加することが出来なかった場合, これまではUnrated扱いでしたが,
今回のABCから0問正解と見なされその順位帯の成績となってしまいます.
2.3 Twitter アカウントの作成
Twitterは, 競技プログラミングに取り組まれている方の多くが利用しているSNSです.
Twitter上では, 分からない問題に関しての質疑応答,同じ趣味同士の方で趣味に関する情報の共有, 雑談などが行われています.
また, コンテスト開始前にはコンテストへの意気込み, コンテスト終了後にはコンテストの問題の解法などが多くツイートされます.
ぜひ,Twitterアカウントを作成することをお勧めします！
Twitterアカウントの作成方法は, 各自で調べて下さい.
そして, なるべく多くの競技プログラマーの方のTwitterをフォローするようにしましょう.
ちなみに, 本文章の主題から一度外れますが私のTwiterの紹介をします.
基本的に私のTwitterでは, 競技プログラミングのコンテストに関する事の他に, 趣味の音楽ゲームや日常などについて呟いています.
もしよろしければ, 再度掲示しますがTwitterのフォローもよろしくお願いします.
@rute_not_route(Twitter)
第3章 ABCに挑戦！:競技開始から競技終了まで
この章では, 主に競技開始から競技終了までの部分を説明します.
この章を読むことにより,コンテスト中の問題への取り組み方を知ることができます.
3.1 問題文の確認
コンテストが開始されると, 以下の様な画面が表示されます.
8問の問題が表示されると思いますが, まずは1番最初の問題である, A問題のページを開いてみましょう.
A問題のページ
各問題は問題文, 制約, 入力, 出力, 入力例と出力例の5つのセクションに分かれます.
それぞれについて説明します.
問題文
解決したい問題を説明している文章です.
ストーリー性があるものや, 端的に説明しているものなど, 文章の構成は様々です.
制約
入力で与えられる入力の値の制約などが表示されます.
入力
入力の形式が表示されます.
出力
出力するべき値について表示されます.
入力例と出力例
入力とそれに対する出力が表示されます.
3.2 提出
さて, 問題に関して解き方の方針が固まったら, ソースコードを実行環境などで記述します.
実行環境がPCなどにインストールされていない場合でも大丈夫です.
コードテストのページに直接プログラムのソースコードを記述し, 入力欄に入力を入れて実行することにより出力を確認することが可能です.
入力例に対応した出力が行われることが確認出来れば, いよいよ提出の段階に移ります.
コンテストページの提出ページに移動します.
提出ページは, **「言語」「ソースコードの記入欄」「提出ボタン」**によって構成されています.
**「言語」**を選択してソースコードを記入し, 提出ボタンを押しましょう.
提出が完了すると, このような画面になります.
(実際はXの部分に数字が入ります)
結果の部分にACと表示されていれば, 正解の判定になります.
提出結果の種類の一覧に関してはここでは説明しませんが,
AC以外の表示がされていると, 基本的には不正解の判定となります.(WJと表示されているときは正誤判定中です)
正解の判定が表示されれば, この問題に関する作業は終了です.
問題ページに戻ってB問題以降の問題を解きましょう.
3.3 順位の決定方法
「競技」プログラミングということで, 当然順位付けが行われます.
順位付けの方法は以下の順序によって行われます.
- 正解した問題の点数の総和(A問題,B問題2問なら300点)
-
最後に正解した時間 + （正解するまでに提出した）不正解の数*5分の時間
(A問題を10分で正解し,B問題で1回不正解の判定がされた後に20分で正解すれば,時間は25分となります.)
ABCを含む,競技プログラミングのコンテストでは基本的に「難易度が易しい順から」問題が並んでいることが多いです.
そのため, 解いた問題数に比例して順位が上がっていくことが多いです.
3.4 コンテスト中の注意
ABCコンテスト中に行ってはいけない行為があります.
それは以下の通りです.
- SNS上に「順位表から分かる」情報以外を投稿してはならない
- 2人以上で結託して解答してはならない
- について, 投稿しても良い情報は以下の通りです.
その時点での各問題に対するAC数
First ACした人
「全完した」などの発言
これらの情報は, 順位表から分かる情報であり,共有は問題ないです.
逆に, 投稿してはいけない情報は以下の通りです.
問題の解法に関する情報
WAの回数, TLEの回数, テストケース数など
これらの情報は, 共有された場合SNSを見た方のみが有利になってしまい, 競技性が成立しない, という状況になるため絶対に共有しないで下さい.
第4章 ABC終了後に取り組むこと:競技終了から
この章では, 主に競技終了からの部分を説明します.
この章を読むことにより, ABCの競技終了後に行うべきことがわかります.
4.1 公式解説ページの確認
競技終了後は, 解説が公開されます.
コンテストページを更新し, 解説 ページを確認しましょう.
(コンテスト終了直後はコンテスト全体の解説ページは表示されず, 問題毎の公式解説ページが表示されます)
各問題の公式解説ページには, 問題に対する解説とソースコードが記載されています.
AtCoderでは, C++の学習コンテンツが公開されているため, 基本的にはソースコードは**C++で記述されているものが多いです. Java, C#, PythonなどC++**以外の言語で参加されている方は, 問題によってはソースコードが記載されていない可能性があります.
この場合は**「第三者のソースコード」を見て理解する**, という方法もあります.
これは提出のページから「すべての提出」ページを選択することにより閲覧することが可能です.
(問題名, 言語, 判定, ユーザー名で絞って検索することも可能です)
解説を読んで, 解けなかった問題に対してはどのように考察をすれば良かったのか, どのような実装をすれば良かったのか を確認しましょう.
逆に, 解けた問題に対しては 考察の方法が解説と同じだったかを確認しましょう.
もしかすると, 考えた方針と解説の方針が異なる可能性があります. その場合は正解した問題でも もう一度実装するようにしましょう.
4.2 SNSやYouTube等の解説を利用
また, SNS等では ユーザー解説がツイートされることがあります.
はてなブログやQiita記事など, ブログ記事にして公開される場合もあります.
SNSでは気軽に問題に関する質問が出来るので, もし解説を読んでも分からない場合はツイートをされた方にリプライをして説明を求めてみましょう.
また,YouTubeにて解説動画を上げている方もいらっしゃいます.
これは宣伝にはなりますが, 私自身毎回のABCコンテスト終了後(22:45), YouTube上にて**「振り返り放送」と題してA問題からC問題までの問題を解説しています.
基本的にはPython3**でコーディングを行っています.
初心者の皆さんに分かりやすい解説を心がけていますので, よろしければチャンネル登録をして配信をお待ち下さい.
RuteチャンネルのURL
4.3 レーティングについて
コンテスト終了後しばらく時間が経過するとレーティングというものが付与されます.これは, 毎回のコンテストの成績によって変動します.
(参加回数が10回未満の場合,レーティングの変動がパフォーマンスよりも小さくなることもあります)
レーティングには色がつけられており,400区切りで色が変わっています.
初心者の皆さんは, まず「茶色(Brown)」レーティングに到達することを目指しましょう.
茶色レーティングは,**「一般的には十分高いレベルである」**と, AtCoder代表取締役の高橋 直大さんも自身のブログにて説明しています.
第5章 ABCの対策方法(初心者向け)
この章では, 主に競技プログラミング初心者の方々向けにABCの対策方法について説明します.
5.1 パフォーマンス値について
次の画像で示すデータは, ABC212からABC225までの14回のコンテストにおいてのパフォーマンス値と完数の一覧です.
パフォーマンス値, 完数の定義は以下の通りです.
- パフォーマンス値
- コンテスト毎に計算されるレーティングの値.
前述したレーティングを計算するために必要な値です.
ただし, パフォーマンス = レーティングではありません. - 完数
- 以下の計算式によって計算しました.
$(解いた問題の数) - min(1,(正答時間[秒]) / 6000)$
例えば, 2問を20分で解いた場合完数は1.80完となります.
茶パフォーマンス以上を取得するには, 平均的には3完以上の成績が必要なので, ここでは3完をするための対策として「A問題からC問題までの解き方」を説明します.
5.2.1 A問題の解き方
ABCのA問題では, 基本的にはこの分野の問題が問われます.
| 算数問題 | 条件分岐 | 簡単な文字列処理 |
|---|---|---|
| 特に条件分岐は, A問題の中でもよく問われています. | ||
| ABC215 A問題「Your First Judge」 | ||
| ABC216 A問題「Signed Difficulty」 | ||
| ABC223 A問題「Exact Price」 |
このような問題では, 基本的には
「条件にあてはまるならYes, 条件にあてはまらないならNoを出力しなさい」
という形式の出力が多いです
Python,C++だと, このように条件分岐を記述します.覚えておいてください.
条件分岐の書き方(Python)
if 条件:
print("Yes")
else:
print("No")
条件分岐の書き方(C++)
#include<bits/stdc++.h>
using namespace std;
int main(){
if (条件){
cout << "Yes" << endl;
}else{
cout << "No" << endl;
}
return 0;
}
5.2.2 B問題の解き方
ABCのB問題では, 基本的にはこの分野の問題が問われます.
| for文によるループ | 複雑な文字列処理 | 全探索 |
|---|---|---|
| 数学問題 | 配列 |
特にfor文によるループに関する問題が多く出題されています.
ABC213 B問題「Booby Prize」
ABC222 B問題「Failing Grade」
ABC229 B問題「Hard Calculation」
Python,C++だと, このようにfor文を記述します.覚えておいてください.
for文の書き方(Python)
for i in range(回数):
実行したい処理
for文の書き方(C++)
#include<bits/stdc++.h>
using namespace std;
int main(){
for (int i = 0; i < N; i++){
実行したい処理;
}
return 0;
}
基本的にはfor文を使った問題や全探索の問題が問われますが, たまに数学関連の問題が出題されることもあります. 少しギョッとするかもしれませんが, 問題文をよく読んで理解してから考察を考えてみましょう.
5.2.3 C問題の解き方
ABCのC問題では, 基本的にはこの分野の問題が問われます.
| 全探索 | Bit全探索 | 順列全探索 |
|---|---|---|
| 深さ優先探索 | 幅優先探索 | 工夫した全探索 |
| 二次元ソート | UnionFind | 動的計画法 |
特に,工夫した全探索など, 計算量を落とす問題は頻出ですので,
覚えておきましょう.ここで,計算量という概念についても説明します.
計算量
一般的なコンピューターでは, 1秒間に**$10^{8}$(1億)回程度の計算を行うことができます.
競技プログラミングの問題には, 「実行時間制限」が設定されています.
たいていの問題は「実行時間制限」が2秒で設定されています.
例えば, 入力のデータ数$N$**の制約が$ 1 \leq N \leq 2×10^{5}$などの場合, $N$の2乗に比例する計算量の処理を行うプログラムを記述すると, **TLE(実行時間制限超過)**となり不正解となります.
先ほどのような制約で, $N$の2乗に比例する計算量の処理を問題を解いている中で思いついた場合, **「計算量を落とすことができないか」**と一度考えるようにしましょう.
これまでA問題からC問題までの解き方を説明しましたが, 茶～緑のパフォーマンスで特に重要なのはB問題を解いた後のC問題の解答速度です.
C問題はB問題までと比べ難易度が上がることが多いです.この問題の解答速度によってパフォーマンスが変わることが多いので, なるべく早く解くことができるようにしましょう.
5.3 「早解き」を意識する.
過去のABCコンテストでは,ある問題とある問題の間で難易度の差があった際, 同じ点数の間でも取得出来るパフォーマンスの範囲が大きかった ということがありました.
以下は,「過去のあるABCの問題毎の難易度(Difficulty)」と, 「パフォーマンスと完数の関係」をまとめた表です.
ここで着目して欲しいのは朱色で色塗りした完数の部分です.
ABC214,ABC224の両方のデータを見ると,3完内のパフォーマンスの範囲が広いことが分かります.
これは, C問題とD問題の間にDifficultyの差があるために発生したことです.
ABCの問題セットは,基本的には
灰-灰-灰上位-(緑下位or茶上位)-水-青-(黄or橙)-赤
というDifficultyになるように問題の難易度が調整されていますが,希にこのような**「問題の難易度の差が存在する」**問題セットになる場合があります.
このような問題セットの場合は, 早解きをすることにより普段取得しているパフォーマンス値よりも高いパフォーマンス値を取得出来る可能性があります.
では, どのようにして早解き力を身につけたらよいか, ということですが, 個人的なオススメとしてはズバリ
過去のコンテストの「バーチャル参加」を行うことです.
過去のAtCoderコンテストのコンテストページには, 「バーチャル参加」というボタンが存在します.
このボタンをクリックすると, 以下の様な画面に移動します.
開始時刻を設定することにより, 開始時刻から100分間 コンテストと同様の時間で問題を解くことが出来ます.
また, 実際の順位表と比較して, コンテスト本番ではどのくらいの順位だったか を調べることが出来ます.
最初のうちは, 100分間参加して コンテスト同様に参加することをおすすめします. 時間がない, という方はA問題からC問題までを10分で解くことに挑戦してみましょう.
これは正直な所初心者の方に対してはかなり厳しいことを言ってしまうことになりますが, 先ほども言った通り茶色以上のパフォーマンス値を取得するためには平均的には3完が必須です.また, 難易度の差があることにより3完でも水色のパフォーマンス値を取得出来るので, バーチャル参加という機能を通じて楽に早解きの練習をしてもらいたいと思います.
第6章 おわりに:競プロ人口を増やしたい
この章が最後になります. この章では, 主にこれから競技プログラミングのコンテストに参加される方に私が伝えたいことを説明します.
さて, 「プログラミング」教育の必修化については, 既にニュースなどでも報道されていることもあり, 知っている方も多いと思います.
2020年からは小学校, 2021年からは中学校で「プログラミング」教育が必修化されました. 来年2022年からは高等学校で「プログラミング」教育が必修化される予定です.
また,2025年1月に実施される予定の, 大学入試共通テストから**「情報」**という科目が導入されます.
この科目では, 主にプログラミングやデータサイエンスに必要な統計処理, 情報リテラシーの知識が試され, IT人材の拡大に繋げるねらいがあります.
本記事の読者層が高校生・中学生・小学生のみに限らないのは十分承知です.
ですが, 「プログラミング的思考力」や「アルゴリズムの設計力」は現代社会(IT分野)において必要であると考えています.
「プログラミング的思考力」や「アルゴリズムの設計力」を鍛える教材として, 個人的には「AtCoder」を含む「競技プログラミング」を勧めたいです.
「AtCoder」の問題には基本的な入出力の問題から高度なデータ構造を扱う問題等, 様々な難易度の問題があり, これらの問題を解くことによってプログラミング的思考力などを向上させることが出来ると思います.
現在, AtCoderコンテストに参加されている日本人の人数は4000人程度です.この人数は, 最も参加者数が多かった1年半前のコンテストの参加人数の半分以下になっており, 競技人口の衰退も否めない状況になっています.
ABC 229 日本人参加者数
— じゅぴろ⚖ (@jupijupi111) November 27, 2021
register 3923 (-200), submit (-169) pic.twitter.com/n4XVZcrmMg
小学生・中学生・高校生の皆さんはこの記事を見て「プログラミング的思考力」向上などの目的で「AtCoderコンテスト」に参加してほしいと思います.
大学生の方で, もし"アルゴリズムに興味がある, プログラミングに興味がある"という方も同様に参加してほしいと思います.
AtCoderでは時々企業協賛コンテストが開催され, 好成績を収めることにより, 賞金がもらえるコンテストも存在します.
また, **AtCoder Jobs**という, AtCoderのレーティングによって就職活動を支援するサイトもありますので現23卒・24卒等の方はよろしければそちらを見て就職を検討して頂きたい と思っています.
社会人の方も, 「プログラミング能力を向上したい」「実務のプログラミングを利用して競技に参加したい」等と思っている方も同様に参加してほしいと思っています.
オススメコンテンツ「アルゴ式」
アルゴ式とは, 「競技プログラミング」の形式で問題を解くことにより情報科学を学習できるサービスです.
アルゴ式の公式サイトはこちら
このサービスでは,教科書・および付随する練習問題によって情報科学を学習することができます.
例えば, 「全探索」のコンテンツでは配列の全探索から二重ループの全探索まで,「競技プログラミング」で主に出題される問題と同様の問題を解くことが出来ます.
また, 従来の「競技プログラミング」とは異なり, 「プログラミングで学ぶ数学」と称して, 様々な数学の概念を「競技プログラミング」と同様の形式で学習できるコンテンツも存在します.
アルゴ式は今年8月1日に公開されたばかりの新しいコンテンツです. 競技プログラミングを始められる方は, ぜひこちらのサイトに登録してみて下さい. ABCの問題を解くときの参考になるかもしれません.
まとめ
最後になりますが, 本記事をここまで読んで頂き, ありがとうございました.
3日目にしては文章量がある記事だったと思いますが, 「競技プログラミングを始めたばかりの方に伝えたいこととしては, やはり『ABCの参加方法』や『ABCの対策方法』だろう」と思い当記事を作成致しました.
今後のAdvent Calendarでも様々なテーマで競技プログラミングの記事が公開されると思いますので, 何卒よろしくお願いします.
記事に関して質問や感想などがありましたらコメントにて投稿をお願いします.