Arc's blog

競プロなど

トップ > 競技プログラミング > 競技プログラミングを始めよう(2020年版)

競技プログラミングを始めよう(2020年版)

競技プログラミング

2018年に書いた同タイトルの記事の2020年版です．競プロを始めるにあたって知っておくと良いことのまとめです．

競技プログラミングって何？

端的に言うと，プログラムを書いて数学パズルを解くeスポーツです．競技プログラミングの大会(コンテスト)では，難しい問題を速く解けると高い順位が得られます．

どんな問題が出るかを知りたい方はAtCoder Beginners Selectionを確認してみましょう．

主なプログラミングコンテスト

オンラインを中心に様々なコンテストが開催されています．メジャーなプログラミングコンテストを紹介します．

AtCoder

日本最大級のプログラミングコンテストサイトです．

定期的にコンテストが開催され，それぞれのコンテストの結果に応じて「レート」と呼ばれる数値が増減します．レートが高くなると嬉しくなります．

2020年現在では次のコンテストが開催されています．

  • AtCoder Beginner Contest (ABC)

    • レート増減対象: 0〜1999
    • 概ね週1回開催されるコンテストです．初心者〜中級者向けの問題が出題されます． とりあえずこのコンテストから参加してみましょう．

  • ARC級コンテスト

    • レート増減対象: 0〜2399
    • レート2400未満の人を対象としたコンテストとして，昔はAtCoder Regular Contest(ARC)が開催されていました．このレート帯を対象としたコンテストは現在「ARC級コンテスト」（もしくは単に「ARC」)と呼ばれています．冠スポンサー企業の名前がついたコンテストたちです．
    • 回にもよりますが，ABCの難易度の上限を更に引き上げたような問題構成です(1問目あたりは比較的簡単な問題が出ます)．

  • AtCoder Grand Contest (AGC)

    • レート増減対象: 1200〜
    • AtCoder最高難度のコンテストです．2020年6月のAGC045からレート増減対象が1200以上になりました(昔は無制限)．

      『 上級者向けのコンテンツです。初級者・中級者の方には難しい問題が多く出題されますのでご注意ください。』 AGC044 トップページ

Codeforces

世界最大級のプログラミングコンテストサイトです．多くのコンテストはJST23時台から2時間ほど行われるため，日本人にとってはつらいかもしれません．たまに18時台スタートのコンテストもあります．

このコンテストサイトでもレートが増減します．問題文は全て英語とロシア語で提供されることに注意．

Google Code Jam (GCJ)

Google社主催のプログラミングコンテストです．年1回行われるコンテストとしては世界最大級です．

オンラインで行われる予備予選と予選3回，そしてリアル会場で行われる決勝で構成されています．(2020年はコロナウイルスの影響で決勝もオンラインになってしまいました)

競プロの勉強をする

競プロが楽しそうに思えてきましたか？ 本格的に始めてみたくなったらこの下の記事を読んでみましょう．

言語を学ぶ

競技プログラミングでは様々なプログラミング言語を使えますが，主流はC++です．「使える言語がない！」という場合はAtCoder Programming Guide for beginners (APG4b)でC++の学習をしてみると良いと思います．競プロ用途としてのC++の機能はほぼ網羅できると思います．

もし何か使える言語がある場合は，その言語で問題を解いてみましょう．計算量がシビアな問題以外はどんな言語でも解けます．

以下，各プログラミング言語についての個人的な見解です．

  • C++
    • 競プロの主流言語．実行速度の速さ，ライブラリ(STL)の豊富さがメリット．ライブラリを使えばソートを1行で行ってくれる．
  • C
    • 実行速度はC++と同等レベルだが，文字列操作がしんどい．ライブラリが少ない．
    • Cの知識を元にしてC++への移行を考えてもいいと思う．
  • C#, Java
    • ライブラリは豊富．競プロ用途でも十分な実行速度を持つ(らしい)．
    • AtCoderの問題はJavaで解けると保証されている(ソース)．
  • Python
    • ライブラリは豊富．
    • 実行速度に限界を感じてきたらC++を触ってみると良いと思う．
  • その他
    • よく分かりません…ごめんなさい…

アルゴリズムを学ぶ

ABC300点以降の問題では，問題を解くために何らかのアルゴリズムを記述する場面が増えます．アルゴリズムを勉強するためのおすすめ書籍を紹介します．

アルゴリズム初学者におすすめの本です．豊富なイラスト図解とわかりやすい説明が魅力です．大学でアルゴリズムの勉強をある程度やっている人は，下の本に進んでもいいと思います．

通称「蟻本」．競プロで用いる主なアルゴリズムが網羅的に掲載されています．上の本より難易度は高め．私の高校の先生は「聖書」と呼んでいました(割と正しいと思います)．競プロにハマってきたら1冊持っておくと良いと思います．

問題を解く

AtCoder Problemsというサイトでは，過去にAtCoderのコンテストで出題された問題の一覧や，自分の解いた問題の一覧を確認できます．また，問題の推定難易度を表示してくれます．この推定難易度を参考にしながら問題を解くことができます．

例えば推定難易度(Difficulty)が400である場合，レート400の人が50%の確率で解けることを示します．(ソース)

過去問精選 10 問を読みながらAtCoder Beginners Selectionを解いてみるのもおすすめです．

競プロ関連のおすすめサービス

競プロ関連で私がよく使っている便利なサービスを記載します．

  • AtCoder Problems 既に紹介しましたが再掲．他にもVirtual Contest開催機能(過去問を選んで非公式コンテストを作成できる機能)などがあります．
  • Codeforces Problems 上のサービスのCodeforces版です．
  • ac-predictor AtCoderでのコンテスト中に，現在の順位からレートの増減をリアルタイムで予測してくれるサービスです．tampermonkeyによるブラウザ拡張機能が提供されています．
  • CF-Predictor 上のサービスのCodeforces版です．こちらもブラウザ拡張機能が用意されています．