はじめに

こんにちは、初めまして。東京大学1年のE8（いーはち）こと米田優峻と申します。私は趣味で「競技プログラミング（競プロ）」に参加しており、競技プログラミングの国内大手サイト「AtCoder 」では最上位ランクである赤色のレーティングを持っています。また、縁あって、昨年12月には書籍『「アルゴリズム×数学」が基礎からしっかり身につく本』（発行：技術評論社）を上梓させていただきました。

競技プログラミングは、オンライン上で出題された問題に対し、プログラミングを使って時間内にどれだけ多く正解できるかを競う大会です。競プロではプログラミングスキルも必要ですが、重要なのは“解き方”を思いつくこと、すなわちアルゴリズムを理解し、応用する力です。そこで本連載では、全24回・1年間にわたってさまざまなアルゴリズムについて取り上げていく予定です。

時には簡単なパズルなども交えながら、アルゴリズム初学者にもわかりやすいように解説していきますので、身構えず楽しんでお読みいただければ幸いです。今回は初回ということで、参加を通じてプログラミングやアルゴリズムを楽しみながら学べる競技プログラミングについて、例題と共にご紹介したいと思います。

競技プログラミングとは

先述の通り、競技プログラミングは、プログラミングを駆使して時間内にどれだけ多くの問題に正解できるかを競う大会です。IT 企業の採用現場などで利用されるコーディング試験と似ていますが、簡単な問題から超難問まで、出題範囲が広いため、初心者から熟練者まで楽しむことができるという特徴があります。

競技プログラミングの大会を開催するサイトは日本にも数多く存在しますが、なかでも有名なサイトの一つが AtCoderです。毎週土曜か日曜の 21 時からコンテストが開催され、全世界から同時に 5000 人以上が参加します。また、コンテストの成績に応じて「レーティング」と対応する「色」が付けられるため、1つでも上位の色に到達することが多くの参加者の目標です。特に、レーティングが 2800 以上（Top 0.2%）に到達し、赤色を付与された「レッドコーダー」は、参加者にとって憧れの対象となっています。

  • AtCoderのコンテストの流れ ※レッドコーダー保有者数は2022年1月17日現在

競プロで出題される問題

次に、競技プログラミングで出題される問題の例を1つご紹介しましょう。

整数 N を入力し、素数かどうかを 1 秒以内で出力するプログラムを作成してください。

制約： N は 2 以上 1013 以下の整数

出典： アルゴリズムと数学 演習問題集 012 - Primality Test

単純な解法として、「N が 2 で割り切れるか」「N が 3 で割り切れるか」…「N が N-1 で割り切れるか」を全部調べ、いずれも割り切れなければ「素数」と出力することが考えられます。これを Python で実装すると、次のようになります。

# 入力・全探索
N = int(input())
IsPrime = True
for i in range(2, N):
    if N % i == 0:
        IsPrime = False

# 出力        
if IsPrime == True:
    print("Yes")
else:
    print("No")

しかし、コンピュータといえど計算速度には限界があります。例えば家庭用 PC では 1 秒間に 108～109 回程度の計算しか行うことができず、N=1013 のケースではプログラムの実行に丸1日以上かかってしまいます。このような場面では、アルゴリズム（問題を解く手順）の改善が必要です。

例えば上の問題の場合は、N-1 まで全部試し割りする必要はありません。2 以上√N 以下の整数で割り、いずれも割り切れないときに「素数」と出力すれば、プログラムが正しくかつ高速に動作します。下図は N=19 の場合の計算過程を示しています。

このアルゴリズムを Python で実装すると次のようになり、N=1013 などの大きいケースでプログラムを実行しても1秒以内に計算が終わります※1。 

# 入力・全探索
N = int(input())
B = int(N ** 0.5) # √N 以下の最大の整数
IsPrime = True
for i in range(2, B + 1):
    if N % i == 0:
        IsPrime = False

# 出力
if IsPrime == True:
    print("Yes")
else:
    print("No")

このように、競技プログラミングではコーディングの能力だけでなく、より良いアルゴリズムを考えるスキルも大切です。また、アルゴリズムの改善は競技プログラミングの一番の醍醐味であり、難しいアルゴリズムを自力で思いついたときは嬉しい気持ちになるものです。

※1　改善されたアルゴリズムが必ず正しい答えを出力する理由については、プログラミングのWeb学習サイト「アルゴ式」の「素数判定のO(√N)アルゴリズム」で詳しい解説が無料公開（2022年１月現在）されています。

競プロに参加するメリット

競技プログラミングではプログラムを実際に書くので、プログラミング能力の向上に繋がります。また、先述の通りアルゴリズムが重要となる問題も出題されるため、論理的思考力や問題解決力を身に付けることができます。その他にも、数学の知識が身につく、就職活動に役立つ、単純に楽しいなどのメリットがあります。なお、競プロと就職について詳しく知りたい方は、AtCoder Jobs をご覧ください。

アルゴリズムを学んでいこう！

今回は競技プログラミングの概要と、アルゴリズムの重要性について説明しましたが、アルゴリズムは普段のプログラミングでも欠かせません。そこで次回以降は、いくつかの有名なアルゴリズムや、それらを実装するために必要なデータ構造について取り上げていく予定です。皆さんも楽しくアルゴリズムを学んでいきましょう!

最後に、本稿をお読みになり、少しでも競技プログラミングに興味を持たれた方は、ぜひ一度コンテストに参加してみてください※2。

※2　なお、AtCoderへの登録方法は、Qiita｜レッドコーダーが教える、競プロ上達ガイドライン【初級編：競プロを始めよう】でまとめているので、必要に応じて参照してください。