Who Am I

東京高専の情報工学科を2025年に卒業した三浦理稀です。
高専時代には高専プロコンに出たり、八王子のプログラミングコンテストの運営に携わったり、LINEヤフーのハッカソンに出たりいろいろしてました。本記事では、高専時代から今でもやっている競技プログラムの話をしていきます。

What's 競技プログラム

　競技プログラムは、与えられた問題をプログラムで解くゲームです。例えば次のような問題が与えられます。

100,000個の数値列A, Bが存在します。Aの各数値がBの中に存在するか調べてください。

問題にはプログラムの実行時間制限が定められており、１回の実行につき2秒ほどが体感多いです。この問題を解こうとすると次のような処理が考えられます。

- Bの数値一つずつについて、Aに一致する数値があるか一つずつ調べる

ただし、この処理は最悪のケースで100,000(Aの要素数)×100,000(Bの要素数)=百億回も数値が一致しているか調べる必要があります。Pythonであれば何十分もかかってしまう可能性もあります。（途方もない...）
この問題の一つの解法として、Aを小さい順に並び替えて（大きい順でもいい）、Bの各数値について二分探索をすることが考えられます。この処理は最悪ケースでだいたい190万回、数値が一致しているかを調べればよいので1秒足らずで処理を終えることができます。（速い！！！）
また、問題が次のように変わったとします。

100,000,000個の数値列A, Bが存在します。Aの各数値がBの中に存在するか調べてください。
ただし、各数値は0~999の間の値です。

この問題では先ほどの手法では制限時間に間に合わない可能性があるので別の手法を考える必要があります。
ここで、先ほどの問題にない条件（数値の制約）を踏まえると次の処理を考えることができます。

- サイズ1000の配列を用意し、0から999のインデックスに対してAに含まれる数値の有無を保存することで、Bの各要素がAに含まれているかを配列を参照して調べる

この処理では、数値列A,Bの個数と同程度ほどの操作しか行わないため非常に高速に処理を行うことができます。
競技プログラムでは、同じような問題でも与えられた条件に応じて解法が変わり、柔軟な発想力を鍛えることができます。

Welcome to 競プロ

競技プログラムは毎週土曜日にオンラインでコンテストを行っているAtCoderや、いろいろな人が問題を投稿しているMojaCoderなど簡単に始められるサイトがいくつもあります。また、与えられた条件に応じて高速な処理を考える競技プログラムは、目的に合わせてプロダクトを作るエンジニアにピッタリのトレーニングでもあると思います。興味の沸いた人はぜひ参加してください！