競技プログラミングとは

はじめに

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

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

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

競技プログラミングとは

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

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

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

競プロで出題される問題

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

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

制約： N は 2 以上 10¹³ 以下の整数

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

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

# 入力・全探索