競技プログラミング

競技プログラミングを始めよう！

はじめに

てくますプロジェクトのYukkinです！　この記事は、競技プログラミングに興味がある方や、これから始めてみたい方に向けて書きました。競技プログラミングとはどのようなものなのかや、どのように学び始めればよいのかを解説していきます。

この記事がきっかけとなり、競技プログラミングに挑戦する人が少しでも増えたら嬉しいです！

本記事は、数学・情報・論理パズルを楽しむ Techmath Project Advent Calendar 2024 の7日目の記事でもあります。アドベントカレンダーの応援や購読をしていただけると嬉しいです。

競技プログラミングってなに？

概要

競技プログラミング（通称：競プロ）は、プログラミングスキルを競い合うスポーツのようなものです。参加者は、限られた時間内にプログラムの問題をできるだけ多く正確に解くことを目指します。

一般的にプログラミングといえば、アプリ開発やシステム構築など「ものづくり」のイメージが強いですが、競プロは純粋にスキルを試す「競技」の世界を楽しむものです。

「競技」と聞くと難しそうに思えるかもしれませんが、心配はいりません！ 　問題には初心者向けから上級者向けまで様々なレベルが用意されており、誰でも気軽に始められます。自分のペースで取り組めるので、実力に応じた楽しみ方ができるようになっています。

競プロはこんな方にオススメ！
  • 論理的思考力や問題解決力を向上させたい方
  • プログラミングやアルゴリズムのスキルを向上させたい方
  • 競争心があり、自己成長したい方
  • 数学やパズルを解くのが好きな方

AtCoder

競プロを始めるには AtCoder というプラットフォームがおすすめです。

AtCoderでは、毎週末に AtCoder Beginner Contest（通称：ABC）が開催されています。このコンテストに参加して、レート（評価）を上げていくことが、一般的な目標になっています。

レートに応じて色が割り当てられており、次のようにランクが上がっていきます：
灰色 → 茶色 → 緑色 → 水色 → 青色 → 黄色 → 橙色 → 赤色

各色がどのレート範囲に対応しているかや、上位何％に該当するかなどの詳細は、AtCoderの公式情報 を参照ください。

ちなみに、私は現在「緑色」に位置しています！

ここから先は、競プロを始めたばかりの初心者（灰色ランク）が、どうすれば茶色や緑色を目指せるかについて、話していきます。

競プロ初心者が習得するべき知識

前提：言語選択について

競プロで最も一般的に使われている言語はC++で、次いでPythonです。

私自身はPythonを使用していますが、PythonはC++と比べて実行速度が遅いという特徴があります。現在の私のレベルでは、速度の遅さが問題になることはありませんが、処理速度が気になる方や将来的に高難度の問題に挑戦したい方は、C++を選択するのが無難です。

基本的な文法を理解しよう

入出力

競プロの問題では、入力値が与えられ、問題文に応じた処理を行い、出力値を返します。そのため、入力と出力の方法を理解することが、最初の第一歩です。

Pythonでの入力方法

# 整数
# 【1行】1数字
n = int(input())

# 【1行】複数数字
a, b, c = map(int, input().split())
l = list(map(int, input().split()))

# 【複数行】1数字
l = [int(input()) for _ in range(n)]

# 【複数行】複数数字
l = [list(map(int, input().split())) for _ in range(n)]

# 文字列
# 【1行】1単語
s = input()

# 【1行】複数単語
a,b,c = input().split()
l = list(input().split())

# 【複数行】1単語
l = [input() for _ in range(n)]

# 【複数行】複数単語
l = [list(input().split()) for _ in range(n)]

Pythonでの出力方法

# 1つ出力
print(s)

# 空白区切りで複数出力
print(*l)

# 区切り文字なしで複数出力
print(*l, sep="")

# 改行区切りで複数出力
print(*l, sep = "\n")

他の基本文法

ここまでの内容で、A問題を解けるようになるでしょう。

全探索問題を解けるようになろう

基本的な文法を使えるようになったら、全探索問題を解けるようになりましょう。

ここまでの内容で、B問題を解けるようになるでしょう。

典型アルゴリズムを習得しよう

次のような典型アルゴリズムを少しずつ理解していきましょう。それが初心者を抜け出し、中級者へと進む道です。

  • 累積和
  • bit全探索
  • 二分探索
  • 幅優先探索
  • 深さ優先探索
  • UnionFind
  • 動的計画法

などなど（他にもレベル別にたくさんあります）

典型アルゴリズムは、以下のようにいつでも取り出して使えるようにしておきましょう。

# めぐる式二分探索
# 全探索だとO(N)のものをO(logN)にするテクニック

# 二分探索で動かす変数の値がmidの場合に、条件を満たすかどうかを返却する
def solve(mid):
    # この部分を実装

# 二分探索
ok = 1 # 解が存在する値
ng = N # 解が存在しない値
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if solve(mid):
        ok = mid
    else:
        ng = mid
print(ok)

ここまでの内容で、C問題の多くに取り組め、D問題にもチャレンジできるようになるでしょう。

競プロ初心者はどうやって学べばよいか

基本的な文法に問題なければ、次の２つに専念するのが良いと思います。

  1. ABC（AtCoder Beginner Contest）の問題を解く
    • できるだけ多くの問題に取り組みましょう。
    • 毎週、可能な限りABCに出場して経験を積みましょう。
    • 過去問は AtCoder Problems を活用して解いてみてください。B問題まで大体解ける人は、A〜C問題を重点的に挑戦するなど、現在の自分より少し上のレベルの問題まで取り組むのが効果的です。
    • AtCoder Daily Training に参加して過去問に触れる機会を増やすのもおすすめです。
  2. 典型アルゴリズムの習得
    • 「鉄則本」を活用して、典型的なアルゴリズムを少しずつ学びましょう。

これらを着実に実践することで、茶色ランクはもちろん、緑色ランクを目指すことも十分可能です。

終わりに

競プロは、問題を解き明かしたときの達成感や、自分の成長を実感できる喜びを味わえる素晴らしい趣味です。あなたもぜひ、一緒に競プロに挑戦してみませんか？

ABC解説
情報科学の部屋へ

    コメントを書く

    お気に入りページ一覧