アルゴリズムをしっかり／中高数学駆け込み寺 素数判定の巻

今回は競プロを中心にして, アルゴリズムを勉強できるコンテンツやいくつかの取り組み方を紹介します.

数学系プログラミング問題集: Project Euler

何はともあれ, ここまで読み進めてきたあなたに, まず真っ先に紹介しなければならないサイトがあります.

archiveページからはじめの10題のタイトルを並べておきます.

タイトルからして完全に数学の問題です. 「これは楽しそうだ」と直観した方も多いのではないでしょうか. あなたもそうかもしれません.

Product Eulerの利用上の注意

ただし急いでつけ加えたい注意があります. このサイト, 正解を出せない限り正解が見られません.

AtCoderでは正解できなくても他の人の解答を見て勉強できるようになっています. 特に初学のうちは人の解答を見て勉強するのがとても大事です. しかしProject Eulerではそうはいきません. ある程度まで慣れてきたならともかく, 数学でも物理でもプログラミングでも, 初学のうちはよいモノを見て審美眼を磨くとともに, 読む訓練の徹底を勧めます.

特にあなたがこれから本格的にプログラミング学習をはじめるとしましょう. なかなか自力で書けるようになりません. 英語などの語学と同じです. もっと言えば日本語でもそうです. 日本語を読んだり話を聞くのはできても, きちんと文章を書ける人はなかなかいません. 真っ先に紹介こそしましたが, 実はいきなりアプローチするのはお勧めできないのです.

体系的なアルゴリズム学習・手法学習の重要性

そしてあえてProject Eulerを真っ先に紹介したもう一つの理由を伝えます. それはかなり早い段階で本格的なアルゴリズム学習を要求されるからです.

具体的にはProblem 18を見てみてください.

この問題文の下方, NOTEに次の記述があります.

Problem 67は同じ問題ですが100行あるため総当りでは解けません. もっと賢い方法が必要です.

少し調べてみると, 例えば動的計画法(dynamic programming)を使えば, (まともな時間で)解けると言われています. どんな本やコンテンツで勉強するかによりますが, 重要性を鑑みてかなり早い段階から議論をはじめる本もありますし, 何にせよまともな本ならまず書いてある手法です.

少なくとも競プロ入門レベルならプログラムも短くシンプルなので, プログラムやアルゴリズムに多少慣れていれば, 読むだけなら簡単に読め, わかった気にはなれるはずです. しかし問題を見たときに自力でアルゴリズムを書こうと思うと全く書けません. 一定以上の訓練が絶対に必要です.

何にせよ, 数学系のプログラムでも一般的なアルゴリズムの知識は絶対に必要です. それも中高数学どころか算数レベルであっても, プログラムを書いて計算しようと思うと目まいがするほどハードな計算や, ハードな手法が出てきます. 実は私自身, 教材研究としてProject Eulerに取り組む中でこの第18問に出会い, 「やはり腰を据えてきちんとアルゴリズムの勉強をしなければ駄目だ」と気付き, 今にいたります. 私自身の経験でもあるのです.

そうはいってもはじめの数十題は割とシンプルにプログラムが書けます. はじめの一歩にはお勧めです.

アルゴリズム学習へのいくつかのアプローチ

数学アルゴリズム系プログラムへの第一歩としてProject Eulerを紹介しました. そして何だかんだでアルゴリズムの基本的な知識や技術の習得の重要性も紹介しました. ではどうやって勉強を進めるといいか, いくつかのアプローチを紹介します.

もしあなたが大人なら: 本の紹介

まずあなたが大人で, ある程度の資金があるとしましょう. この場合はもう素直に本を買うのを勧めます. 硬軟織り交ぜていろいろな本があります. これを書いている2022/3時点ではなかなか難しいかもしれませんが, できれば実際に大きな書店に行って, 何冊か見比べてみてあなたにとって読みやすそうな本を探してみてください. もちろんお住まいの地域の問題もありますし, これを書いている2022年時点では新型コロナで難しい部分があるかもしれません.

プログラミング言語についてもいくつかバリエーションがあります. 少し古い本だとCやC++が多いのではないでしょうか. Javaもいくつかあるかもしれません. 最近はこのミニ講座でも採用したPythonで書かれた本が増えています. 本に載っているのはC++のプログラムであっても, オンライン含めた付録にはPythonのプログラムが載っている場合もあります.

ここではひとまず次の二冊を推薦しておきます.

どちらも図解が多く比較的読みやすいはずです. ネット上でサンプルコードも公開されています.

