今日勉強したことを
つらつらと
logo

茶色コーダーのための最強の数学サイトがあった

2020/05/22 14:05
競技プログラミングで使う数学を学び直すのに、最適なテキストを見つけました。

緑くらいはすぐ行けるかと思ってたのですが、茶色で停滞中です。原因を考えてみると、数学をすっかり忘れているのが問題ではないかと思い当たりました。

いろいろ調べてみると、組み合わせや順列の数など高校数学の初歩はもちろん、整数論などの競技プログラミングに触れないとやらないような内容まで幅広かったです。競技プログラミングで使うような数学は大学数学レベルとなっていることも多く、高校数学を結構忘れてしまっている私にはつらいテキストが多かったです。

また、競技プログラミングで使う定理は割と偏りがあり、方程式や因数分解といった大学入試によく出る数学はそれほど出ません。

何冊か参考書も手にとってみたものの、欲しい情報がまとまっているテキストはありませんでした。

最適な参考書は無料で公開されていた

津山高専の松田 修先生、山中 聡先生著の津山高専生のための知って欲しい定理と証明です。

高専は中学卒業後に入る、高校と短大をあわせたような学校です。このテキストは高専 1 年生向けに著されたようで、中学数学さえマスターしていれば読めるようにできています。

競プロ頻出問題が盛りだくさん

フェルマーの小定理や順列、組み合わせ、等差数列、等比数列といった頻出問題がコンパクトにまとめられています。全部で 40p ほどで、サクッと読める量なのが嬉しいです。

定理をまとめたものなので、深く考えず暗記して問題ないと思います。この定理をプログラムに落とし込んでみることで、身について行くように感じました。

逆元を理解するために必要なガロア理論の入門書もある

「1000000007 で割ったあまり」の求め方を総特集! 〜 逆元から離散対数まで 〜といった記事を読むと、まるで常識のように逆元という概念が出てきます。競技プログラミングやるまで、私は聞いたこともありませんでした。

逆元は群論などの抽象代数学で出てくる概念です。その群という言葉を作ったのがエヴァリスト・ガロアで、群論を系統建てたのがガロア理論です。そのガロア理論も高専生向けのテキスト「ガロア理論を理解しよう 」も一緒に載っています。

知って欲しい定理と証明に比べてかなり難易度は高くなっていますが、頑張れば読み解けそうです。取り組んでみてもいいかなと思いました。


© 2021 simodake