競プロで遊ぼう: AtCoderの紹介／中高数学駆け込み寺 素数判定の巻

さて, 今回からは改めてアルゴリズムの話をします. 特に競プロ(競技プログラミング)の観点からの取り組み方を紹介します.

はじめに注意

はじめに書いておきます. このメルマガ執筆時点で私自身アルゴリズムや競技プログラミングの再勉強中です. どちらかと言えば「一緒に勉強していこう」くらいのスタンスで書いていますし, 「この辺が面白そう」, 「実際やってみて面白かった」という視点で書いています.

さて, 今回は競技プログラミングの話, それもAtCoderというサービスを中心に話をします. すぐに遊べるネタが大量にあり, オンライン上の資料もたくさんあるからです. 次回, 他のサイト・サービスやプログラミング・プログラミング言語に関して, もう少し勉強用の資料・情報をシェアします.

競プロ(競技プログラミング)とは何か

まず競技プログラミングを簡単に紹介しましょう. 競技プログラミングは適当に問題セットが与えられ, 問題をいかに早く解けるかを競う競技です. 早押しクイズのプログラミング版だと思ってもらえばいいでしょう. 他にはWikipediaの記述も参考にしてください.

競技プログラミングで出てくる問題は, 特にアルゴリズムを組んで解く問題が基本です. 数学的な設定にして具体的に言えば次のような問題です.

  1. 条件Aをみたす場合の数を求めよ.
  2. 条件をみたす解の有無を判定せよ.
  3. 条件をみたす問題の解を具体的に(1つ)構成せよ.

私がいま取り組んでいる入門レベルの問題では1番が多いです. ちなみに素数判定は1番か2番にあたります. 「素因数分解したときに因数となる素数の数を求めよ」と言われれば1番, 直接「素数かどうか判定せよ」と言われれば2番です.

たったこれだけですが, なかなかどうして難しく, そして楽しいのです. 以下, 条件をみたす場合の数を求める問題を意識した記述にしますが, 本質的な制約ではあります.

競プロでの制約

競プロでは次の大事な制約があります. これが難しく面白い点です.

素数判定で巨大な素数の判定するとき, ルートを取って計算量を削らないと凄まじい時間がかかったことを思い出してください. 常にそれを意識しながらプログラムを書く必要があります.

実際に問題を見てみよう

いろいろ書きはしましたが, これだけではなかなか具体的なイメージは掴めないでしょう. まずは次の記事を読んで, AtCoder https://atcoder.jp の簡単な問題を眺めてみてください.

後者のAtCoder Beginners Selectionは前者の記事を元にしたAtCoder公式のページです. こちらには解き終わった次のアクションとして, AtCoder Problems https://kenkoooo.com/atcoder/などが紹介されているため, あえて載せておきました. 2022/3時点で私が取り組んでいるのもまさにAtCoder Problemsです. 2022/1から再開して2022/3/13時点で300題中160題まで解いた状態です.

これ以外にもAtCoderのホームページ https://atcoder.jp/home の「常設中のコンテスト」を見ると, 次のような学習用コンテンツへのリンクがあります.

量が膨大なので圧倒されると思います. むしろ遊ぶネタがたくさんあると思ってのんびり取り組んでください. 上記AtCoderホームページ https://atcoder.jp/home の上から順に取り組めばいいでしょう.

AtCoderでは他の人が書いたプログラムも完全公開されています. 他の人のプログラムを読み解くのも非常に大事な勉強法です. AtCoder学習のいいところでもあります. ぜひAtCoderを使い倒してみてください.

競プロ学習のいいところ: 一題一題がコンパクト

一言で書きましょう. プログラムが短い点にあります. 短くても書くのは大変です. しかし他人が書いたプログラムを読むのは非常に大事な勉強法で, その読むのがとても楽なのです. 少なくともボリュームの点で.

アプリ開発・ゲーム開発では全体で1000行を越えるプログラムもふつうです. しかし競プロでの簡単な問題は一題ごとに10-20行程度で収まります. 言語によっては2-3行で書ける場合があります. 気楽に「空き時間にちょっと一題見てみよう」が成り立つレベルです.

このお手軽感は勉強を続ける上で決定的に大事です.

プログラミング言語を選ぶときの注意

いまの時点で一点だけ注意します. このミニ講座や紹介した有料講座ではプログラミング言語としてPythonを採用しました. しかし上記の初心者向けプログラミングコンテンツでは, プログラミング言語としてC++を採用しています. これにはいくつかの理由があります.

特に後者が重要です. 慣れないプログラミング言語を読み書きするのは, 慣れない外国語でやり取りするのと同じくらい大変です. そもそも意思疎通できないことさえふつうです. そこで「競プロやるならもうはじめからC++にしてしまえばいいのでは?」という話です. 慣れていない人がC++の開発環境を作るのは楽ではありません. しかしAtCoder上でC++のプログラムを実行でき, そこで面倒な部分を吸収してくれています.

Pythonでも大丈夫

これも念のためいまの時点でフォローしておきます. 最近はPythonの応用が広がっていて, 本やコンテンツでもPythonを採用している本が増えています. もちろんアルゴリズムの本でもPythonを使っている本が増えているため, 本を読むならPythonで書かれたアルゴリズムの本を探すのも楽になっています. 無理にAtCoder公式サイトのコンテンツだけで勉強する必要もなければ, C++で競プロに取り組む必要もありません. C++に馴染めないと思ったらぜひ別の言語で競プロやアルゴリズム学習に取り組んでみてください.

今回のまとめ

今回はAtCoderにフォーカスして勉強する方法を紹介しました. 原則無料で勉強できますし, AtCoder以外にブログやTwitterでも質の高い学習情報を出してくれている人がたくさんいます. 実際に私もAtCoderでプログラムを読み書き倒して楽しんでいます.

どうしても合う・合わないはあるため, 無理に競プロ, 特にAtCoderに挑む必要はありません. しかし無料で遊び倒せる上, そこでいい成績をおさめていれば就職にも直接役立ちさえする面白いサービスです.

次回は競技プログラミング系の他のサービスや, アルゴリズム学習に関する本やコンテンツを紹介します. お楽しみに.

最後に: 本家メルマガの案内

最後に改めて私の本家メルマガを案内します.

数学・物理・プログラミング, そしてそれらを学ぶ上で大事な英語を中心とした語学の情報を発信しています. もしあなたが私の活動や私からの情報に興味があるなら, ぜひ登録しておいてください. 新しいコンテンツを作ったときにもこのメルマガで案内します.

アンケートにご協力ください

何かご意見や感想があれば次の読者アンケートまでお願いします.

回答は確約できませんが, 直接返事をご希望ならこのメールへの返信でも構いません.

またメールします.