お勧めの理由

実はこれらをお勧めする理由がもう一つあります. それはアルゴ式・AtCoderとの対応です.

前者の大槻本はアルゴ式 https://algo-method.com の公式コンテンツです. プログラムをたくさん読み書きしなければ, 解きたい問題が解けるようになりません. AtCoderと違ってこのサイトは手法ごとにたくさんの問題が載っています.

中高の数学で散々経験したと思いますが, テスト範囲で「この方法で解ける問題しか出てこない」とわかっていても解けないことはよくあります. 手法指定のもとで解けるかどうかは理解の一つの試金石です. ぜひこのサイトとセットで勉強してみてください. 私もAtCoderが一段落したらこのサイトを一通り試してみる予定です.

後者の米田本はいわばAtCoderとの協賛で, https://atcoder.jp/contests/math-and-algorithm に自動採点システムがあります. プログラムの実行環境を作るのは大変ですし, プログラムが正しく書けているかチェックするのも大変です. そこをサポートしてくれるシステムがあるのだから, ぜひ使い倒してください.

サイト・サービスとセットの有料コンテンツとして, 書籍を二冊, 具体的に紹介しました. 買ってじっくり読み, そして書くのが大事で, しかも理解を深める上でも手っ取りばやいです. 本だけではなく各サービスも徹底的に活用して訓練してください. これだけでも一年は軽く遊び倒せるはずです.

もしあなたが中高生なら

次に中高生向けの対策を紹介します. もっと言えば自由に本を買えるお金がない人向けです. アルゴリズムの本は専門的な内容でもあるため, それほど安くありません. 中高の学参は高くても1000円程度の本が多いと思いますが, 大学の教科書や大人が買う技術書レベルになるとどうしても値段がはね上がります.

「親に買ってもらえばいいのでは?」と思う人がいるかもしれません. しかしそんな親がいる子供ばかりではありません. 教育熱心な親だとしても, そんなに自由にお金を出せる家庭ばかりではないのです. 「自分でアルバイトをすればいいのでは?」と思う人もいるでしょう. しかしそれこそ私は親が離婚して片親で, 中学三年で白血病にもなったので, 家にお金もなければ, アルバイトする体力もありませんでした. 上の二言は私自身にとって冗談ではありません. だからこの項はきちんと書き切る必要があるのです.

まずお勧めするのはやはり上で紹介した二サイトです.

上記二サイトは, 自分のマシンにプログラミング言語の実行環境を準備しなくてもいい点も優れています. ここでは特にアルゴ式を勧めます. AtCoderはあくまでコンテストが本体ですが, アルゴ式は教材が本体だからです.

プログラムを楽に書く上で, できればChromebook含めたパソコン, 最低でもキーボードがあるタブレットがほしいですが, 気合を入れればスマホでも何とかなるでしょう. (この講座を見ている以上, 少なくともスマホを持っているか, 家にネット環境とパソコンがあると推測しています.) これまた安くないのが難点ですが, スマホ用のキーボードもあります. Chromebookを含めたパソコンを買うよりは安いので, これで何とかする手がないではありません.

「どうしても教材がほしい!」

そうは言っても, 本やまとまったコンテンツがほしい・読んでみたい場合もあるでしょう.

実はオンラインで探せば無料のコンテンツがたくさん落ちています. いろいろな大学の講義資料もあれば, 著者が自分の本を公開していることさえあります. 特に英語は顕著です. 英語で読むのは大変かもしれませんが, 日本語の資料もたくさんあるのでぜひ探してみてください.

もちろん私自身も日々勉強しながら成果をコンテンツにまとめています. その結晶の一つがまさにこれです. 無料で提供している分であっても手を抜いて作っていません. 今後もいろいろな情報を提供していくので, ぜひ私の他のコンテンツも楽しみにしていてください.

補足: 理工系の総合語学

実は少なくとも数学・物理・プログラミングの分野では, 無料で優れたコンテンツがたくさんネットに落ちています. 英語で探すとさらにバリエーションが増えます. そもそもプログラミング言語の公式サイトなど公式情報はふつう英語です. ミニ講座の案内ページにも書いたように, このミニ講座は理工系向けの総合語学として, 数学・プログラミング方面に向けたコンテンツとして展開しています. 他にも語学, 特に英語に関する講座展開もあるので, 必要に応じてそちらも参照してください.

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

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

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

新しいコンテンツを作ったときにもこのメルマガで案内します.

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

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

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

またメールします.